近似解法

近似解法は、厳密な最適解を求めるのが難しい問題に対し、実用的な時間で、最適解に近い解を求める方法です。

■ 試験で押さえるポイント

• 貪欲法、局所探索法、焼きなまし法、遺伝的アルゴリズムなどがあります。

• 最適解である保証はありませんが、短い時間で十分によい解が得られます。

■ 過去問での着眼点

巡回セールスマン問題のような、厳密に解くと時間がかかりすぎる問題で使います。

例: 配送の経路を、近い所から順に回る方法（貪欲法）で決めます。