旅行商问题-A*算法-java

旅行商问题-A*算法-java

import java.awt.BasicStroke;
import java.awt.Color;
import java.awt.Container;
import java.awt.Font;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.Point;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

import javax.swing.Jframe;


public class Drawframe extends Jframe{
	private Map pointMap=new HashMap（）;
	public Drawframe（）{
		Container p = getContentPane（）;
        setBounds（100 100 1000 600）;
        setVisible（true）;
        setLayout（null）;   
        setResizable（false）;
        this.setDefaultCloseOperation（Jframe.EXIT_ON_CLOSE）;
	}
	public void paintCom（）{
		Graphics g=this.getGraphics（）;
		
		Graphics2D g2 = （Graphics2D）g;
		//Scanner input=new Scanner（System.in）;
		//0:A 1:B 2:C 3:D 4:E
		//int num=input.nextInt（）;
		int num=5;
		int[][] matrix=new int[num][num];
		matrix[0][1]=matrix[1][0]=6;
		matrix[1][2]=matrix[2][1]=6;
		matrix[0][4]=matrix[4][0]=7;
		matrix[0][2]=matrix[2][0]=1;
		matrix[0][3]=matrix[3][0]=5;
		matrix[1][3]=matrix[3][1]=4;
		matrix[1][4]=matrix[4][1]=3;
		matrix[2][3]=matrix[3][2]=8;
		matrix[2][4]=matrix[4][2]=2;
		matrix[3][4]=matrix[4][3]=5;
		int edgeNum=10;
		DrawSee ds=new DrawSee（nummatrix）;
		ds.paintMap（）;
		//open表
		List open=new ArrayList（）;
		//closed表
		List closed=new ArrayList（）;
		//wrong表 存放错误的路径
		Set> wrong=new HashSet>（）;
		//map表 存放每个节点的估价函数值
		Map map=new HashMap（）;
		//将A0起始节点放入map 估价函数为0
		map.put（“A0“ 0）;
		//将A0起始节点放入open表中
		open.add（“A0“）;
		while（true）{
			//从open表中取出最小估计函数值的节点，并从open表出删去
			String startString=open.get（0）;
			open.remove（0）;
			//将字母形式转为数字形式，放入closed表中，层数设为下一层
			char startchar=startString.charAt（0）;
			closed.add（startchar）;
			int start=startchar-‘A‘;
			int floor=startString.charAt（1）-‘0‘;
			
			if（!pointMap.containsKey（startString））{
				g2.fillOval（500100*floor+1001010）; //画实心圆
				pointMap.put（startString new Point（500100*floor+100））;
				g2.setFont（new Font（“宋体“Font.BOLD20））;
				g2.setColor（Color.RED）;
				g2.drawString（startString 500+10100*floor+100）;
			}
			
			
			floor++;
			//flag表示是否在此节点的下一层中找到可以拓展的节点
			boolean flag=true;
			for（int i=0;i				//前驱节点可以到达此节点时进行处理
				if（i!=start&&matrix[i][start]!=0）{
					char endchar=（char） （i+‘A‘）;
					//如果closed中已经存在此节点则继续寻找下一节点
					if（closed.contains（endchar））{
						continue;
					}
					//closed不存在此节点则加入closed中
					closed.add（endchar）;
					//如果加入该节点后，发现该路径存在于错误路径中，则继续寻找下一节点
					if（wrong.contains（closed））{
						closed.remove（closed.size（）-1）;
						continue;
					}
					closed.remove（closed.size（）-1）;
					flag=false;
					String endString=endchar+String.valueOf（floor）;
					try{
						Thread.sleep（2000）;
	

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        5778  2017-03-28 00:36  Drawframe.java
     文件        2653  2017-03-28 00:36  DrawSee.java
     文件         371  2017-03-28 08:01  Main.java