課題レポート4: 力技で解く巡回セールスマン問題
＜目次＞
巡回セールスマン問題とは、与えられた都市集合全てをちょうど一度ずつ巡回し、出発都市に戻る際の総巡回経路長が最小となる経路を求める問題である。今回のレポート課題では「全ての経路長を調べ尽くした上で、最小となる経路を見つける（＝力技）」ようなプログラムを実装すること。なお、経路の組み合わせ数は後述するように「(N-1)!/2」通りとなるため、都市数が多い問題に対しては事実上解けない（調べ尽くすことができない）ことに注意すること。
- report4.zip
- 都市配置例
- input1.txt, input2.txt, input3.txt, input4.txt
- 1行目に都市数、2行目以降に各都市のx,y座標を記載。（例えば input1.txt の1行目は「8」であり、8都市分のデータが記載されていることを意味している）
- cities_input1.txt.pdf, cities_input2.txt.pdf, cities_input3.txt.pdf, cities_input4.txt.pdf
- 都市配置図作成スクリプト
- plot_map.py
- 使い方:
python3 plot_map.py input1.txt
- 上図は input1.txt の都市配置図であり、都市0〜都市7までの合計8都市が配置されている。
- セールスマンは都市0から出発し、残りの全て都市を1度ずつ巡回して都市0に戻るものとする。
- 例えば「都市0->都市1->都市2->...->都市7->都市0」のように巡回する経路を「012345670」と表記するとしよう。この時の経路長は「都市0->都市1」+「都市1->都市2」+...「都市7->都市0」により求められる。
- 「012345670」は一例であり、可能な巡回経路数は
7!/2だけ存在する。すなわち都市数をCと置くと(C-1)!/2であり、都市数の増加に応じて指数関数的に可能な巡回路数が増えてしまう。
- 例えば、都市数が3の時の巡回経路は「0120」「0210」の2パターンが考えられるが、この2つの経路は向きを考慮しなければ全く同じ経路であり、事実上1パターンしか存在しないことと同等である。「0120」を後ろから巡回すると「0210」になる。上記式において「/2」で割り算しているのは、向きを無視しているためである。
- 同様に、都市数が4の時の巡回経路は「01230」「01320」「02130」「02310」「03120」「03210」の6パターンがあるが、向きを無視すると3パターンとなる。
- 実装上は向きを考慮しても無視してもどちらでも構わないが、漏れ無く調べ尽くすようにしよう。
- 可能な巡回路全てを調べつくし、最短となる経路を求めよう。
- 可能な解をすべて列挙し尽くそう。
- 解の候補が指数関数的に増加する問題の場合、力技で解く（＝可能な解を全て調べ尽くす）のは無駄が多いという意味で本来はよろしくないが、今回はプログラミングの演習として「どうやれば全て調べ尽くすことができるか」を考え、実際に実装してみよう。
- 適度に関数化しよう。
- 今回の課題は具体的な関数仕様は指定しない。自由に設計・実装してみよう。ただし、1つの関数や、関数になっていないコードが50行を超える場合には分割や関数化すること。
- 自作した関数全てについて、docstringによるドキュメントを書こう。
- 自作した関数全てについて、doctestによるユニットテストを書こう。
- ダウンロードしたファイルには4種類の都市配置（input1.txt〜input4.txt）を用意している。これら4つの都市配置における最短路となる巡回経路を、力技で求めるプログラムを作ろう。
- 補足
- 実行イメージ（下記）
- レポートにはinput4.txtに対して処理した結果を掲載すること。
- 厳密に下記通りの出力とならなくても良いが、レポートには(1)読み込んだ都市数、(2)都市座標、(3)求めた最短経路長、(4)その際の巡回経路の4点を実行結果に含めること。
- レポートに掲載する結果は input4.txt のみで良いが、input1.txt〜input3.txt についてもコード修正無しで動作するプログラムを作成すること。
- 下記実行イメージではコマンドラインにて入力ファイルを指定している。コマンドラインにてファイル名を指定する方法は、授業13回目のコマンドライン引数の利用を参考にしよう。
- 4種類の都市配置（input1.txt〜input4.txt）各々について、最短となる巡回路を求めるのに要した時間を計測し、「横軸に都市数、縦軸に実行時間(sec)」を取る折れ線グラフを作図せよ。
- 補足
- レポートには、(1)グラフの作図方法を述べ、(2)グラフを掲載すること。
- グラフ作成には gnuplot か matplotlib を用いること。
- gnuplotはソフトウェア演習で演習済み。
- matplotlibは、ダウンロードファイルに含まれる「plot_map.py」を参考にするか、別途授業で補足する予定です。
- 時間計測には「time」コマンドを用いよ。例えばターミナル上で「time python3 report4.py input4.txt」として実行すると、処理に要した時間を計測し、出力してくれる。
- 時間計測結果の読み方
- 「python3 report4.py input4.txt 23.31s user 0.49s system 98% cpu 24.186 total」のように出力された場合、トータルで24.186秒かかったことを意味する。
- 自作した関数全てについて docstringによる簡易ドキュメント、doctestによるテストを記述せよ。
- docstringドキュメントには、(a)関数1行概要、(b)引数説明、(c)戻り値説明、の3点を記述すること。
- レポートには、工夫した関数を1つ選び、コード解説を掲載すること。
- 4種類の都市配置（input1.txt〜input4.txt）を解くのに要した時間から、都市数が12〜20まで増えたと仮定した時の実行時間を見積もれ。また、見積もった時間から、力技で解くアプローチの特徴について考察せよ。
- レポートには、(1)理由とともに見積もった時間を述べると共に、(2)力技で解くアプローチの特徴について考察せよ。
- 見積もり時間については、都市数12の時の見積もり時間、都市数13の時の見積もり時間、、、都市数20の時の見積もり時間、合計9件の見積もり時間を示すこと。
- 「見積もった時間」は目安で構わないが、理由をつけて見積もること。（どれだけ精度高い見積もりを出したとしても、理由が記述されていなければ減点です）
- ヒント
- input1.txtは8都市、input2.txtは9都市、input3.txtは10都市、input4.txtは11都市の例である。全巡回経路数は都市数により定まり、都市が増えると指数関数的に経路数が増える。経路数の増え具合と、実行時間との増え具合の間に何かしらパターンを見出すことはできないだろうか？
- (オマケ) 余裕がある人向けの発展課題です。前述1では力技で最短経路を見つけたが、「最適でなくても構わないので、ある程度良質の解を、低コストで見つける（なるべく無駄を省く）」ことはできないだろうか？ 自由に考え、提案し、実装してみよ。
- レポートには締め切りがある。締め切りに間に合わない場合には、取り組み具合が分かるように報告すること。（報告がない場合には加点しようがないです）
- [7/28追記補足]
- 何度か言ってますが、とても難易度は高いです。友人・先輩らと協力することを推奨します。
- 「途中段階まででの報告」や「（取り組む時間が無かったので白紙報告）」でも構わない。取り組んだところまでで採点をします。レポートを出さないと0点になるので注意。
- 例えば、課題詳細1のプログラムを完成することが困難である場合、以下の報告に代替しても構わない。（減点にはなるが、0点にはならない）
- 何かしら途中段階までの報告。
- 都市数4に限定したプログラムや、都市数5に限定したプログラムを個別に作成した報告。（都市数Nで汎用性のあるプログラムには至っていないが、指定した都市数について力技で解くプログラムについての報告）
- 課題詳細1を代替する場合、課題詳細2や4については下記情報を代替して見積もると良いでしょう。（なお、実行時間は実装やPCスペックに依存して異なりますので、自分で実装した人は自身の計測結果を採用して下さい）
- 都市数8で要した時間の例: python3 tsp.py input1.txt 0.05s user 0.01s system 93% cpu 0.067 total
- 都市数9で要した時間の例: python3 tsp.py input2.txt 0.24s user 0.01s system 97% cpu 0.259 total
- 都市数10で要した時間の例: python3 tsp.py input3.txt 2.00s user 0.04s system 99% cpu 2.052 total
- 都市数11で要した時間の例: python3 tsp.py input4.txt 20.64s user 0.36s system 99% cpu 21.027 total
# 実行イメージ
% python3 report4.py input1.txt
city_num = 8
[[20, 20], [120, 20], [220, 20], [70, 120], [170, 120], [270, 120], [20, 220], [120, 220]]
min_dist = 847.2135954999579, min_path = [0, 3, 6, 7, 4, 5, 2, 1, 0]
% python3 report4.py input2.txt
city_num = 9
[[20, 20], [120, 20], [220, 20], [70, 120], [170, 120], [270, 120], [20, 220], [120, 220], [220, 220]]
min_dist = 947.2135954999579, min_path = [0, 3, 6, 7, 8, 4, 5, 2, 1, 0]
% python3 report4.py input3.txt
city_num = 10
[[20, 20], [120, 20], [220, 20], [320, 20], [70, 120], [170, 120], [270, 120], [20, 220], [120, 220], [220, 220]]
362880
min_dist = 1047.213595499958, min_path = [0, 1, 2, 3, 6, 5, 9, 8, 7, 4, 0]
% python3 report4.py input4.txt
city_num = 11
[[20, 20], [120, 20], [220, 20], [320, 20], [70, 120], [170, 120], [270, 120], [370, 120], [20, 220], [120, 220], [220, 220]]
3628800
min_dist = 1147.2135954999578, min_path = [0, 1, 2, 3, 7, 6, 5, 10, 9, 8, 4, 0]
- ペアや友人らと話し合って取り組んで構わないが、コード解説を加えるなど「自分自身の報告書」となるように取り組むこと。試して分かったこと、自身で解決できなかった部分等についてどう取り組んだか、といった過程がわかるように示すこと。（考えを図表や文章を駆使して表現して報告する練習です）
- レポート作成は好きなツール（ソフトウェア）を使って構わない。ただし下記を含めること。
- タイトル
- 今回は「プログラミング1、レポート課題4: 「力技で解く巡回セールスマン問題」」。
- 提出日: yyyy-mm-dd
- 報告者: 学籍番号、氏名
- 複数人で相談しながらやった場合、相談者らを「協力者: 学籍番号、氏名」として示そう。
- 課題説明
- 結果と考察
- 課題への取り組みを通し、課題の意義、課題から分かったこと、今後の展望などを述べる。失敗やつまづきがあれば、それらについての失敗分析を含めること。
- 参考リンク: 実験レポートの書き方
- その他
- 通常は感想等をレポートには含めませんが、練習なので課題に取り組みながら何か感じたこと、悩んでいること等、書きたいことがあれば自由に書いてください。（なければ省略OK）
- 提出物は「レポート」、「作成したスクリプトファイル」の2点である。
- レポートは電子ファイルで提出するものとする。
- 提出先:
- 締切: 8/4(木)。