0

我必须找到从 D 点到 R 点的最短路径。这些是固定点。这是一个例子：

在此处输入图像描述

盒子还包含墙壁，除非你打破它们，否则你无法穿过它们。每破墙都会花费你，比如说“a”点，其中“a”是一个正整数。每一个不涉及墙的动作都会花费你1分。

任务是找出所有成本最低的路径，即破墙数量最少的路径。

由于框的宽度可以达到 100 个单元格，因此使用回溯是无关紧要的。它太慢了。我想出的唯一解决方案是这个：

  1. 如果没有墙壁，向东或向南
  2. 如果南有墙，检查西是否有墙。西有墙，破南墙。如果西边没有墙，就往西走，直到你找到一个没有墙的南边牢房。对南部和东部重复此过程，直到您按此顺序超过破墙的成本。如果从西边的路径进入同一个地方，就好像我打破了南墙并且花费相同或小于“a”点，那么使用这条路径，否则刹车南墙。
  3. 如果上面没有遇到，根据盒子边界来制动南墙或东墙。

重复步骤 1、2、3，直到“乘客”到达 R 点。这 3 个步骤之间存在“else-if”关系。

你能想出一个更好的问题算法吗？我用 C++ 编程。

4

4 回答 4

3

使用 Dijkstra，但对于不破墙的移动，成本为 1，破墙为 (a+0.00001)。然后 Dijkstra 会给你你想要的，在所有最低成本路径中打破最少墙壁的路径。

从概念上讲，想象一个旅行者可以跳过墙壁——同时跟踪成本——并且在面临两条路径的选择时也可以分成两个相同的旅行者，以便同时走他们两个（拿那个，罗伯特弗罗斯特！ ）。一次只有一名旅客移动，这是迄今为止成本最低的旅客。那个人动了动，在地板上写下“我只花了x 就到了这里”。如果我发现那里已经有这样的笔记，如果我更便宜地到达那里，我会擦掉旧笔记并写下我自己的；如果其他旅行者更便宜地到达那里，我会自杀。

于 2014-02-23T17:29:07.550 回答
1

由两部分组成的“先成本，后破墙”可以表示为一对 (c, w)，按字典顺序进行比较。c是成本，w是破墙数。这使它再次成为“单一事物”（在某种意义上），因此您可以将其放入算法等中，仅期望“成本”（作为抽象事物，它可能会增加其他成本或进行比较其他费用）。

所以我们可以只使用A*和曼哈顿距离启发式（也许有一些更聪明的东西不会完全忽略墙壁，但这会起作用 - 低估距离是可以接受的）。当然，移动成本不会忽略墙壁。邻居将是所有相邻的方格。所有成本将是我上面描述的那对。

于 2014-02-23T16:57:57.967 回答
0

这可以很容易地建模为加权图，然后将Dijkstra 的最短路径算法应用于它。每个方格都是一个节点。它连接到它相邻的正方形的节点。根据是否有墙，连接的权重为 1 或“a”。这将为您带来最低的成本。最低成本和最少的破墙次数可能不同。

于 2014-02-23T16:52:20.497 回答
0

这是一个通用算法（您必须自己进行实现）：

将矩阵转换为加权图：

  • 对于矩阵中的每个条目，创建一个Vertex.
  • 对于每个Vertex，创建一个数组Edges，每个相邻的一个Vertex。
  • 对于每个Edge，根据打破连接的两者之间的墙的成本定义一个权Vertices重Edge。

然后，在图表上运行 Dijkstra 算法 ( http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm )，从Vertex D. 作为输出，您将有最短（最便宜）的路径从图表上的Vertex D任何其他人，包括.VertexVertex R

于 2014-02-23T16:56:02.840 回答