java – GRAPH：找到一个算法来确定矩形迷宫中从一个点到另一个点的最短路径？
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了java – GRAPH：找到一个算法来确定矩形迷宫中从一个点到另一个点的最短路径？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含8407字，纯文字阅读大概需要13分钟。
内容图文
我正在努力制定一个合适的算法,以便从迷宫中的START位置转到EXIT位置.
值得一提的是,迷宫是矩形的,最大尺寸为500×500,理论上,DFS可以通过一些分支和绑定技术进行解析……
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
说明：
我们的经纪人每走一步就会失去能量,他只能向上,向下,向左和向右移动.此外,如果代理人的剩余能量为零或更少,他就会死亡,所以我们打印出类似“不可能”的东西.
因此,在输入10中是初始代理的能量,3 4是START位置(即第3列,第4行),我们有一个迷宫7×6.把它想象成一种迷宫,在这种迷宫中,我想找到一个让代理人有更好的剩余能量(最短路径)的出口.
如果存在导致相同剩余能量的路径,我们当然选择具有少量步骤的路径.
我需要知道在最坏的情况下DFS到迷宫500×500是否可行于这些限制以及如何操作,存储每个步骤中的剩余能量以及到目前为止所采取的步骤数.
输出意味着代理以剩余能量= 5到达出口位置4以两个步骤到达.如果我们仔细观察,在这个迷宫中,也可以以相同的能量但以3个步骤退出位置3 1(第3列,第1行),因此我们选择更好的一个.
考虑到这些,有人可以帮我一些代码或伪代码吗？
我在使用2D阵列时遇到麻烦,以及如何存储剩余的能量,路径(或采取的步骤数)….
编辑：
拉里,正如我所说,我对代码有点困惑.这是我到目前为止所尝试的,只是为了确定最短的路径,从START到EXIT的步数更少,同时修复EXIT ……
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();
}
}
输入：
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步.
有了我的想法,你的帮助,是否要求我指出我的失败或纠正它们？
我对此感到厌倦……因为我要让事情变得简单……
更多的输入/输出(当无法实现退出时(能量> 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
Output
12 5 1 8
Goodbye cruel world!
5 1 4 2
解决方法:
只需使用Dijkstra’s algorithm,使用主要方向的隐式图表.使用堆实现它将是O(V log V),对于500×500应该足够好.第一次放松节点时,它使用的能量最低,你可以到达那里.您可以使用此算法相当简单地设置节点的前驱.
编辑：一些伪代码,解释Dijkstra的算法：
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.
这是一般的伪代码,虽然你也必须跟踪步骤的数量,主要是作为决胜局,所以它不应该是太多的工作.
至于DFS解决方案,它取决于能量是多少.如果它是有界的,小的和一个int,你可以将2D图形转换为xye上的3D图形,其中e是剩余的能量 – 你从最初的能量开始,然后向下工作,但是跟踪你的位置曾经去过.
编辑：对于DFS解决方案,它应该是O(H * W * E),对于E <= 30000,H,W <= 500,它不可能足够快,至少对于实时,并且可能需要一点记忆.
内容总结
以上是互联网集市为您收集整理的java – GRAPH：找到一个算法来确定矩形迷宫中从一个点到另一个点的最短路径？全部内容，希望文章能够帮你解决java – GRAPH：找到一个算法来确定矩形迷宫中从一个点到另一个点的最短路径？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。