演習課題「ループで入力を取得しよう」
以下のフォーマットに沿って入力が行われます。
n (n 訪問点数)
x_1 y_1 (x_1 は 訪問点の x 座標、 y_1 訪問点の y 座標)
x_2 y_2 (x_2 は 訪問点の x 座標、 y_2 訪問点の y 座標)
・・・
x_n y_n (x_n は 訪問点の x 座標、 y_N 訪問点の y 座標)
右のコードエリアのプログラムは、訪問点の座標一覧を取得して、
貪欲法にもとづいて巡回する順序を(0,0)から出力するプログラムです。
しかし、このまま実行してもエラーになってしまいます。
このプログラムを修正して、正しく表示されるようにしてください。
プログラムを実行して、正しく出力されれば演習課題クリアです!
期待する出力値
0 0
2 3
4 5
1 9
演習課題「ループで入力を取得しよう」
以下のフォーマットに沿って入力が行われます。
```
n (n 訪問点数)
x_1 y_1 (x_1 は 訪問点の x 座標、 y_1 訪問点の y 座標)
x_2 y_2 (x_2 は 訪問点の x 座標、 y_2 訪問点の y 座標)
・・・
x_n y_n (x_n は 訪問点の x 座標、 y_ 訪問点の y 座標)
```
右のコードエリアのプログラムは、訪問点の座標一覧を取得して、
貪欲法にもとづいて巡回する順序を(0,0)から出力するプログラムです。
しかし、このまま実行してもエラーになってしまいます。
このプログラムを修正して、正しく表示されるようにしてください。
プログラムを実行して、正しく出力されれば演習課題クリアです!
期待する出力値
0 0
2 3
4 5
1 9
#08:貪欲法で解いてみよう
このチャプターでは貪欲法を使って巡回セールスマン問題を解くプログラムを完成させます。
3
90 100
40 15
30 30
拡張for文(for-each文) - 繰り返し処理 - Java入門
https://www.javadrive.jp/start/for/index8.html
本レッスンでは、貪欲法による最近傍(Nearest Neighbor)法と呼ばれるアルゴリズムについて学んできました。
巡回セールスマン問題の貪欲法のアルゴリズムは他にもいくつか有名なものがあり、特に近傍挿入法(Nearest Insertion)法は有名です。
2-opt法や3-opt法などのk-opt法は、実装が比較的簡単な、巡回セールスマン問題の局所解探索アルゴリズムです。
焼きなまし法やタブーサーチなどの局所解探索アルゴリズムとして有名な手法を利用してみるのも良いでしょう。
厳密な解の求め方としては、ビット列を利用した動的計画(DP)法による解法が15頂点程度までのデータに対して、現実的な時間で解を求められることが知られています。
また、整数計画法と分枝限定法を組み合わせた手法では、より多くの頂点をもつデータに対して厳密解を求めることができます。