java - 递归(完成)

Question

我编写了这个应该有效的路径查找算法，但我收到了大量的 java.lang.ArrayIndexOutOfBoundsException。该程序的目标是找到从一点到另一点成本最低的最短路径。这是我的代码:

public boolean travel(int[][] path, int cX, int cY, int eX, int eY)
{
    boolean returned = false;
    System.out.println("the current X position on the GRID is: "+cX+"the current y position on the GRID is: "+cY);
    path[cX][cY]=1;
    if(cost>lowestCost - grid[cX][cY]){ 
        return false;
    }
    cost += grid[cX][cY];
    if(cX>=eX && cY>=eY){
        return true;
    }
    if(cX+1>=eX && cY+1<eY){
        return false;
    }
    if(cY+1>=eY && cX+1<eX){
        return false;
    }
    if(travel(path,cX+1,cY+1,eX,eY)==true){
        returned=true;
        replace(newBest, path);
    }
    if(travel(path,cX,cY+1,eX,eY)==true){
        returned=true;
        replace(newBest, path);
    }
    if(travel(path,cX+1,cY,eX,eY)==true){
        returned=true;
        replace(newBest, path);
    }


    return(returned);

}

cX 是数组中的当前 X 位置，cY 是数组中当前的 Y 位置，eX 和 eY 是目标坐标。 path[][] 是用来存放路径的数组。如果您有任何答案，请告诉我!也不建议任何其他算法，只是对实际代码进行一些编辑。 grid[][] 是存储从一个到另一个的成本的数组。非常感谢

 if(travel(newBest,0,0,rows,columns)==true)
                {
                    lowestCost=cost;
                }

这就是我如何调用查找最短路径的方法。

这是整个小程序:

import java.applet.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;
public class GridWorld extends Applet implements Runnable, MouseListener, KeyListener,     MouseMotionListener
{
public int worldx;
public int worldy;
public int columns;
public int rows;
public int destX, destY;
public int cost, lowestCost;
public boolean sizeD;
public int[][] grid;

public int[][] prevBest;

public int[][] newBest;


Graphics bufferGraphics; //Set up double buffer
Image offscreen;
Thread thread;//Sets up a Thread called thread

public void init()
{
    worldx=1000;
    worldy=1000;
    cost=0;
    lowestCost=5000;
    sizeD=false;
    columns=5;
    rows=5;
    destX=0;
    destY=0;
    grid= new int[rows][columns];
    prevBest= new int[rows][columns];
    newBest = new int[rows][columns];



    offscreen = createImage(worldx,worldy); //create a new image that's the size of the applet DOUBLE BUFFER SET UP
    bufferGraphics = offscreen.getGraphics(); //set bufferGraphics to the graphics of the offscreen image. DOUBLE BUFFER SET UP

    addKeyListener(this);//setup all the listeners
    addMouseListener(this);//setup all the listeners
    addMouseMotionListener(this);//setup all the listeners
    thread = new Thread(this);  //constructs a new thread
    thread.start();             //starts the thread
}//init()
public void fillGrid()
{
    prevBest= new int[rows][columns];
    newBest = new int[rows][columns];
    lowestCost = 0;
    for(int ro = 0;ro<rows;ro++)
    {
        for(int col = 0;col<columns;col++)
        {
                grid[ro][col]=(int)(Math.random()*100);
                newBest[ro][col]=0;
                prevBest[ro][col]=0;
                if(ro==col)
                {
                    prevBest[ro][col]=1;
                    lowestCost+=grid[ro][col];


                }
        }
    }

    destX=(rows-1);
    destY=(columns-1);
}
public boolean baseCase(int ct, int lowct, int destR, int destC, int cX, int cY)
{
    boolean returned=false;
    if(ct>=lowct)
    {
        returned=true;
    }
    if(cX+1==rows)
    {
        returned=true;
    }
    if(cY+1==columns)
    {
        returned=true;
    }
    if(cX==destR && cY==destC)
    {
        returned=true;
    }

    return(returned);
}
public boolean isValid(int x, int y, int[][] path, int eX, int eY) {
    //not valid if: cordinates are into grid dimensions
   if (!((x >= 0 && x < grid.length) && (y >= 0 && y < grid.length)))
       return false;
   //valid if: not visited yet, or is destiny
   if (path[x][y] == 0 || (x == eX && y == eY))
       return true;

   return true;
}
/*public int traverse(int steps, int destR, int destC, int curX, int curY)
{
    int direction = 0;
    if(cost>=lowestCost)
    {
        //System.out.println("Greater cost Base Case");
        direction=4;
    }
    if(curX+1>=destR && curY+1<destC)
    {
        System.out.println("Reached the farthest row Base Case");
        direction=1;
    }
    if(curY+1>=destC && curY+1<destR)
    {
        System.out.println("Reached the farthest columns Base Case");
        direction=2;
    }
    if(curX+1>=destR && curY+1>=destC)
    {
        System.out.println("At destination Base Case");
        direction=4;    
    }
    switch(direction)
    {
        case 0: newBest[curX][curY]=1;
                cost+=grid[curX][curY];
                System.out.println("the current X position on the GRID is: "+curX+"the current y position on the GRID is: "+curY);
                return(traverse(steps+1,destR,destC,curX+1,curY+1)); //diag

        case 1: newBest[curX][curY]=1;
                cost+=grid[curX][curY];
                return(traverse(steps+1,destR,destC,curX,curY+1)); //right

        case 2: newBest[curX][curY]=1;
                cost+=grid[curX][curY];
                return(traverse(steps+1,destR,destC,curX+1,curY));//down

        case 3: 
                return(5000);

        case 4: System.out.println("the Grid's cost is: "+cost);
                return(cost);
        default: return(0);

    }
}*/

