PHP Classes
elePHPant
Icontem

File: example.mst.php

Recommend this page to a friend!
  Classes of Ken Schick  >  Christofides heuristic  >  example.mst.php  >  Download  
File: example.mst.php
Role: Example script
Content type: text/plain
Description: Example class
Class: Christofides heuristic
Solve salesman travel with Christofides heuristic
Author: By
Last change:
Date: 8 years ago
Size: 2,732 bytes
 

 

Contents

Class file image Download
<?php
/***************************************************************
* Copyright notice
*
* (c) 2010-2011 Chi Hoang (info@chihoang.de)
* All rights reserved
*
* The above copyright notice and this permission notice shall be included
* in all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
* OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
* DEALINGS IN THE SOFTWARE.
*
* Permission is hereby granted, free of charge, to any person obtaining a
* copy of this software and associated documentation files (the "Software"),
* to deal in the Software without restriction, including without limitation
* the rights to use, copy, modify, merge, publish, distribute, sublicense,
* and/or sell copies of the Software, and to permit persons to whom the
* Software is furnished to do so, subject to the following conditions:
*
* Free for non-commercial use
****************************************************************/

require_once ( "mst.php" );

$example_3 = Array ( 1 => Array ( 1, 2, 3, 8, 7 ),
                     
2 => Array ( 1, 3 ),
                     
3 => Array ( 1, 2, 4, 7 ),
                     
4 => Array ( 3, 7, 9, 5 ),
                     
5 => Array ( 4, 9 ),
                     
6 => Array ( 7, 9 ),
                     
7 => Array ( 1, 3, 4, 6, 8, 9 ),
                     
8 => Array ( 1, 7 ),
                     
9 => Array ( 4, 5, 6, 7 ),
                  );
                 
$example_2 = Array ( 1 => Array ( 2, 3 ),
                   
2 => Array ( 1,3,4,5 ),
                   
3 => Array ( 1,2,4,5 ),
                   
4 => Array ( 2,3,5 ),
                   
5 => Array ( 2,3,4 )
                );

$example_1 = Array (
                   
1 => Array ( 2, 3, 4, 5 ),
                   
2 => Array ( 1,4 ),
                   
3 => Array ( 1,4,5, 6 ),
                   
4 => Array ( 1,2,3, 6 ),
                   
5 => Array ( 1, 3 ),
                   
6 => Array ( 3, 4 )
                );
               
$test = new mst ( );
$test->example ( );
$test->prim ( );
$test->pickPrimTree ( );
$test->makePMTree ( $test->mst );
$test->getWayStr ( 0 );
$pm = $test->pmatch ( $test->wayStr );
$test->addmatch ( $test->mst, $pm [ 1 ] );
$start = $test->eulerCircuit ( $test->mst );
$path = $test->FindEulerCircuit ( $start );
$path = $test->HamiltonianPath ( $path );
$sum = $test->sumPath ( $path );
echo
"2.0x MST: " . $doubleMST = $test->total * 2 . " km \n";
echo
"1.5x MST: " . $sum . " km \n";
echo
"Error in percent: " . substr ( ( ( $sum - $doubleMST ) / $sum ) * 100 , 0, 2 )." %\n";
echo
"Travelsalesman route: " . implode (", ", $path ) ."\n";
?>