1

我有一个编程任务，要在“扇区”中找到从 START 到 GOAL 的最短路径。您可以将扇区可视化为节点的二维数组，其中一个节点为 START，另一个节点为 GOAL。所有其他节点都是 FLAT 或 HILL。你不能越过山丘。例如：

  0123456789
 |----------| {S = START, G = GOAL, " " = FLAT, # = HILL}
0|S         |
1|#####     |
2|          |
3|          | 
4|          | 
5|          | 
6|          | 
7|          |
8|   #######|
9|         G|
 |----------|

好的，所以我实施了 Dijkstra 算法来得出从 S 到 G 的最短路径。但是还有一个我无法弄清楚的额外问题，我希望能得到一些建议。如果它让我们找到一条更短的路径，我们将获得 5 颗炸弹来炸开 HILL。因此，对于我发布的示例扇区，我想使用 2 个炸弹来获得这样的路径：

  0123456789
 |----------| {S = START, G = GOAL, " " = FLAT, # = HILL, + = PATH}
0|S         |
1|#+###     | Blasted away HILL @ [1][1]
2|  +       |     4 bombs remaining
3|   +      | 
4|    +     | 
5|     +    | 
6|      +   | 
7|       +  |
8|   #####+#| Blasted away HILL @ [8][8]
9|         G|     3 bombs remaining
 |----------|

用于测试程序的扇区为 100x100，并且具有厚厚的“山脉”，因此只需 5 颗炸弹，您就可以将一条直线轰向目标或任何东西。

关于如何智能地计算使用炸弹的任何想法？现在，我有一个临时实现，它只是说“如果您当前正在查看的节点是 HILL 并且您还有炸弹，请炸毁 HILL”。显然这不会削减它，但我想不出如何正确地做到这一点。

感谢您的任何帮助。

4

1 回答 1

0

我假设在您的第一个解决方案中，您有一个图形连接，您有一个仅连接平面空间的图形。我建议您为每个 Hill 创建高成本边缘。例如，Hill 的每个传入边都需要 100000 个单位。所有其他边的成本为 1 个单位（仅作为示例）。

在您的第一个示例中，您可以在(0,0) -> (0,1)成本为 100000 之间获得优势。

因此，如果累积成本大于或等于 ，则需要停止搜索（在 Dijkstra 中，如果成本为相邻节点的搜索）(bombs + 1)*100000。

基本思想是你的算法会尽量减少成本，而使用炸弹是非常昂贵的。自然，最短的路径会找到炸弹最少的路径。如果您在最小路径上有 5 个炸弹，那么成本将是 500000 加上穿越平坦地形的成本。

于 2014-01-18T01:08:56.287 回答