 public int[][] replace(int[][] p1, int[][] p2)
 {
    for(int col=0;col<columns;col++)
        {
            for(int ro=0;ro<rows;ro++)
            {
                p1[ro][col]=p2[ro][col];
            }
        }
    return(p1);
 }
public boolean travel(int[][] path, int cX, int cY, int eX, int eY)
{
    boolean returned = false;
    System.out.println("cX: "+ cX+" , cY: "+ cY+", eX: "+eX+", eY: " +eY+" Path 1 length: "+path[0].length+" Path 2 length: "+path[1].length);
    path[cX][cY]=1;
    if(cost>lowestCost - grid[cX][cY]){ 
        System.out.println("1");
        return false;
    }
    cost += grid[cX][cY];

    }
    if(travel(path,cX+1,cY+1,eX,eY)==true && isValid(cX+1,cY+1,newBest,eX,eY)){
        System.out.println("the current X position on the GRID is: "+cX+"the current y position on the GRID is: "+cY);
        returned=true;
        replace(newBest, path);
    }
    if(travel(path,cX,cY+1,eX,eY)==true && isValid(cX,cY+1,newBest,eX,eY)){
        System.out.println("the current X position on the GRID is: "+cX+"the current y position on the GRID is: "+cY);

        returned=true;
        replace(newBest, path);
    }
    if(travel(path,cX+1,cY,eX,eY)==true && isValid(cX+1,cY,newBest,eX,eY)){
        System.out.println("the current X position on the GRID is: "+cX+"the current y position on the GRID is: "+cY);

        returned=true;
        replace(newBest, path);
    }


    return(returned);

}

public void paint(Graphics g) 
{// paint() is used to display things on the screen
    setSize(worldx,worldy);
    //clear the offscreen image
    bufferGraphics.clearRect(0,0,worldx,worldy);
    bufferGraphics.setColor(Color.black);
    //bufferGraphics.fillRect(0,0,worldx,worldy);

    if(sizeD==true)
    {
        if(travel(newBest,0,0,rows,columns)==true)
                {
                    lowestCost=cost;
                }
    }
    for(int ro = 0;ro<rows;ro++)
    {
        for(int col = 0;col<columns;col++)
        {
            if(sizeD==true)
            {

                if(newBest[ro][col]==1)
                {
                    bufferGraphics.setColor(Color.red);
                    bufferGraphics.fillRect((50*col),(50*ro),50,50);
                    bufferGraphics.setColor(Color.black);
                }
                if(prevBest[ro][col]==1)
                {
                    bufferGraphics.setColor(Color.gray);
                    bufferGraphics.fillRect((50*col),(50*ro),50,50);
                    bufferGraphics.setColor(Color.black);
                }

                bufferGraphics.drawLine(0,(50*ro),50*columns,(50*ro));
                bufferGraphics.drawLine((50*col),0,(50*col),50*rows);
                bufferGraphics.drawString(""+grid[ro][col],(50*ro)+25,(50*col)+25);



            }

        }
    }

    if(sizeD==false)
    {
        bufferGraphics.drawRect(200,300,100,100);
        bufferGraphics.drawString("5",250,350);
        bufferGraphics.drawRect(400,300,100,100);
        bufferGraphics.drawString("10",450,350);
        bufferGraphics.drawRect(600,300,100,100);
        bufferGraphics.drawString("20",650,350);
    }


    g.drawImage(offscreen,0,0,worldx,worldy,this);//Draw the screen
}// paint()

