shellsorter.java

利用遗传算法解决TSP旅行商问题的Java原码

public class ShellSorter extends Sorter
{

	/**
	*method:getvalue()
	*param:
	*return: double
	*/
	private  double getvalue(CityMap[] cm)
	{
		//CityMap[] cm=new CityMap[GENE_NUMBER];
		//cm=citymap;
		double routevalue=0.0;
		double px,py,qx,qy;
		for (int i=0;i<cm.length-1;i++)
		{
			px=cm[i].getxpos();
			py=cm[i].getypos();
			qx=cm[i+1].getxpos();
			qy=cm[i+1].getypos();
			routevalue+=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
		}
		double first_end;
		px=cm[0].getxpos();
		py=cm[0].getypos();
		qx=cm[cm.length-1].getxpos();
		qy=cm[cm.length-1].getypos();
		first_end=Math.pow((Math.pow(qx-px,2.0)+Math.pow(qy-py,2.0)),0.5);
		return routevalue+first_end;

	}
	//

	public void Sort(Object []list,SortTool tool,boolean descending)
	{
		int inc,comp;
		if (descending)
		{
			comp=SortTool.COMP_GRTR;
		}
		else
		{
			comp=SortTool.COMP_LESS;
		}

		//
		for (inc=1;inc<=list.length/9;inc=3*inc+1);
		
		for (;inc>0;inc/=3)
		{
			for (int i=inc+1;i<=list.length;i+=inc)
			{
				CityMap[] t=(CityMap[])list[i-1];
				int j=i;
				while ((j>inc)&&(tool.compare(getvalue((CityMap[])list[j-inc-1]),getvalue(t))==comp))
				{
					list[j-1]=list[j-inc-1];
					j-=inc;
				}
				list[j-1]=t;
			}

		}
	}
};