NP完全問題と近似アルゴリズムとは？

NP完全問題と近似アルゴリズムとは、解の検証は多項式時間でできるが、多項式時間の解法が知られていない問題群のうち、互いに帰着可能で最も難しい部類をNP完全という。巡回セールスマン・ナップサック・充足可能性問題などが該当し、実務では厳密解を諦めて近似アルゴリズムやヒューリスティクスで実用解を得る。

えぬぴーかんぜんもんだいときんじあるごりずむ

応用情報技術者試験の頻出用語／テクノロジ系

NP完全問題と近似アルゴリズムの意味

解の検証は多項式時間でできるが、多項式時間の解法が知られていない問題群のうち、互いに帰着可能で最も難しい部類をNP完全という。巡回セールスマン・ナップサック・充足可能性問題などが該当し、実務では厳密解を諦めて近似アルゴリズムやヒューリスティクスで実用解を得る。

配送ルート最適化は訪問先が30か所でも全順列は天文学的な数になるため、まず貪欲法で近い地点をつなぎ、その後に経路の一部を入れ替えて改善する局所探索で実用解を作る。近似アルゴリズムには「最適解の2倍以内」のように保証比が示されるものもある。

「NP＝解けない問題」ではない。NPは検証が多項式時間でできる問題のクラスで、Pもその中に含まれる。またP≠NPは未解決であり、「NP完全問題には多項式時間解法が存在しないことが証明されている」という記述は誤り。

最終更新：2026-08-25／解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。