如何在 PHP 中实现两个节点之间的最短路径的蚁群算法？

Question

我的目标是使用蚁群算法获得图中两个节点之间的最短路径及其长度。

假设我们有一个这样的图表：

$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 类，但无法完成它。

<?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 的示例。

Answer 1

有一个新的库，允许在 PHP 中使用蚁群优化来查找两个节点之间的最短路径