工学部 知能情報工学科 准教授 高 尚策 （コウ ショウサク）

Presentation on theme: "工学部 知能情報工学科 准教授 高 尚策 （コウ ショウサク）"— Presentation transcript:

1 工学部 知能情報工学科 准教授 高 尚策 （コウ ショウサク）
知能情報工学実験A 工学部　知能情報工学科 准教授　　高　尚策　（コウ　ショウサク）

2 実験概要 私の研究室： 質問など: 参考図書: 実験の進め方: 電子情報実験研究棟5階(5506室)
参考図書: 特になし、 「プログラミング言語C 第２版」でも見てください 実験の進め方: 学年進行で５週x３テーマ １．「ジャンケンプログラム」（担当：稲積　泰宏） ２．「画像データベース」　　（担当：村山　立人） ３．「巡回セールスマン問題の近似解を求めるプログラム」　 　　　　　　　　　　　　　　　　　　　　　　　　 （担当：高　尚策） 開発過程; 解の精度とアルゴリズムの面白さで評価

3 実験の目的 プログラミング実習の雰囲気をつかむ． 資料収集、成果発表、コミュニケーション能力を伸ばす． ソフトウェア設計技術の基礎の習得
　ソフトウェア設計の目的： 人間が意図した作業を代わりにコンピュータに行わせること なぜ？ 人間は面倒なことはやりたくない コンピュータは疲れない そのための方法論を学ぶ C 言語を題材に

4 実験の流れ 課題： 「巡回セールスマン問題の近似解を求めるプログラム」 1回目（基礎知識）： 2回目（実装、テスト、提案）：
巡回セールスマン問題とその解法の調査（資料1,2,3参考） 2回目（実装、テスト、提案）： 巡回セールスマン問題の解を求める基本的なアルゴリズムの実装　（サンプル有り,資料４）と近似解を求めるアルゴリズムの提案 3回目（実装，テスト，データ作成） 提案したアルゴリズムの実装及び性能評価 4回目　レポート報告と面談（１） 5回目　レポート報告と面談（２）

5 レポートに関して 内容 実装したプログラムをレポート形式で報告 実装が十分理解できればソース・コードを提出する必要はない

6 レポート課題 巡回セールスマン問題の近似解を求めるプログラムを作成せよ．
　　作成したプログラムを用いて、下記の４つの都市データの最短経路を求めよ． （１） Eil51.txt （２） Eil101.txt (３) Ja9847.txt (４) Mona-lisa100K.txt

7 注意事項 データ・ファイルの見方 レポートに書くべきこと 1行が1都市に相当 各行の3つの数字の意味（例：”1 288 149”）
都市の番号（”1”） （都市の位置を 2 次元平面上にプロットした場合の） x 座標（”288”） y 座標（“149”） レポートに書くべきこと 実装したアルゴリズムの説明 求めた解（ルート，総移動距離） 288 149 都市1

8 補足資料(1) Eil51.txt （a） Eil51の都市の分布 （ｂ）Eil51　ＴＳＰの最良解 　　総移動距離は４２６

9 補足資料(2) Eil101.txt （a） Eil101の都市の分布 （ｂ）Eil101　ＴＳＰの最良解 　　総移動距離は629

10 補足資料(3) Ja9847.txt　（日本都市） （ｂ）日本の都市によるＴＳＰの最良解 　　総移動距離は491,924 （a） 都市の分布

11 補足資料(4) Mona-lisa100K.txt （ｂ）モナ・リザＴＳＰの最良解 　　総移動距離は5,757,191 （a） 都市の分布