前へ / 戻る

デモ動画

　mp4 が再生可能なブラウザでご覧ください。

• ダイクストラ法( 456KB )
• クラスカル法その１( 226KB )
• クラスカル法その２( 504KB )

今日のまとめ

• 最短路問題にはダイクストラ法という決定版の高速なアルゴリズムがあります。
• 郵便配達員問題は、グラフがオイラーグラフ・半オイラーグラフのときは高速に解けますが、 奇数次数の頂点が多くなる程解きにくくなります。
• 最小連結子問題にもクラスカル法という高速なアルゴリズムがあります。
• 巡回セールスマン問題には残念ながら高速なアルゴリズムはなく、「ましな解」で満足するのが普通です。

宿題

• ここから download してください。
• 提出期限：6月18日(金)
• 提出方法：スキャンするか写メを撮るなどして、pdf ファイル・画像ファイル等を shiota＠is.kochi-u.ac.jp 宛に送信してください（＠は小文字）。
  • 上手く送れない人はメールで連絡してください。
  • ＠の後ろは is.kochi-u.ac.jp です。皆さんの s.kochi-u.ac.jp より1文字多いのでお間違え無いように。
• 件名に「組合せとグラフの理論第8回の宿題」と書いておいて頂けると有難いです。
• 宿題を複数回分まとめて提出されると見落とす危険があります。１回分ずつ送信してください。

前へ / 戻る