我想你在这里问两个问题。
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）。您有两条信息有助于限制问题以使其易于处理：
- 该图是一个网格。
- 最多有 24 个脏方块。
我喜欢你在这里使用 A* 的直觉。它通常有助于解决找到最小移动数的问题。但是，A* 需要相当多的代码。我认为你最好使用分支绑定方法（有时称为分支和修剪），它应该几乎同样有效，但更容易实现。
这个想法是使用深度优先搜索开始枚举所有可能的解决方案，如下所示：
# 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() 越紧，您可以跳过的分支越多。