关于一个简单算法的优化？有请各位指教！！！

Question

如果只是如你所述，定位1的位置，x1,y1;81的位置x81,y81,
goto(x1,y1);
goto(x1,y81);
goto(x81,y81).

Answer 1

To hl_longman(寒山之松！):在这个程序中，1和81这两个格子的位置是固定的；从1必须要走完其余格子最后达81；To simonhappy() ( ) :怎么定位1，81的位置是无关紧要的，关键是怎样优化算法。
或者就算法本身的问题多多提点意见，不胜感激之至！

Answer 2

9*9 81个格子是固定的。
1和81的位置也是固定的。
那么楼主是不是想得有点过于复杂了？
1、人能不能走通？
if(不能){
  不用忙活了。
}
else{
  2、走通时转折的点和转向的方向加到一个列表里。
  3、开始走，到了转折点读取方向，继续走。
}

Answer 3

方格坐标(0-8)*(0-8),方向：U,D,L,R(上，下，左，右)转折点如下：
起点：(2,6)D
(2,7)L
(1,7)U
(1,5)R
(3,5)D
(3,8)L
(0,8)U
(0,4)R
(4,4)D
(4,8)R
(8,8)U
(8,7)L
(5,7)U
(5,6)R
(8,6)U
(8,5)L
(5,5)U
(5,4)R
(8,4)U
(8,2)L
(7,2)D
(7,3)L
(0,3)U
(0,0)R
(8,0)D
(8,1)L
(1,1)D
(1,2)R
终点：(6,2)
这是一个转折点序列。如果你只要走通，那么把这个硬编码进去就行了。如果你要动态的找出这样的序列，除了按这样的思路之外，可以考虑一下图的遍历问题。

Answer 4

楼主的意思应该是求一个通用的算法吧：
N*N的矩阵，从(x,y)不重复的走到(a,b)，求行走路线。
如果是用人的思维方式去解答，那就根本算不上是算法了。

Answer 5

To hq1305018(跃强):若预先知道您的转折点序列，这就不用在探讨这个问题了；怎样得到动态的转折点序列，这也是一个很好的问题？最终落实到一个问题：怎样进行图的遍历？To  kunchengking(Chinaren):堆栈的方法是很不错，再多点意见。另外，请各位以我前面提出的具体算法为基础多提点意见，谢谢。

Answer 6

package arithmetic;import java.util.Stack;/**
 * @author oz 2004-8-5
 */
public class SearchPath { private int HEIGHT = 9;
private int WIDTH = 9;
private boolean[][] mapMark = new boolean[HEIGHT][WIDTH];
private int[][] searchDirection = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};//上，右，下，左的搜索次序。 private int stepCount = 0;
private Point startPoint, endPoint;
private Stack stack = new Stack();
public SearchPath(int startx, int starty, int endx, int endy) {
startPoint = new Point(startx, starty);
endPoint = new Point(endx, endy);
} private class Point {
public int x, y;
public Point(int _x, int _y) {
x = _x;
y = _y;
}
public boolean equals(Object o) {
if (o instanceof Point) {
Point p = (Point) o;
return p.x == x && p.y == y;
}
return false;
}
public String toString() {
return "x:" + x + "\ty:" + y;
}
}
private boolean checkBound(Point p) {
return p.x >= 0 && p.x < WIDTH && p.y >= 0 && p.y < HEIGHT;
}
private boolean isValidPoint(Point p) {
//不允许越界；不允许是已经遍历过的点；不允许是起点，不是最后一步不允许是终点。
if (checkBound(p)) {
if (!mapMark[p.x][p.y]) {
if (!p.equals(startPoint)) {
if (p.equals(endPoint) && stepCount != HEIGHT * WIDTH - 2) {
return false;
} else {
return true;
}
}
}
}
return false;
}
private void forward(Point p) {
stack.push(p);
stepCount++;
mapMark[p.x][p.y] = true;
if (stepCount == HEIGHT * WIDTH - 1) {
throw new RuntimeException("gameover");
}
}
private void backward() {
Point p = (Point) stack.pop();
stepCount--;
mapMark[p.x][p.y] = false;
}
//递归移动
private void move(Point currentPoint) {
for (int i = 0; i < searchDirection.length; i++) {
currentPoint.x += searchDirection[i][0];
currentPoint.y += searchDirection[i][1];
if (isValidPoint(currentPoint)) {
forward(new Point(currentPoint.x, currentPoint.y));
move(currentPoint);
}
currentPoint.x -= searchDirection[i][0];
currentPoint.y -= searchDirection[i][1];
}
backward();
}
public void search() {
move(new Point(startPoint.x,startPoint.y));
}
public void print(){
int size = stack.size();
int[][] pr = new int[WIDTH][HEIGHT];
for(int i=0; i<size; i++){
Point p = (Point)stack.get(i);
pr[p.x][p.y] = i;
System.out.println(p);
}
for(int i=0; i<pr.length; i++){
for(int j=0; j<pr[i].length; j++){
System.out.print(pr[i][j]+"\t");
}
System.out.print("\r\n");
}
}
public static void main(String[] args) {
SearchPath s = new SearchPath(0, 0, 4, 4);
try {
s.search();
} catch (Exception e) {
e.printStackTrace();
s.print();
}
}}

