TSP brute force and nearest neighbour in PHP

brute_force.txt

[2013-12-12 08:51:40] start BruteForceTSP
best so far: 4918.6049886512, atempt: 1
Path: (443, 511)->(471, 124)->(10, 774)->(88, 600)->(518, 322)->(292, 171)->(995, 423)->(14, 374)->(697, 153)->(422, 301)
....
best so far: 2384.6557454024, atempt: 341178
Path: (443, 511)->(422, 301)->(518, 322)->(995, 423)->(697, 153)->(471, 124)->(292, 171)->(14, 374)->(88, 600)->(10, 774)
[2013-12-12 08:52:17] end BruteForceTSP

--------

Score: 2384.6557454024
Path: (443, 511)->(422, 301)->(518, 322)->(995, 423)->(697, 153)->(471, 124)->(292, 171)->(14, 374)->(88, 600)->(10, 774)
Swog: 
new 1100,1100 
string 20,20 {Andres Viikmaa, BruteForceTSP. Score: 2384.6557454024 } :tekst
coordsys west south right up
origin 50,50
fcircle 443,511 3 :p1
fcircle 422,301 3 :p2
fcircle 518,322 3 :p3
fcircle 995,423 3 :p4
fcircle 697,153 3 :p5
fcircle 471,124 3 :p6
fcircle 292,171 3 :p7
fcircle 14,374 3 :p8
fcircle 88,600 3 :p9
fcircle 10,774 3 :p10
# insert here your solution instead of 1 2 3 ... 
line (p1) (p2)
line (p2) (p3)
line (p3) (p4)
line (p4) (p5)
line (p5) (p6)
line (p6) (p7)
line (p7) (p8)
line (p8) (p9)
line (p9) (p10)
line (p10) (p1)

nearest_neighbour_1000.txt

[2013-12-12 08:52:17] start NearestNeighbourTSP
[2013-12-12 08:52:17] end NearestNeighbourTSP
Score: 2771.2464987545
Path: (443, 511)->(518, 322)->(422, 301)->(471, 124)->(292, 171)->(14, 374)->(88, 600)->(10, 774)->(697, 153)->(995, 423)

Swog: 
new 1100,1100 
string 20,20 {Andres Viikmaa, NearestNeighbourTSP. Score: 2771.2464987545 } :tekst
coordsys west south right up
origin 50,50
fcircle 443,511 3 :p1
fcircle 518,322 3 :p2
fcircle 422,301 3 :p3
fcircle 471,124 3 :p4
fcircle 292,171 3 :p5
fcircle 14,374 3 :p6
fcircle 88,600 3 :p7
fcircle 10,774 3 :p8
fcircle 697,153 3 :p9
fcircle 995,423 3 :p10
# insert here your solution instead of 1 2 3 ... 
line (p1) (p2)
line (p2) (p3)
line (p3) (p4)
line (p4) (p5)
line (p5) (p6)
line (p6) (p7)
line (p7) (p8)
line (p8) (p9)
line (p9) (p10)
line (p10) (p1)

tsp.php

<?php

class TSP {
	protected $nodes;
	function getNextNode($from, $state) {
		$next = array_shift($this->nodes);
		return $next ? array($next, $state) : false;
	}
	function load($file) {
		$this->nodes = array_map(function($a) {return explode(' ', $a);}, file($file, FILE_IGNORE_NEW_LINES));
		array_shift($this->nodes);
	}
	function solve() {
		
		$answer = array();
		$next = null;
		while ($next = $this->getNextNode($next[0], $next[1])) {
			$answer[] = $next[0];
		}
		return $answer;
	}
	
	function getDistance($start, $end) {
		return sqrt(pow ($start[0] - $end[0],2) + pow($start[1] - $end[1],2));
	}
	
	function getScore($path) {
		$distance = 0;
		for ($i=1;$i<count($path); $i++) {
			$distance += $this->getDistance($path[$i], $path[$i-1]);
		}
		return $distance;
	}
	function getPath($path) {
		return implode('->', array_map(function ($a) {return "($a[0], $a[1])";}, $path));
	}
	
	function getSwog($path) {
		$score = $this->getScore($path);
		$method = get_class($this);
		$swog = <<<EOM
new 1100,1100 
string 20,20 {Andres Viikmaa, $method. Score: $score } :tekst
coordsys west south right up
origin 50,50

EOM;
		for($i=0;$i<count($path);$i++){
			$swog .= "fcircle ".$path[$i][0].",".$path[$i][1]." 3 :p".($i+1)."\r\n";
		}
		$swog .= "# insert here your solution instead of 1 2 3 ... \r\n";
		for($i=1; $i<count($path);$i++){
			$swog .= "line (p".($i).") (p".($i+1).")\r\n";
		}
		$swog .= "line (p".($i).") (p1)\r\n";
		return $swog;
	}
}

class BruteForceTSP extends TSP {
	protected $best = null;
	protected $bestScore = 1000000;
	protected $counter = 0;
	private function bruteForce($todo, $walked = array( )) {
		if (empty($todo)) {
			$this->analyze($walked);
		}  else {
			for ($i = 0; $i<count($todo); $i++) {
				$_todo = $todo;
				unset($_todo[$i]);
				//var_dump(array(array_values($_todo), array_merge($walked, array($todo[$i]))));
				$this->bruteForce(array_values($_todo), array_merge($walked, array($todo[$i])));
			}
		}
	}
	function analyze($nodes) {
		$score = $this->getScore($nodes);
		if ($score < $this->bestScore) {
			$this->bestScore = $score;
			$this->best = $nodes;
			echo "best so far: ".$this->bestScore.", atempt: ".(++$this->counter).PHP_EOL;
			echo "Path: ".$this->getPath($this->best).PHP_EOL.PHP_EOL;
			echo "Swog: ".PHP_EOL.$this->getSwog($this->best).PHP_EOL.PHP_EOL;

		}
	
	}
	function solve() {
		$first = array_shift($this->nodes);
		$this->bruteForce($this->nodes, array($first));
		return $this->best;
	}
	
}
class NearestNeighbourTSP extends TSP {
	function getNextNode($from, $state) {
		if ($from != null) {
			$t = $this;
			usort($this->nodes, function($a, $b) use($from, $t) {
				return $t->getDistance($from, $a) < $t->getDistance($from, $b) ? -1:1; 
			});
		};
		return TSP::getNextNode($from, $state);
	}
}
function runTsp($tsp, $file){
	$_tsp = new $tsp();
	$_tsp->load($file);
	echo "[".date("Y-m-d H:i:s")."] start $tsp".PHP_EOL;
	$path = $_tsp->solve();
	echo "[".date("Y-m-d H:i:s")."] end $tsp".PHP_EOL;
	echo "Score: ".$_tsp->getScore($path).PHP_EOL;
	echo "Path: ".$_tsp->getPath($path).PHP_EOL.PHP_EOL;
	echo "Swog: ".PHP_EOL.$_tsp->getSwog($path).PHP_EOL.PHP_EOL;
}

runTSP('TSP', 'TSP_10.txt');
runTSP('BruteForceTSP', 'TSP_10.txt');
runTSP('NearestNeighbourTSP', 'TSP_10.txt');