GRAPH：找到一种算法来确定矩形迷宫中从一个点到另一个点的最短路径？ [英] GRAPH: find an algorithm to determine the shortest path from one point to another in a rectangular maze?
问题描述
我很头疼，想要从迷宫中的一个 START 位置移动到 EXIT 位置。
迷宫是矩形的， maxsize 500x500 ，理论上可以通过DFS和一些分支和绑定技术来解决...... p>
10 3 4
7 6
3 3 1 2 2 1 0
2 2 2 4 2 2 5
2 2 1 3 0 2 2
2 2 1 3 3 4 2
3 4 4 3 1 1 3
1 2 2 4 2 2 1
输出：
5 1 4 2
说明：
每次他踏出一步，我们的代理人都会释放能量，他只能向上，向下，向左和向右移动。另外，如果代理商剩余的能量达到零或更少，他就会死亡，所以我们会打印一些类似Impossible的内容。
因此，在输入 10 是初始代理的能量， 3 是 START 位置（即第3列第4行），我们有一个迷宫7x6 STRONG>。认为这是一种迷宫，我想找到让代理人有更好的剩余能量（最短路径）的出口。
如果有路径导致剩余能量相同，我们当然选择步数较少的那一种。
我需要知道一个DFS到迷宫500x500最坏的情况是可行的这些限制和如何做到这一点，存储剩余的能量在每一步和目前采取的步骤数。
输出表示代理已到达剩余能量= 5分两步到出口位置1 4。如果我们仔细观察，在这个迷宫中，也有可能在pos 3 1（第3列第1行）以相同的能量退出，但有3个步骤，所以我们选择更好的一个。
考虑到这些，有人可以帮我一些代码或伪代码吗？
我有一个二维数组以及如何存储剩余的能量，路径（或采取的步骤数量）的问题....
编辑：
拉里，正如我所说的，我对代码有点困惑。这是我到目前为止所尝试的，只是确定最短路径从START到EXIT的步骤较少，同时修复EXIT ...
public class exitFromMaze {
int energy，startY，startX，xMax，yMax;
int adjMatrix [] [];
布尔值visited [] [];
ArrayList< Cell>邻居;
// ArrayList< Cell>参观;
单元格开始;
Stack< Cell>栈;
public exM（）{
Scanner cin = new Scanner（System.in）;
int nrTests = cin.nextInt（）;
for（int i = 0; i< nrTests; i ++）{
energy = cin.nextInt（）;
startY = cin.nextInt（） - 1; //从columnstartY开始
startX = cin.nextInt（） - 1; //开始行startX
xMax = cin.nextInt（）; // 7 cols
yMax = cin.nextInt（）; // 8行
adjMatrix = new int [yMax] [xMax];
visited = new boolean [yMax] [xMax];
// visited = new ArrayList< Cell>（）;
this.stack = new Stack< Cell>（）; （int c = 0; c
visited [r] [c] = false;
//System.out.println(\"matrix[\"+r+\"][\"+c+] =+ adjMatrix [r] [c]）;
}
}
start = new Cell（startX，startY，0）;
// adiciona a pos actualàpilha de celulas / nos
stack.push（start）;
// printArray（yMax，xMax）;
findBestExit（）;
} // end_of_test_Cases
}
private void findBestExit（）{
//开始深度优先搜索
单元格curCell; （！（stack.empty（）））{
curCell =（Cell）（stack.pop（））;
while（！
//只是修复一个退出点...现在（如果它适用于一个，它必须适用于所有其他可能的退出）
if（curCell.row == 0&& curCell.col == 4）{
System.out.println（到达pos：+ curCell.row +，+ curCell.col +with E =+（energy-curCell.getEnergy（）） +with+ curCell.getSteps（）+steps）;
//完成= curCell;
休息;
} else {
visited [curCell.row] [curCell.col] = true;
}
this.neighbours =（ArrayList< Cell>）curCell.getNeighbours（this.xMax，this.yMax）;
for（Cell neighbourCell：neighbors）{
// 1-我认为这里缺少某些东西，这就是要削减一些案例的重点......不是吗？
if（curCell.getEnergy（）+ neighbourCell.getEnergy（）
neighbourCell.setSteps（curCell.getSteps（）+1）;
neighbourCell.setPrevious（curCell）;
stack.push（neighbourCell）;
}
// ...
}
}
//深度搜索和DIJKSTRA的结束？
}
class Cell {
int row;
int col;
int能量;
int步骤;
单元格之前;
//下一个节点;
public Cell（int x，int y，int steps）{
this.row = x;
this.col = y;
this.energy = adjMatrix [x] [y];
this.steps = steps;
//this.next = null;
this.previous = null;
}
public Cell（int x，int y，Cell prev）{
this.row = x;
this.col = y;
this.steps = 0;
this.energy = adjMatrix [x] [y];
this.previous = prev;
$ b @Override
public String toString（）{
return（，+ this.getRow（）+，+ this.getCol（） + ）;
}
public int getEnergy（）{
return energy;
}
public void setEnergy（int energy）{
this.energy = energy;
}
public Cell getPrevious（）{
return previous;
}
public void setPrevious（Cell previous）{
this.previous = previous;
}
public int getRow（）{
return row;
}
public void setRow（int x）{
this.row = x;
}
public int getCol（）{
return col;
}
public void setCol（int y）{
this.col = y;
}
public int getSteps（）{
return steps;
}
public void setSteps（int steps）{
this.steps = steps;
}
public cell south（int verticalLimit）{
Cell ret = null;
if（row<（verticalLimit - 1））{
ret = new Cell（row + 1，col，this）;
//ret.previous = this;
}
return ret;
}
/ **
*给出北方到我们当前的单元格
* @在这个方向返回单元格，如果不可能则返回null
*沿着这个方向前进
* /
public cell north（）{
Cell ret = null;
if（row> 0）{
ret = new Cell（row-1，col，this）;
//ret.previous = this;
}
return ret;
}
/ **
*给出我们当前单元格的西（左）
* @在这个方向返回单元格，如果它是$ b $，则返回null b *不可能沿着这个方向前进
* /
public cell west（）{
Cell ret = null;
if（col> 0）{
ret = new Cell（row，col-1，this）;
//ret.previous = this;
}
return ret;
}
/ **
*给出我们当前单元的东方向（右）
* @返回该单元的方向，如果它是$ b，则返回null $ b *不可能朝这个方向前进
* /
public cell east（int horizontalLimit）{
Cell ret = null;
//如果它在collumns的最大数目内
if（col <（horizontalLimit - 1））{
ret = new Cell（row，col + 1，this）;
}
return ret;
$ b $ public List getNeighbours（int xlimit，int ylimit）{
ArrayList< Cell> res = new ArrayList< Cell>（4）;
小区n;
n =南（ylimit）;
if（n！= null）{
res.add（n）;
}
n = north（）;
if（n！= null）{
res.add（n）;
}
n = east（xlimit）;
if（n！= null）{
res.add（n）;
}
n = west（）;
if（n！= null）{
res.add（n）;
}
return res;
}
}
private void printArray（int h，int w）{
int i，j;
//以矩形形式打印数组$ b $ System.out.print（）;
for（i = 0; i
}
System.out.println（）;
for（int r = 0; r
for（int c = 0; c< w; c ++）{
System.out.print（\t+ adjMatrix [r] [c]）;
}
System.out.println（）;
}
System.out.println（）;
public static void main（String args []）{
new exM（）;
对于输入：
1
40 3 3
7 8
12 11 12 11 3 12 12
12 11 11 12 2 1 13
11 11 12 2 13 2 14
10 11 13 3 2 1 12
10 11 13 13 11 12 13
12 12 11 13 11 13 12
13 12 12 11 11 11 11
13 13 10 10 13 11 12
它应该打印：
12 5 1 8
即代理退出一个更好的退出，（0,4），剩余能量= 12，并且只有8步。
有了我的想法，你的帮助，是否要求我指出我的失败或改正了他们？
我越来越厌恶这个......因为我必须让一些简单的事情变得复杂......
更多的输入/输出（当它不可能（Energy> 0），只需打印该事实即可）。
3
40 3 3
7 8
12 11 12 11 3 12 12
12 11 11 12 2 1 13
11 11 12 2 13 2 14
10 11 13 3 2 1 12
10 11 13 13 11 12 13
12 12 11 13 11 13 12
13 12 12 11 11 11 11
13 13 10 10 13 11 12
8 3 4
7 6
4 3 3 2 2 3 2
2 5 2 2 2 3 3
2 1 2 2 3 2 2
4 3 3 2 2 4 1
3 1 4 3 2 3 1
2 2 3 3 0 3 4
10 3 4
7 6
3 3 1 2 2 1 0
2 2 2 4 2 2 5
2 2 1 3 0 2 2
2 2 1 3 3 4 2
3 4 4 3 1 1 3
1 2 2 4 2 2 1
输出
12 5 1 8
再见残酷的世界！
5 1 4 2
使用基数方向上的隐式图表，使用Dijkstra的算法。使用堆实现它会是 O（V log V），这对于 500x500 应该足够好。当你第一次放松一个节点时，它会以最低的能量使用你可以到达的地方。你可以用这个算法很简单地设置一个节点的前奏。
编辑：一些伪代码，带有Dijkstra算法的解释：
函数Dijkstra（图形，源代码）：
//距离最远的地方无限远
dist =初始化大小为V的列表到无穷大
//没有顶点指向任何东西
previous =将大小为V的列表初始化为未定义
//从源到源的距离为0
dist [source] = 0
Q =优先队列
将所有顶点插入Q
，而Q不为空：
//获得距离源最近的顶点
current_vertex = Q.pop
如果dist [current_vertex] ==无穷
break
//这些是四个主方向上的相邻顶点$对于current_vertex旁边的每个顶点，b $ b：
//如果耗费更少的能量如果（dist [current_vertex] + energy [vertex]< top_vertex]，则转到vertex
// from current_vertex
if dist [vertex]）
dist [vertex] = dist [current_vertex] + energy [顶点]
前[vertex] = current_vertex
//另一个if语句在
//如果能量相同，则最小化步骤
//现在完成后，您应该将最便宜的成本设置为
//dist中的每个顶点。拿最便宜的一个。
//您可以在上一页后退，重建所采用的路径。
这是一般的伪代码，但您也必须记录步骤的数量作为一个决胜者，所以它不应该做太多的工作。
至于DFS解决方案，它取决于能量是多少。如果它是有界的，小的和int，那么可以将2D图转换为 xye 的3D图，其中 e 是剩余的能量 - 你从最初的能量开始，然后继续前进，但要记住你以前去过的地方。
编辑：对于DFS解决方案，对于E≤30000，H，W≤500它应该是 0（H * W * E），它不可能足够快，至少实时，并可能需要一点记忆。
I'm getting such an headache trying to elaborate an appropriate algorithm to go from a START position to a EXIT position in a maze. For what is worth, the maze is rectangular, maxsize 500x500 and, in theory, is resolvable by DFS with some branch and bound techniques ...
10 3 4
7 6
3 3 1 2 2 1 0
2 2 2 4 2 2 5
2 2 1 3 0 2 2
2 2 1 3 3 4 2
3 4 4 3 1 1 3
1 2 2 4 2 2 1
Output:
5 1 4 2
Explanation:
Our agent looses energy every time he gives a step and he can only move UP, DOWN, LEFT and RIGHT. Also, if the agent arrives with a remaining energy of zero or less, he dies, so we print something like "Impossible".
So, in the input 10 is the initial agent's energy, 3 4 is the START position (i.e. column 3, line 4) and we have a maze 7x6. Think this as a kind of labyrinth, in which I want to find the exit that gives the agent a better remaining energy (shortest path).
In case there are paths which lead to the same remaining energy, we choose the one which has the small number of steps, of course.
I need to know if a DFS to a maze 500x500 in the worst case is feasible with these limitations and how to do it, storing the remaining energy in each step and the number of steps taken so far.
The output means the agent arrived with remaining energy= 5 to the exit pos 1 4 in 2 steps. If we look carefully, in this maze it's also possible to exit at pos 3 1 (column 3, row 1) with the same energy but with 3 steps, so we choose the better one.
With these in mind, can someone help me some code or pseudo-code? I have troubles working this around with a 2D array and how to store the remaining energy, the path (or number of steps taken)....
EDIT:
Larry, as I said, I'me a little bit confused about the code. Here's what I've tried so far, only to determine the shortest path with less steps from START to EXIT, fixing EXIT in the meanwhile...
public class exitFromMaze {
int energy, startY, startX, xMax, yMax;
int adjMatrix[][];
boolean visited[][];
ArrayList<Cell> neighbours;
//ArrayList<Cell> visited;
Cell start;
Stack<Cell> stack;
public exM() {
Scanner cin = new Scanner(System.in);
int nrTests = cin.nextInt();
for (int i = 0; i < nrTests; i++) {
energy = cin.nextInt();
startY = cin.nextInt()-1; //start at columnstartY
startX = cin.nextInt()-1; //start at line startX
xMax = cin.nextInt();//7 cols
yMax = cin.nextInt(); //8 rows
adjMatrix = new int[yMax][xMax];
visited = new boolean[yMax][xMax];
//visited = new ArrayList<Cell>();
this.stack = new Stack<Cell>();
for (int r = 0; r < yMax; r++) { // yMax linhas
for (int c = 0; c < xMax; c++) { // xMax colunas
adjMatrix[r][c] = cin.nextInt();
visited[r][c] = false;
//System.out.println("matrix["+r+"]["+c+"] = "+adjMatrix[r][c]);
}
}
start= new Cell(startX, startY, 0);
//adiciona a pos actual à pilha de celulas/nos
stack.push(start);
//printArray(yMax, xMax);
findBestExit();
}//end_of_test_Cases
}
private void findBestExit() {
// BEGINNING OF DEPTH-FIRST SEARCH
Cell curCell;
while (!(stack.empty())) {
curCell = (Cell) (stack.pop());
//just fix an exit point ...for now (if it works for one, it has to work for all the other possible exits)
if (curCell.row==0 && curCell.col== 4) {
System.out.println("Arrived at pos: "+curCell.row+","+curCell.col+" with E= "+(energy-curCell.getEnergy())+" with "+curCell.getSteps()+" steps");
//finish = curCell;
break;
} else {
visited[curCell.row][curCell.col] = true;
}
this.neighbours = (ArrayList<Cell>) curCell.getNeighbours(this.xMax, this.yMax);
for (Cell neighbourCell: neighbours) {
//1- I think something's missing here and it would be here the point to cut some cases...isn't it?
if ( curCell.getEnergy() + neighbourCell.getEnergy() < this.energy && !visited[neighbourCell.row][neighbourCell.col]){
neighbourCell.energy+= curCell.energy;
neighbourCell.setSteps(curCell.getSteps()+1);
neighbourCell.setPrevious(curCell);
stack.push(neighbourCell);
}
// ...
}
}
// END OF DEPTH-FIRST SEARCH and DIJKSTRA?
}
class Cell {
int row;
int col;
int energy;
int steps;
Cell previous;
//Node next;
public Cell(int x, int y, int steps) {
this.row = x;
this.col = y;
this.energy = adjMatrix[x][y];
this.steps = steps;
//this.next = null;
this.previous = null;
}
public Cell(int x, int y, Cell prev) {
this.row = x;
this.col = y;
this.steps = 0;
this.energy = adjMatrix[x][y];
this.previous = prev;
}
@Override
public String toString() {
return "(,"+this.getRow()+","+this.getCol()+")";
}
public int getEnergy() {
return energy;
}
public void setEnergy(int energy) {
this.energy = energy;
}
public Cell getPrevious() {
return previous;
}
public void setPrevious(Cell previous) {
this.previous = previous;
}
public int getRow() {
return row;
}
public void setRow(int x) {
this.row = x;
}
public int getCol() {
return col;
}
public void setCol(int y) {
this.col = y;
}
public int getSteps() {
return steps;
}
public void setSteps(int steps) {
this.steps = steps;
}
public Cell south(int verticalLimit) {
Cell ret = null;
if (row < (verticalLimit - 1)) {
ret = new Cell(row+1, col, this);
//ret.previous = this;
}
return ret;
}
/**
* Gives the north to our current Cell
* @return the Cell in that direction, null if it's impossible
* to go in that direction
*/
public Cell north() {
Cell ret = null;
if (row > 0) {
ret = new Cell(row-1, col ,this);
//ret.previous = this;
}
return ret;
}
/**
* Gives the west (left) to our current Cell
* @return the Cell in that direction, null if it's
* impossible to go in that direction
*/
public Cell west() {
Cell ret = null;
if (col > 0) {
ret = new Cell(row, col-1,this);
//ret.previous = this;
}
return ret;
}
/**
* Gives the east direction(right) to our current Cell
* @return the Cell in that direction, null if it's
* impossible to go in that direction
*/
public Cell east(int horizontalLimit) {
Cell ret = null;
//if it's inside the number max of collumns
if (col < (horizontalLimit - 1)) {
ret = new Cell(row , col+1, this);
}
return ret;
}
public List getNeighbours(int xlimit, int ylimit) {
ArrayList<Cell> res = new ArrayList<Cell>(4);
Cell n;
n = south(ylimit);
if (n != null) {
res.add(n);
}
n = north();
if (n != null) {
res.add(n);
}
n = east(xlimit);
if (n != null) {
res.add(n);
}
n = west();
if (n != null) {
res.add(n);
}
return res;
}
}
private void printArray(int h, int w) {
int i, j;
// print array in rectangular form
System.out.print(" ");
for (i = 0; i < w; i++) {
System.out.print("\t" + i);
}
System.out.println();
for (int r = 0; r < h; r++) {
System.out.print(" " + r);
for (int c = 0; c < w; c++) {
System.out.print("\t" + adjMatrix[r][c]);
}
System.out.println("");
}
System.out.println();
}
public static void main(String args[]) {
new exM();
}
}
For the input:
1
40 3 3
7 8
12 11 12 11 3 12 12
12 11 11 12 2 1 13
11 11 12 2 13 2 14
10 11 13 3 2 1 12
10 11 13 13 11 12 13
12 12 11 13 11 13 12
13 12 12 11 11 11 11
13 13 10 10 13 11 12
It should print:
12 5 1 8
i.e., the agent exit in a better exit, (0,4),with the a remaining energy= 12 and in only 8 steps.
With my ideas, your help, is it ask to much to point me out my fails or correct them? I'm getting so sick of this ... because I gotta be complicating something easy...
More inputs/outputs (when it's not possible to achieve an exit alive (with Energy>0), just print that fact).
3
40 3 3
7 8
12 11 12 11 3 12 12
12 11 11 12 2 1 13
11 11 12 2 13 2 14
10 11 13 3 2 1 12
10 11 13 13 11 12 13
12 12 11 13 11 13 12
13 12 12 11 11 11 11
13 13 10 10 13 11 12
8 3 4
7 6
4 3 3 2 2 3 2
2 5 2 2 2 3 3
2 1 2 2 3 2 2
4 3 3 2 2 4 1
3 1 4 3 2 3 1
2 2 3 3 0 3 4
10 3 4
7 6
3 3 1 2 2 1 0
2 2 2 4 2 2 5
2 2 1 3 0 2 2
2 2 1 3 3 4 2
3 4 4 3 1 1 3
1 2 2 4 2 2 1
Output
12 5 1 8
Goodbye cruel world!
5 1 4 2
Just use Dijkstra's algorithm, using the implicit graph in the cardinal directions. Using the heap implementation it will be O(V log V), which should be good enough for 500x500. The first time you relax a node, it is with the lowest energy used you can get there. You can set up a node's precessor fairly trivially with this algorithm.
Edit: some pseudo code with explanation for Dijkstra's algorithm:
function Dijkstra( graph, source ):
// distance is infinity to everywhere initially
dist = initialize list of size V to infinity
// no vertices pointed to anything
previous = initialize list of size V to undefined
// distance from source to source is 0
dist[source] = 0
Q = priority queue
insert all vertices into Q
while Q is not empty:
// get the vertex closest to the source
current_vertex = Q.pop
if dist[current_vertex] == infinity
break
// these are the adjacent vertices in the four cardinal direction
for each vertex next to current_vertex:
// if it costs less energy to go to vertex
// from current_vertex
if ( dist[current_vertex] + energy[vertex] < dist[vertex] )
dist[vertex] = dist[current_vertex] + energy[vertex]
previous[vertex] = current_vertex
// Another if statement here to
// minimize steps if energy is the same
// Now after this is done, you should have the cheapest cost to
// each vertex in "dist". Take the cheapest one on the edge.
// You can walk backwards on the "previous" to reconstruct the path taken.
That's the general pseudo code, though you would also have to keep track of the number of steps, mostly as a tiebreaker, so it shouldn't be too much more work.
As for the DFS solution, it depends on what the energy can be. If it is bounded, small, and an int, you can convert the 2D graph into a 3D graph on x-y-e, where e is the energy remaining - you start at the initial energy, and work your way down, but keeping track of places you've been before.
Edit: For the DFS solution, it should be O(H*W*E), for E <= 30000, H, W <= 500 it will not likely be fast enough, at least for real time, and might take a bit of memory.
这篇关于GRAPH：找到一种算法来确定矩形迷宫中从一个点到另一个点的最短路径？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