Answer 7

多谢 simonhappy；回去试试。
另外可否请 simonhappy看看我的代码有何问题？

Answer 8

To simonhappy() :java中的递归最好采用static方法，否则效率极低，但即使这样，java处理递归还是要比C、C++低的很多，建议采用堆栈来模拟递归，这样效率才会有质的提高。

Answer 9

simonhappy的方法的确可以实现。但效率似乎也不是特别高，有何办法进行优化？

Answer 10

多谢simonhappy的指教，优化后的算法公告如下：执行java KnightNew 2 2 6 6 9所得到的结果大约6分钟。也许还有更好的办法，不使用Point类，直接建立数组实现。谢谢各位不断的关注，希望能得到大家更多的意见。
import java.util.*;
 
public class KnightNew{
  private int[][] position={{0,-1},{1,0},{0,1},{-1,0}};  //搜索方向依次按下右上左
 
  private int Height=2,Weight=2;
  
  private Point StartPoint,EndPoint;
  private int[][] go=null;//记录搜索次序
  private int stepCount = 1;
  private Vector list=new Vector();  
  
  KnightNew(int startX, int startY, int endX, int endY, int _size){
    StartPoint = new Point(startX,startY);
    EndPoint = new Point(endX,endY);
    Height = _size ;
    Weight = _size ;
    go =new int[Height][Weight];
    go[startX][startY]=1;
  }
 
  private class Point{
  public int x ,y;
  String direction="";
  Point(int x, int y){
    this.x=x;
    this.y=y;
  }
 
  public boolean equals(Object o){
    return (o instanceof Point)&&(this.x==((Point)o).x)&&(this.y==((Point)o).y);
  }
}
   //测试位置p是否可用，如果未曾访问过及其位置有效，返回True;否则为false
  private boolean test(Point p){
    if((p.x>=0)&&(p.x<Height)&&(p.y>=0)&&(p.y<Weight)){
      if(go[p.x][p.y]==0){
        if (p.equals(EndPoint) && stepCount != Height * Weight - 1) {
   return false;
 } else {
   return true;
 }        
      }
    } 
    return false;
  }
   public void search(){
  //初始化
  list.add(StartPoint);
  Point current=null;
  while(list.size()!=Height*Weight){
    if(list.size()==0){
      System.out.println("No solution!");
      System.exit(1);
    }
    current=(Point)(list.lastElement());
    if(current.direction.equals("0123")){
      stepCount--;
      go[current.x][current.y]=0;
      list.remove(list.lastElement());
      continue;
    }//处理回溯
        
    int i;
    for(i=0;i<=3;i++){      
      if(current.direction.indexOf(Integer.toString(i))!=-1)
        continue;
      Point next=new Point(current.x+position[i][0],current.y+position[i][1]);  
 
      if(test(next)){
        stepCount++;
        go[next.x][next.y]=stepCount;
        current.direction+=String.valueOf(i);
        list.add(next);
        break;
      }
      else{
        current.direction=current.direction+String.valueOf(i);        
        continue;
      }  
    }
  }
   for(int i=0;i<go.length;i++){
    for(int j=0;j<go[i].length;j++){
     System.out.print("\t"+go[j][go.length-1-i]);
    } 
    System.out.println("");
  }
} 
 
  public static void main(String[] args){
    GregorianCalendar c1 = new GregorianCalendar();
    c1.setTime(new Date());
 
    KnightNew k= new KnightNew(Integer.parseInt(args[0]),Integer.parseInt(args[1]),Integer.parseInt(args[2]),Integer.parseInt(args[3]),Integer.parseInt(args[4]));
    k.search();
    GregorianCalendar c2 = new GregorianCalendar();
    c2.setTime(new Date());
 
    long hours, minutes, seconds,timeInSeconds;
 
    timeInSeconds=(c2.getTime().getTime()-c1.getTime().getTime())/1000;
    hours = timeInSeconds / 3600;
    timeInSeconds = timeInSeconds - (hours * 3600);
    minutes = timeInSeconds / 60;
    timeInSeconds = timeInSeconds - (minutes * 60);
    seconds = timeInSeconds;
    System.out.println("Total time: "+hours + " hour(s) " + minutes + " minute(s) " + seconds + " second(s)");
  } 
}