巡回セールスマン問題

研究室の教授に、「巡回セールスマン問題をC言語で書いてこい」と言われました。まったく何もわかりません。巡回セールスマン問題とは何か、と言うことは大体ネットなど使ってわかりました。C言語は基本的なことは書けます。初心者の僕は何から始めればいいでしょうか？？また、オススメの書籍などありましたら教えていただけませんか？よろしくお願いします。

No.3 回答者： wps_2005 回答日時： 2006/03/30 00:02

「巡回セールスマン問題をC言語で書いてこい」では教授の真意がよくわかりませんね。

巡回セールスマン問題が何なのかは勉強するとして、
・6都市ぐらいをしらみつぶしで調べるものを書くことが課題? → これなら単なるC言語のプログラミングの課題ですね。
・もっと大型の問題を解くための近似解算出アルゴリズムを調べることが課題? → こっちだったら、数多くの解法がありますから、プログラミング以前に調査してまとめなきゃいけないことがいろいろとありそうです。

講義での課題ならまだしも、研究室に配属になった方の、指導教官から与えられた課題から発せられた質問としてはどうかなあと思いますが。

巡回セールスマン問題を知りたいのなら、もっとも詳しいのは参考URLの書籍でしょう。

参考URL：http://www.amazon.co.jp/exec/obidos/ASIN/4254126 …

No.2 回答者： tatsumi01 回答日時： 2006/03/29 11:50

No. 1 のものですが補足します。

No. 1 の回答では、二つの都市Ａ、Ｂを結ぶ経路について、Ａ→ＢとＢ→Ａを結ぶコストが同じであることを前提にしていました。そうすると、No. 1 で書いたアルゴリズムはムダをしています（逆周りでも同じコストなのに計算している）。もっとも、この計算量は２倍程度ですから大したことはありません。
コストが非対称のとき（Ａ→ＢとＢ→Ａのコストが違うとき）に、No. 1 のアルゴリズムが成立しますが、(1) で読み込むコストの個数はＮ（Ｎ－１）になります。
問題集に掲載されている問題が対称か非対称かはわかりません。
なお、ホップフィールド型ニューラルネットワークで解く（近似）手法はコスト対称を前提にしていると思います。
また、このカテゴリで「巡回セールスマン」をキーにして検索すると以前の質問・回答が出てきます。中にはＣ言語のプログラムを示した質問もあります（間違っているという指摘もあるようですが）。

No.1 回答者： tatsumi01 回答日時： 2006/03/27 15:29

近似解でなく、厳密解を求められているのでしょうか。

厳密解は恐らく、全ての都市の順列についてコストを計算し最小値を求めるものでしょう。
どこから始めても同じですから、どこかの都市（Ａ）を固定し、Ａから始まる全ての都市の順列を作って、最後にＡに戻る経路を追加します。
(0) 都市数Ｎを入力する
(1) 二つの都市を結ぶコスト（Ｎ（Ｎ－１）／２個あります）をファイルから読み込む
(2) Ａから始まる都市の順列を一つづつ生成し、最後にＡを追加する
(3) (2) で生成した順列で、隣り合う都市のコストを加算し、メモリに格納する
(4) (2), (3) を全ての順列について計算し、最小値を求める
(5) 最小値と、それを与える順路を出力する
以上で完了です。
なお、この方法だとＮ！のオーダーの計算時間がかかります。Ｎ＝２０程度になったら、１週間近くかかるのではないでしょうか。
また、巡回セールスマン問題については、標準的な問題集（都市数ごとに都市間のコストを書いたテーブル）があり、正解も掲載されているそうです。バグの検出のためには問題集をダウンロードすると良いでしょう。

なお、厳密解ではなくニューラルネットワークで近似解を求めよという問題だったらまた違うアルゴリズムになります。