我想你在问两个问题。在
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)))
您的目标是找到一种重新排序列表(range(n))的方法，使成本最小化。在
2。如何找到解决此问题的最小移动次数？
正如其他人所指出的，这个问题的广义形式是难处理的(NP-Hard)。有两条信息有助于约束问题，使其易于处理：图形是一个网格。在
最多有24个脏方块。在
我喜欢你在这里用*的本能。它通常有利于解决求最小移动次数的问题。但是，*需要相当数量的代码。我认为您最好使用分支绑定方法(有时称为Branch-and-Prune)，这种方法应该几乎同样有效，但更容易实现。在
这样做的目的是使用深度优先搜索来列举所有可能的解决方案，如下所示：
^{pr2}$
每次要递归到某个分支时，请检查该分支是否比目前发现的最便宜的解决方案更昂贵。如果是这样，你可以跳过整个分支。在
如果这还不够有效，可以添加一个函数来计算剩余成本的下限。如果cost([2])+下限(set([1，3])比目前发现的最便宜的解决方案更昂贵，那么可以跳过整个分支。下限()越紧，可以跳过的分支越多。在