このような問題を「巡回セールスマン問題」といい、最適化問題の命題としてよくとりあげられます。
都市数が少ないうちは、しらみつぶしに全経路を調べれば、ある程度の時間で解くことも可能でしょう。
しかし都市数が増えるにしたがって加速度的に難しくなっていくだけでなく、膨大な時間を要するように
なっていきます。
最適な解を見つけるためには、どのようにすればよいのでしょうか。
また、たとえ最適な解ではなくても、短時間で最適な解になるべく近い解(準最適解)を見つけるには、
どのようにすればよいのでしょうか。
このような最適化問題を解くために、本研究室では、
を用いた手法の研究を行っています。
|