java – GRAPH:找到一个算法来确定矩形迷宫中从一个点到另一个
我正在努力制定一个合适的算法,以便从迷宫中的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行),因此我们选择更好的一个. 考虑到这些,有人可以帮我一些代码或伪代码吗? 编辑: 拉里,正如我所说,我对代码有点困惑.这是我到目前为止所尝试的,只是为了确定最短的路径,从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,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,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,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,它不可能足够快,至少对于实时,并且可能需要一点记忆. (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |