newhamiton.java

计算机算法程序

package liu;
//汉密尔顿回路的非递归算法
//经过测试，17个节点需36s，18个节点就需一分钟以上
import java.util.Arrays;
import java.util.Date;
import java.util.Random;

import javax.swing.JOptionPane;

public class NewHamiton {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
       int top = 1,pmin ,Hsum = 0,size;
       // top 栈顶指针，size表示节点个数 
       // pmin记录当前路径的最小值
       // Hsum记录汉密尔顿路和
       int[] Path;//当前路径
       int[] Visited;//访问标志 1代表访问 0代表没访问
       int[] Stack;//设立栈
       long begin,end,time;//建立开始运行时间，结束时间
	   Date date1 = new Date();
	   begin = date1.getTime();
       
       String s = JOptionPane.showInputDialog("Please input the vexnumeber?");		
	   size  = Integer.parseInt(s); //输入节点个数
       
       Path = new int[size+1];
	   //Arrays.fill(Path, 0);//初始值设置为假；
	   Visited = new int[size+1];
	   Arrays.fill(Visited, 0);//开始节点都设为0
	   Stack = new int[size+1];//建立栈
	   int [][] m = new int [size+1][size+1];//存放边的长度
	   
	   pmin = size * 200;
	   Visited[1] = 1;//先访问节点1
	   Stack[1] = 1;
	   
	   Random rand = new Random();
	   for(int i=1;i<size+1 ;i++)  //对每一条边付值
			for(int j=i+1;j<size+1 ;j++){ //构造完全图
	          m[i][j] = rand.nextInt(10)+1;//随机生成边的权
			  m[j][i] = m[i][j];
			}
	   	  
	   top++;//刚开始把1入栈，栈顶元素就应该1
	   for(int j = 0; ;)
	   { 
		   j = j + 1;
		   if(j > size)  
		   { 
			   top = top -1;//出栈
			   if(top > 1) 
			   { 
				   j = Stack[top]; //栈顶元素保存j
				   Hsum = Hsum - m[Stack[top - 1]][j];//和减去对应的权值
				   Visited[j] = 0;//该节点的访问标志设为0
			   }
		   }
		   else if(Visited[j]==1) continue;//找到一个未访问的节点
		   else if(Hsum + m[Stack[top - 1]][j]>pmin) continue;//分支限定法
		   else 
		   { 
			   Stack[top] = j;//入栈
			   Hsum = Hsum + m[Stack[top - 1]][j];//加上到j节点的权
			   Visited[j] = 1;//访问标志至1
			   //top = top + 1;//栈顶指针向上移动
			   if(top<=size - 1) { top++;j = 0;} //继续入栈到最后一个元素
			   else
			   {   if(pmin >Hsum + m[j][1]) //找出最小回路
			       { 
				      pmin = Hsum + m[j][1];
				      for(int k = 1;k <= size;k++)
					     Path[k] = Stack[k];
			       }
			       top++;
			   }
			   
		   }
		 
		   if(top==1) break; //栈顶为1时，搜索结束，退出循环  
	   }
    
	Date date2 = new Date();
    end = date2.getTime();
	time = end - begin;
	System.out.println("计算所用的时间是："+time/1000+" s");
	   
	System.out.println("路线长度为："+pmin);
    System.out.println("路径为：");
    for(int i=1;i<size;i++)
    	System.out.print(Path[i]+"->("+m[Path[i]][Path[i + 1]]+")->");
	System.out.print(Path[size]+"->("+m[Path[size]][Path[1]]+")->"+Path[1]);
	}

}