Как реализовать алгоритм Ant Colony для кратчайшего пути между двумя узлами в PHP?

Моя цель — получить кратчайший путь и его длину между двумя узлами в графе, используя алгоритм 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.

1

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]