next up previous
: `なるべく最大に近い`とは? : appr : 問題(1),(2)対する多項式時間アルゴリズムの存在性

近似アルゴリズム(Betterな解を求める)

Bestな解を求めることは計算時間が多くかかるので, Betterな解を 求めるアルゴリズムが研究されはじめ, そのようなアルゴリズムを近似アルゴリズムと呼ぶ. 例えばグラフの最大クリーク問題では, △の答えはサイズが最大ではないが, どの2点間にも辺が存在するという条件は満たしている(図参照). もし, (ある条件を満たし), かつ, (最大のものを求めたい)という '最大`という条件を, `なるべく最大に近い`というものに置き換えたら 多項式時間のアルゴリズムが作れるかも知れない.



Koichi Yamazaki 平成12年3月15日