与えられたグラフについて、以下の2つの問題を解きます。 (1) コストが最小のハミルトン閉路を見つける。始点はaとする。 (2) TSP(巡回セールスマン問題)の最小全域木を用いた近似解法により、近似解を求める。
2025/7/22
1. 問題の内容
与えられたグラフについて、以下の2つの問題を解きます。
(1) コストが最小のハミルトン閉路を見つける。始点はaとする。
(2) TSP(巡回セールスマン問題)の最小全域木を用いた近似解法により、近似解を求める。
2. 解き方の手順
(1) コスト最小のハミルトン閉路の探索
ハミルトン閉路は、グラフ内のすべての頂点を一度ずつ通って始点に戻る閉路です。始点がaであるという制約の下で、可能なすべてのハミルトン閉路を検討し、そのコストを計算します。
考えられるハミルトン閉路の候補は以下の通りです。
* a-b-c-e-d-a : コスト 3 + 1 + 5 + 4 + 2 = 15
* a-b-c-d-e-a : コスト 3 + 1 + 6 + 4 + 2 = 16
* a-b-e-d-c-a : コスト 3 + 3 + 6 + 5 + 1 = 18
* a-b-e-c-d-a : コスト 3 + 3 + 5 + 6 + 2 = 19
* a-b-d-c-e-a : コスト 3 + 1 + 6 + 5 + 4 = 19
* a-b-d-e-c-a : コスト 3 + 1 + 6 + 4 + 5 = 19
* a-c-b-d-e-a : コスト 1 + 1 + 1 + 6 + 4 = 13
* a-c-b-e-d-a : コスト 1 + 1 + 3 + 4 + 2 = 11
* a-c-d-b-e-a : コスト 1 + 6 + 1 + 3 + 4 = 15
* a-c-d-e-b-a : コスト 1 + 6 + 4 + 3 + 3 = 17
* a-c-e-b-d-a : コスト 1 + 5 + 3 + 1 + 2 = 12
* a-c-e-d-b-a : コスト 1 + 5 + 4 + 1 + 3 = 14
* a-d-b-c-e-a : コスト 2 + 1 + 1 + 5 + 4 = 13
* a-d-b-e-c-a : コスト 2 + 1 + 3 + 5 + 1 = 12
* a-d-c-b-e-a : コスト 2 + 6 + 1 + 3 + 4 = 16
* a-d-c-e-b-a : コスト 2 + 6 + 5 + 3 + 3 = 19
* a-d-e-b-c-a : コスト 2 + 4 + 3 + 1 + 1 = 11
* a-d-e-c-b-a : コスト 2 + 4 + 5 + 1 + 3 = 15
* a-e-b-c-d-a : コスト 2 + 4 + 3 + 1 + 6 = 16
* a-e-b-d-c-a : コスト 2 + 4 + 3 + 6 + 5 = 20
* a-e-c-b-d-a : コスト 2 + 4 + 5 + 1 + 1 = 13
* a-e-c-d-b-a : コスト 2 + 4 + 5 + 1 + 1 = 13
* a-e-d-b-c-a : コスト 2 + 4 + 1 + 1 + 1 = 9
* a-e-d-c-b-a : コスト 2 + 4 + 1 + 5 + 3 = 15
最小コストは9で、ハミルトン閉路は a-e-d-b-c-a です。
(2) 最小全域木を用いた近似解法
最小全域木を求め、それを元にハミルトン閉路を構成します。
1. グラフの最小全域木を求める。
* Kruskal法またはPrim法を用いる。ここではKruskal法を用いる。
* 辺のコストが小さい順に辺を選んでいく。閉路ができないようにする。
* コストが1の辺：a-c, b-c, b-d を選択。
* コストが2の辺：a-d を選択。
* コストが3の辺：b-e, a-bはどちらも選べない。
* コストが4の辺：d-e を選択。
したがって、最小全域木は、辺 (a-c, b-c, b-d, a-d, d-e) から構成される。最小全域木のコストは となる。
2. 最小全域木の辺をたどって、始点aからすべての頂点を訪問する順序を決める。この順序を元にハミルトン閉路を作る。
例えば、aから始めて深さ優先探索を行う。
* a-c
* c-b
* b-d
* d-e
この順序だと a-c-b-d-e となる。
3. 訪問順序に従ってハミルトン閉路を作る。
a-c-b-d-e-a
4. このハミルトン閉路のコストを計算する。
1+1+1+4+2 = 9
3. 最終的な答え
(1) コスト最小のハミルトン閉路：a-e-d-b-c-a, コスト:9
(2) 最小全域木を用いた近似解: a-c-b-d-e-a, コスト: 9