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