最短路径，最少打开算法 [英] Shortest Path, Least Turns Algorithm

问题描述

有一个方形网格的与障碍的。在该网格中，有一类人的两名成员。他们面临着一定的方向（上，右，左或向下）。每个人都有一个一定量的能量。制作人转或使其移动消耗能量（转向消耗1能量单位，运动消耗5点能量单位）。

There is a square grid with obstacles. On that grid, there are two members of a class Person. They face a certain direction (up, right, left or down). Each person has a certain amount of energy. Making the persons turn or making them move consumes energy (turning consumes 1 energy unit, moving consumes 5 energy units).

我的目标是让他们将尽可能靠近彼此相邻（pssed为曼哈顿距离EX $ P $），消耗最少的能源成为可能。请记住，有对电网的障碍。

My goal is to make them move as close as possible next to each other (expressed as the manhattan distance), consuming the least amount of energy possible. Keep in mind there are obstacles on the grid.

我将如何做到这一点？

推荐答案

我会做出假设，以后删除它们。

I'll make assumptions and remove them later.

假设网格是比1000×1000小，你不能耗尽能量..：

Assuming the grid is smaller than 1000x1000 and that you can't run out of energy..:

假如他们不能达到对方： 对于PERSON1，PERSON2，找到各自的到达点的集合，R1，R2。

Assuming they can't reach each other: for Person1,Person2, find their respective sets of reachable points, R1,R2.

（使用广度优先搜索为例）

(use Breadth first search for example)

排序R1和R2由x值。

sort R1 and R2 by x value.

现在通过R1和R2找到一对彼此最靠近的点。 提示：我们整理了两个数组，所以我们知道什么时候点接近他们的x坐标的条款。我们从来没有去更远的x坐标比目前发现的最小。

Now go through R1 and R2 to find the pair of points that are closest together. hint: we sorted the two arrays so we know when points are close in terms of their x coordinate. We never have to go further apart on the x coordinate than the current found minimum.

假设他们互相到达：从PERSON1使用BFS，直到你找到PERSON2并记录路径

Assuming they can reach each other: Use BFS from person1 until you find person2 and record the path

如果使用BFS找到的路径不需要转，那么这是解决方案，

If the path found using BFS required no turns, then that is the solution,

否则：

创建4份网格（称他们为右格，左格，上格，下网）。

规则是，你只能在左侧网格如果你是向左移动，你只能是在正确的格子，如果你是移动的权利，等等。要打开，你必须从一个网格移动到另一个（它使用的能量）。

the rule is, you can only be in the left grid if you are moving left, you can only be in the right grid if you are moving right, etc. To turn, you must move from one grid to the other (which uses energy).

创建此结构，然后使用BFS。

Create this structure and then use BFS.

例如：

现在左格假设你向左移动，所以创建从左边格，其中每个点被连接到剩下的能量的量在其点的曲线图，以向前移动。

Now the left grid assumes you are moving left, so create a graph from the left grid where every point is connected to the point on its left with the amount of energy to move forwards.

唯一的其他选项时，在左格是移动到向上网格或向下格（使用1能量），因此，连接从上格的相应格点和左格栅等等。

The only other option when in the left-grid is the move to the up-grid or the down-grid (which uses 1 energy), so connect the corresponding gridpoints from up-grid and left-grid etc.

现在您已经构建了图形，简单的使用广度优先搜索了。

Now you have built your graph, simply use breadth first search again.

我建议你用蟒蛇NetworkX，也只会是大约20行code。

I suggest you use pythons NetworkX, it will only be about 20 lines of code.

请确保你不接正方形，如果有在路上的障碍。

Make sure you don't connect squares if there is an obstacle in the way.

好运气。

这篇关于最短路径，最少打开算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！