用Python建模图形

Question

我正在尝试解决Python中与图形相关的问题。由于这是一个竞技编程问题，我不使用任何其他第三方软件包。

该问题以5 X 5的网格形式呈现图形。假设机器人处于网格上用户指定的位置。网格在左上角为(0,0)，右下角为(4,4)。网格中的每个单元格由以下3个字符之一表示。 ' b '(ascii值98)表示机器人的当前位置，'d '(ascii值100) 表示脏单元格，'-' (ascii值45)表示网格中的干净单元格。例如，下面是一个样本网格，在此机器人位于0 0：

b---d
-d--d
--dd-
--d--
----d

目标是以最少的步骤清理网格中的所有单元格。 一步被定义为一个任务，其中要么： i）机器人改变其位置 ii）机器人改变单元格的状态（从 d 更改为 -）

假设最初标记为b的位置不需要清洁。机器人可以向上、向下、向左和向右移动。

我的方法是： 我阅读了几篇关于图形的教程，决定将图形建模为25 X 25的邻接矩阵，其中0表示没有路径，1表示在矩阵中的路径（因为我们只能向4个方向移动）。 接下来，我决定应用Floyd Warshell的所有对最短路径算法，并总结路径的值。但我有一种感觉它不起作用。 我陷入了以下问题之一的困境：

i）最小生成树（由于我无法将网格建模并存储为图形，因此无法实现）。

ii）A*搜索（同样的猜测，但在这里也是同样的问题，我无法正确地将网格建模为图形）。

如果您能够提出解决此类问题的好方法，我将不胜感激。关于各种基于图形的问题的提示和伪代码（或链接）也会有所帮助。谢谢

- kaalobaadar

---

嗯，这不是比赛，而是一个名为HackerRank的论坛，我已经明确了我的问题解决方法，但是它并没有带我到任何地方。 - kaalobaadar

问题是否规定了有多少个正方形会变脏？ - Daniel Stutzbach

矩阵大小固定为5*5吗？ - Timothy

是的，矩阵固定为5 * 5。 - kaalobaadar

@DanielStutzbach 不，它没有指定脏方块的数量或位置，我们只有矩阵和起始位置。 - kaalobaadar

Answer 1

我认为你在这里提出了两个问题。

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-困难）。您有两个信息可以帮助限制问题，使其可处理：

1.图形是网格。

2.最多有24个脏方块。

我喜欢您在这里使用A*的直觉。它通常用于解决查找最小移动次数的问题。但是，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()）越紧，您可以跳过的分支就越多。

- Daniel Stutzbach

Answer 2

假设 V={v|v=b或v=d}，并获得完全连接的图 G(V,E)。您可以使用时间复杂度为O(n^2)计算E中每条边的成本。之后，问题变得完全相同：从指定的顶点开始，找到覆盖V的G的最短路径。

自1832年以来，我们称之为旅行商问题（TSP）。

- Timothy

Answer 3

这个问题肯定可以被储存为一个图。节点（脏单元格）之间的代价是它们之间的曼哈顿距离。忽略清理单元格的成本，因为无论采取什么路径，总成本都将相同。

- user1354999

Answer 4

这个问题看起来像是最小曼哈顿斯坦纳树问题。不幸的是，这个问题是NP难问题，所以如果我没错的话，你需要想出一个近似解（基于曼哈顿距离的最小生成树）。

- hytriutucx