不惑にしてまだ何者でもない者のブログ

Arduino関連、Raspberry Pi関連、プログラミング学習

paizaラーニング『アルゴリズム入門編: 「巡回セールスマン問題」を学ぶ (全8回)』を受講してみた

2021-03-31 22:39:54 | paiza

『アルゴリズム入門編: 「巡回セールスマン問題」を学ぶ (全8回)』


メモ

＃01:巡回セールスマン問題とは?

＃02:入力データの形式を確認し、プログラムの枠組みを考えよう

  • 設計

＃03:2次元平面上の点を扱おう

  • Pointクラス：整数座標を表す
  • java.awt.Pointの使い方
    • import java.awt.Point;
    • Point p = new Point(x,y)
  • 2点間の距離の計算
    • Pointクラスのdistanceメソッド

＃04:2次元平面上の経路を扱おう

  • 経路の距離
  • 経路の表示

＃05:ロジックを変数、関数・メソッドで整理しよう 

  • tsp関数の作成

＃06:入力処理を作ろう

  • ループによる入力処理

＃07:貪欲法を考えよう

＃08:貪欲法で解いてみよう

  • 学びを深めるためのキーワードの紹介
    • 本レッスンでは、貪欲法による最近傍(Nearest Neighbor)法と呼ばれるアルゴリズムについて学んできた。
      巡回セールスマン問題の貪欲法のアルゴリズムは他にもいくつか有名なものがあり、特に近傍挿入法(Nearest Insertion)法が有名。
    • 2-opt法や3-opt法などのk-opt法は、実装が比較的簡単な、巡回セールスマン問題の局所解探索アルゴリズム。
    • 焼きなまし法やタブーサーチなどの局所解探索アルゴリズムとして有名な手法。
    • 厳密な解の求め方としては、ビット列を利用した動的計画(DP)法による解法が15頂点程度までのデータに対して、現実的な時間で解を求められることが知られている。
    • また、整数計画法と分枝限定法を組み合わせた手法では、より多くの頂点をもつデータに対して厳密解を求めることができる。

認定証



学習ステータス


最終的なジョブは、一流女剣士のままだったな


最新の画像［もっと見る］

コメントを投稿