Моя цель — получить кратчайший путь и его длину между двумя узлами в графе, используя алгоритм Ant Colony.
Допустим, у нас есть такой график:
$graph = array(
array(0,5,7,3,0),
array(5,0,4,0,0),
array(7,4,0,0,5),
array(3,0,0,0,4),
array(0,0,5,4,0),
);
И я хочу найти кратчайший путь от узла 0
в 5
$start = 0;
$finish = 5;
Цель выхода:
$shortest = [0, 4, 5]; // shortest path
$length = 7; // the path length
Что я сделал:
Я создал Ant Class, но я не могу закончить его.
<?php
// file: Ant.php
namespace Algoritma;
/**********************
| @AUTHOR: Ardianta Pargo <[email protected]>
| @DATE: 22 Juli 2017
*/
class Ant {
// the graph
private $graf = array(array());
// probability between cities/nodes
private $probabilitas = array(array());
// visited nodes
private $visitedNode = array();
// start node and finish node
private $start;
private $finish;
// current position of ant
private $currentPosition;
// tour length of ant
private $tourLength;
public function __construct($start, $finish, $graf){
$this->graf = $graf;
$this->start = $start;
$this->finish = $finish;
$this->currentPosition = $start;
}
public function depositFeromon(){
//...
}
public function move(){
//...
echo "Ant is moving...<br>";
// @TODO calculate probabality to city
// @TODO take random city by probability
// @TODO update current position
// @TODO call deposit pheromone
}
// Setter dan getter
public function setStart($start){
$this->start = $start;
}
public function getStart(){
return $this->start;
}
public function setFinish($finish){
$this->finish = $finish;
}
public function getFinish(){
return $this->finish;
}
public function setCurrentPosition($position){
$this->currentPosition = $position;
}
public function getCurrentPosition(){
return $this->currentPosition;
}
}
Я также создаю другой файл, чтобы проверить его класс:
<?php
include("Ant.php");
use Algoritma\Ant;
// the graph in matrix
$graf = array(
array(0,5,7,3,0),
array(5,0,4,0,0),
array(7,4,0,0,5),
array(3,0,0,0,4),
array(0,0,5,4,0),
);
// initial pheromone
$t0 = 0.01;
// pheromone array
$feromon = array(array());
// cities/nodes count
$n = count($graf);
// where to start and finish
$start = 0; // A
$finish = 5; // E
// tetapan siklus semut
$Q = 1;
// tetapan pengendali intensitas jejak semut
$alpha = 1.00;
// tetapan pengendali visibilitas
$beta = 1.00;
// tetapan penguapan jejak semut
$rho = 0.50;
// visibility
$visibilitas = array(array());
// ants count
$m = 4;
// jumlah siklus maksimal
$NCmax = 2;
$NC = 0;
// ------------------- INITIALIZE -----------------------------for($i = 0; $i < $n; $i++){
for($j = 0; $j < $n; $j++){
// initialize the pheromone
$feromon[$i][$j] = $t0;
if($graf[$i][$j] == 0){
$visibilitas[$i][$j] = 0;
} else {
// initialize the visibility
$visibilitas[$i][$j] = 1 / $graf[$i][$j];
}
}
}
do {
// create ant object
$semut[] = new Ant($start, $finish, $graf);
} while ( count($semut) < $m);// ------------------- ALGORITHM PROCESS -----------------------------while($NC < $NCmax){
// each ant now start moving...
foreach($semut as $ant){
$ant->move();
}
$NC++;
}
var_dump($visibilitas);
Я не знаю, что делать дальше.
Много примеров в интернете с использованием TSP.
Задача ещё не решена.
Других решений пока нет …