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

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頂点程度までのデータに対して、現実的な時間で解を求められることが知られている。
    • また、整数計画法と分枝限定法を組み合わせた手法では、より多くの頂点をもつデータに対して厳密解を求めることができる。

認定証



学習ステータス


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

paizaラーニング『アルゴリズム入門編: 「ハノイの塔」を学ぶ (全10回)』を受講してみた

2021-03-31 21:20:20 | paiza

『アルゴリズム入門編: 「ハノイの塔」を学ぶ (全10回)』


メモ

＃01:ハノイの塔の問題を理解しよう

＃02:ハノイの塔のデータ構造を考えよう

  • 変数の用意と初期化メソッド、printメソッドの作成

＃03:1つの円盤を動かす処理

  • 円盤を動かすメソッドの作成

＃04:円盤が1枚、2枚、3枚のときの解法を考えよう

  • 1つ1つ指定して移動。

＃05:一般的な解法を考えよう

  • 再帰呼び出しを使う方法

＃06:再帰で実装する

  • 再帰呼び出しの実装
※ なぜそうなるのかよく分からんが、たった数行でハノイの塔が解けるなんて！？😲 
ここで、ジョブが進化

＃07:カウントを追加する

  • カウントを追加

＃08:円盤の移動回数を調べる

  • 円盤の枚数と移動回数
枚数移動回数
11
23
37
415
531
※ 前回の移動回数×2+1の関係だな
  • 移動回数＝2^n-1

＃09:特定のステップの状態を表示する

  • 指定したステップの状態を表示

＃10:まとめて移動して、再帰を省略

  • 再帰処理を減らして、円盤が多くても対応

認定証



学習ステータス


なんか文字が表示された状態でスクショされちゃったな😅