forked from: forked from: TSP 3D

TSP 3D
Original work by itatsu
Feb.4.2009
A simple, SA based TSP solver.
Press any key to reset
解法はシンプルなシミュレーテッドアニーリングですぅー

by angerfish 05 Feb 2009

Embed

// forked from keijiro's forked from: TSP 3D
// forked from itatsu's TSP 3D
// TSP 3D
// Original work by itatsu
// Feb.4.2009
// 
// A simple, SA based TSP solver.
// Press any key to reset
//
// 解法はシンプルなシミュレーテッドアニーリングですぅー

package {
	import flash.display.*;
	import flash.events.*;

	[SWF(width="465", height="465", backgroundColor="30", frameRate="60")]
	public class MyBots extends Sprite {
		public function MyBots() {
			global = this;
			global.x = 400;
			global.y = 400;

			stage.quality = StageQuality.HIGH;

			Initialize();

			global.addEventListener(Event.ENTER_FRAME, Update);
			stage.addEventListener(KeyboardEvent.KEY_DOWN, KeyDown);
		}
	}
}

import flash.display.*;
import flash.events.*;
import flash.geom.*;
import flash.text.*;
import flash.filters.*;

// Global
var global:Sprite;

// Rotation
var rX:Number = 0;
var rY:Number = -20 * Math.PI / 10;
var rZ:Number = 0;
var mat:Matrix3D = new Matrix3D();

// City vector
var city:Vector.<Vector3D> = new Vector.<Vector3D>();
// Present route
var route:Vector.<Vector3D> = new Vector.<Vector3D>();
// Best route
var broute:Vector.<Vector3D> = new Vector.<Vector3D>();
// Temprature
var t:Number;

// City amount
const am:int = 2;
// Initial temperature
const it:Number = 2;
// Step
const step:int = 1;
// Annealing rate
const arate:Number = 0.99;

// Textfield
var tField:TextField = new TextField;

function Initialize():void {
	city = new Vector.<Vector3D>();
	route = new Vector.<Vector3D>();
	broute = new Vector.<Vector3D>();
		
	// Generate cities
	for (var i:int = 0; i < am; i++) {
		var cit:Vector3D = new Vector3D((Math.random() - 0.5) * 300, (Math.random() - 0.5) * 300, (Math.random() - 0.5) * 300);
		city.push(cit);
		route.push(new Vector3D(cit.x, cit.y, cit.z));
		broute.push(new Vector3D(cit.x, cit.y, cit.z));
	}
	
	t = it;
	
	var tFormat:TextFormat = new TextFormat;
	tFormat.font = "Arial";
	tFormat.bold = false;
	tFormat.color = 0xffffff;
	tFormat.size = 25;
	tFormat.align = TextFormatAlign.LEFT;

	tField.defaultTextFormat = tFormat;
	tField.selectable = false;
	tField.x = -200;
	tField.y = -200;
	tField.width = 460;
	//tField.antiAliasType = AntiAliasType.ADVANCED;
	
	global.filters = [new GlowFilter(0xffffff, 0.7, 6, 6)];
}

function Update(evt:Event):void {	
	global.graphics.clear();
	while (global.numChildren > 0) {
		global.removeChildAt(0);
	}
	DrawRoute();
	
	global.addChild(tField);
	tField.text = String(Length(broute));
	
	// Rotate
	mat.appendRotation(rX, Vector3D.X_AXIS);
	mat.appendRotation(rY, Vector3D.Y_AXIS);
	mat.appendRotation(rZ, Vector3D.Z_AXIS);
	
	
	SA();
}

function SA():void {
	for (var i:int = 0; i < step; i++)
	{
		var br:Number = Length(broute);

		// INV
		var r2:Vector.<Vector3D> = RouteClone(route);

		var st:int = Math.floor(Math.random() * am);
		var ed:int = Math.floor(Math.random() * am);
		while (ed == st)
		{
			ed = Math.floor(Math.random() * am);
		}
		if (st > ed)
		{
			var temp:int = st;
			st = ed;
			ed = temp;
		}
		for (var j:int = st; j <= ed; j++)
		{
			var d:int = st + ed - j;
			r2[d] = new Vector3D(route[j].x, route[j].y, route[j].z);
		}
		var lr:Number = Length(route);
		var nw:Number = Length(r2);
		if (nw < br)
		{
			broute = RouteClone(r2);
		}
		if (Math.random() < Math.exp(-(nw - lr) / t))
		{
			route = RouteClone(r2);
		}
	}
	// Annealing
	t = t * 0.9;
}

function Length(r:Vector.<Vector3D>):Number {
	var s:Number = 0;
	for (var i:int = 0; i < am; i++)
	{
		var ii:int = (i + 1) % am;
		s += Math.sqrt((r[i].x - r[ii].x) * (r[i].x - r[ii].x)
		+ (r[i].y - r[ii].y) * (r[i].y - r[ii].y)
		+ (r[i].z - r[ii].z) * (r[i].z - r[ii].z));
	}
	return s;
}

function RouteClone(r:Vector.<Vector3D>):Vector.<Vector3D> {
	var r2:Vector.<Vector3D> = new Vector.<Vector3D>();
	for (var i:int = 0; i < am; i++) {
		r2.push(new Vector3D(r[i].x, r[i].y, r[i].z));
	}
	return r2;
}

function DrawRoute():void {
	for (var i:int = 0; i < am; i++) {
		var ii:int = (i + 1) % am;
		var st:Vector3D = mat.transformVector(broute[i]);
		var ed:Vector3D = mat.transformVector(broute[ii]);
		global.graphics.lineStyle(2, 0xffffff);
		global.graphics.moveTo(st.x, st.y);
		global.graphics.lineTo(ed.x, ed.y);
		
		global.graphics.drawCircle(st.x, st.y, 2200 / (380 - st.z));
	}
}

function KeyDown(evt:KeyboardEvent):void {
	//
	Initialize();
}