public void mouseDragged(MouseEvent e) {

}
public void mouseMoved(MouseEvent e){

}
public void mousePressed(MouseEvent e) 
{

}
public void mouseReleased(MouseEvent e) 
{

}
public void mouseEntered(MouseEvent e) 
{
   System.out.println("Mouse entered");
}
public void mouseExited(MouseEvent e) 
{
   System.out.println("Mouse exited");
}
public void mouseClicked(MouseEvent e) 
{
   System.out.println("Mouse clicked (# of clicks: "+ e.getClickCount() + ")");
   int mX=e.getX();
   int mY=e.getY();
   if(new Rectangle(200,300,100,100).contains(mX,mY) && sizeD==false)
   {
    columns=5;
    rows=5;
    grid= new int[rows][columns];
    fillGrid();
    sizeD=true;
   }
   if(new Rectangle(400,300,100,100).contains(mX,mY) && sizeD==false)
   {
    columns=10;
    rows=10;
    grid= new int[rows][columns];
    fillGrid();
    sizeD=true;

   }
   if(new Rectangle(600,300,100,100).contains(mX,mY) && sizeD==false)
   {
    columns=20;
    rows=20;
    grid= new int[rows][columns];
    fillGrid();
    sizeD=true;
   }

}
public void keyPressed( KeyEvent event ) 
{
    String keyin; // define a non‐public variable to hold the string representing the key input
    keyin = ""+event.getKeyText( event.getKeyCode()); 
    System.out.println("Key pressed "+keyin);
}//keyPressed()
public void keyReleased( KeyEvent event ) 
{
    String keyin;
    keyin = ""+event.getKeyText( event.getKeyCode()); 
    System.out.println ("Key released: "+ keyin);
}//keyReleased()
public void keyTyped( KeyEvent event ) 
{
 char keyin;
keyin = event.getKeyChar(); //getKeyChar() returns the character of the printable key pressed. 
System.out.println ("Key Typed: "+ keyin);
}//keyTyped()
public void update (Graphics g) 
{
    paint(g); 
}//Update the graphics

public void run() 
{
    while(true) // this thread loop forever and runs the paint method and then sleeps.
    {

        repaint();
        try {
        thread.sleep(50);
        }
        catch (Exception e){ }
    }//while
}// run()

}//小程序

Answer 1

您将获得大量 java.lang.ArrayIndexOutOfBoundsException因为您没有正确管理进入最后三个 if block 的流程。代码将进入最后三个 if block ，因为您只返回 return(returned); 处的状态。即使您设置了边界检查(前两个 if block )。所以，path[cX][cY]和 grid[cX][cY]当cX和cY为较大值时(取决于路径和网格的索引设置)，可能会遇到索引越界。

此外，前四个 if block 的检查逻辑顺序不正确，您应该在条件满足时返回状态。

前四个 if block 应重新排列为:

if(cost>=lowestCost){ 
    return false;
}
if(cX==eX && cY==eY){
    return true;
}
if(cX+1>=eX && cY+1<eY){
    return false;
}
if(cY+1>=eY && cX+1<eX){
    return false;
}

顺便说一句，请确保您的边界检查(cX+1>=eX && cY+1<eY 和 cY+1>=eY && cX+1<eX)是正确的。这将使代码无法访问 ([eX-1,eX],[0,eY-2]) 中的点和 ([0,eX-2],[eY-1,eY]) .

还有一点，cost>=lowestCost可能会惹上麻烦对于极少数情况，例如所有可能的最短路径的成本都等于最低成本的预设值。处理此问题的一种方法是删除等号。

再来一次，你可能会遇到 cost>=lowestCost 的麻烦对于像 cost = Integer.MAX_VALUE + 1 这样的极端情况.要处理这个问题，您可以尝试

if(cost>lowestCost - grid[cX][cY]){ 
    return false;
}
cost += grid[cX][cY];