知能情報工学実験A 工学部知能情報工学科准教授高尚策（コウショウサク）実験概要  私の研究室：   質問など:   [email protected] 参考図書:   電子情報実験研究棟5階(5506室) 特になし、「プログラミング言語C 第２版」でも見てください実験の進め方: 学年進行で５週x３テーマ１．「ジャンケンプログラム」（担当：稲積泰宏）２．「画像データベース」（担当：村山立人）３．「巡回セールスマン問題の近似解を求めるプログラム」（担当：高尚策）  実験の目的プログラミング実習の雰囲気をつかむ．  資料収集、成果発表、コミュニケーション能力を伸ばす．  ソフトウェア設計技術の基礎の習得ソフトウェア設計の目的：    なぜ？    人間が意図した作業を代わりにコンピュータに行わせること人間は面倒なことはやりたくないコンピュータは疲れないそのための方法論を学ぶ  C 言語を題材に実験の流れ課題：「巡回セールスマン問題の近似解を求めるプログラム」  1回目（基礎知識）：    2回目（実装、テスト、提案）：   巡回セールスマン問題とその解法の調査（資料1,2,3参考）巡回セールスマン問題の解を求める基本的なアルゴリズムの実装（サンプル有り,資料４）と近似解を求めるアルゴリズムの提案 3回目（実装，テスト，データ作成）  提案したアルゴリズムの実装及び性能評価 4回目レポート報告と面談（１）  5回目レポート報告と面談（２）  レポートに関して  内容   実装したプログラムをレポート形式で報告実装が十分理解できればソース・コードを提出する必要はないレポート課題巡回セールスマン問題の近似解を求めるプログラムを作成せよ．作成したプログラムを用いて、下記の４つの都市データの最短経路を求めよ．（１） Eil51.txt （２） Eil101.txt (３) Ja9847.txt (４) Mona-lisa100K.txt  注意事項  データ・ファイルの見方   1行が1都市に相当各行の3つの数字の意味（例：”1 288 149”）    都市の番号（”1”）（都市の位置を 2 次元平面上にプロットした場合の） x 座標（”288”） y 座標（“149”）都市1  レポートに書くべきこと   実装したアルゴリズムの説明求めた解（ルート，総移動距離） 149 288 補足資料(1) Eil51.txt （a） Eil51の都市の分布（ｂ）Eil51 ＴＳＰの最良解総移動距離は４２６補足資料(2) Eil101.txt （a） Eil101の都市の分布（ｂ）Eil101 ＴＳＰの最良解総移動距離は629 補足資料(3) Ja9847.txt （日本都市）（a）都市の分布（ｂ）日本の都市によるＴＳＰの最良解総移動距離は491,924 補足資料(4) Mona-lisa100K.txt （a）都市の分布（ｂ）モナ・リザＴＳＰの最良解総移動距離は5,757,191