ここで2つの質問をしていると思います。
1. この問題を Python でグラフとして表現するにはどうすればよいですか?
ロボットが動き回るとき、彼はある汚れた正方形から別の汚れた正方形に移動し、途中できれいなスペースを通過することもあります。あなたの仕事は、ダーティ スクエアを訪れる順番を決めることです。
# Code is untested and may contain typos. :-)
# A list of the (x, y) coordinates of all of the dirty squares.
dirty_squares = [(0, 4), (1, 1), etc.]
n = len(dirty_squares)
# Everywhere after here, refer to dirty squares by their index
# into dirty_squares.
def compute_distance(i, j):
return (abs(dirty_squares[i][0] - dirty_squares[j][0])
+ abs(dirty_squares[i][1] - dirty_squares[j][1]))
# distances[i][j] is the cost to move from dirty square i to
# dirty square j.
distances = []
for i in range(n):
distances.append([compute_distance(i, j) for j in range(n)])
# The x, y coordinates of where the robot starts.
start_node = (0, 0)
# first_move_distances[i] is the cost to move from the robot's
# start location to dirty square i.
first_move_distances = [
abs(start_node[0] - dirty_squares[i][0])
+ abs(start_node[1] - dirty_squares[i][1]))
for i in range(n)]
# order is a list of the dirty squares.
def cost(order):
if not order:
return 0 # Cleaning 0 dirty squares is free.
return (first_move_distances[order[0]]
+ sum(distances[order[i]][order[i+1]]
for i in range(len(order)-1)))
あなたの目標は、コストを最小限に抑える list(range(n)) を並べ替える方法を見つけることです。
2. この問題を解決するための最小移動数を見つけるにはどうすればよいですか?
他の人が指摘しているように、この問題の一般化された形式は扱いにくい (NP-Hard)。問題を扱いやすくするために制約するのに役立つ 2 つの情報があります。
- グラフはグリッドです。
- ダーティ スクエアは最大で 24 個です。
ここで A* を使用するあなたの本能が気に入っています。多くの場合、移動の最小数を見つける問題を解決するのに適しています。ただし、A* にはかなりの量のコードが必要です。Branch-and-Bound アプローチ (Branch-and-Prune と呼ばれることもあります) を使用する方が良いと思います。これは、ほぼ同じくらい効率的ですが、実装がはるかに簡単です。
アイデアは、次のように、深さ優先検索を使用してすべての可能なソリューションの列挙を開始することです。
# Each list represents a sequence of dirty nodes.
[]
[1]
[1, 2]
[1, 2, 3]
[1, 3]
[1, 3, 2]
[2]
[2, 1]
[2, 1, 3]
ブランチに再帰しようとするたびに、そのブランチがこれまでに見つかった最も安価なソリューションよりも高価であるかどうかを確認してください。その場合は、ブランチ全体をスキップできます。
それが十分に効率的でない場合は、残りのコストの下限を計算する関数を追加します。次に、cost([2]) + lower_bound(set([1, 3])) がこれまでに見つかった最も安価なソリューションよりも高価な場合は、ブランチ全体をスキップできます。lower_bound() が厳密であるほど、スキップできるブランチが多くなります。