README

PathFinder是一个独立库，旨在用PHP实现著名的路径和路线查找算法，以解决诸如以下经典问题：

• SSP：最短路径问题
• TSP：旅行商问题

功能

• 距离：Chebyshev，欧几里得，曼哈顿，八边形，零

• SSP解决算法：AStar，Dijkstra，FloydWarshall

• TSP解决算法：NearestNeighbour，2Opt，3Opt

路线图

• 新的SSP解决算法：Kruskal MooreBellmanFord Prim 或其他

• 新的TSP解决算法：Christofides，kOpt，LinKernighan 或其他

• 速度优化

• 欢迎建议和贡献

类

核心类

• 启发式：一个具有浮动权重的距离。
• 节点：在NodeGrid、NodeGraph、NodeMap或NodePath中使用的节点实体，基本上是一对坐标（x, y）或索引（i,j）
• NodeGraph：一个图是一组通过边连接的顶点。在这里，顶点是节点，任何两个节点都可以通过具有浮动值的边连接。默认情况下，图是对称的，所以从顶点A到顶点B以及相反方向的边具有相同的值。
• NodeGrid：只是一个节点矩阵，使用以下模式使用坐标（x, y）或索引（i,j）

    .--------------> j (width) coord y
    | 1,1 1,2 1,3
    | 2,1 2,2 2,3
    | 3,1 ...
    |
    i (height) coord x

• NodeMap：一个将节点（作为键）映射到对象（作为值）的映射或字典，该对象可以是节点、布尔值等。
• NodePath：一系列连续节点的链表，形成路径

算法类

• ShortestDistance\Dijkstra：使用Dijkstra算法计算最短距离
• ShortestDistance\FloydWarshall：使用FloydWarshall算法计算最短距离
• ShortestPath\AStar：使用AStar算法计算最短路径
• ShortestPath\Dijkstra：使用Dijkstra算法计算最短路径
• TravelingSalesman\NearestNeighbour：使用NearestNeighbour算法计算最短行程
• TravelingSalesman\ThreeOpt：使用ThreeOpt算法改进最短行程
• TravelingSalesman\TwoOpt：使用TwoOpt算法改进最短行程

转换器类

• Grid\ASCIISyntax：允许将具有ASCII语法的地图转换为NodeMap、NodePath、Node对象等，反之亦然

距离类别

• 切比雪夫距离：计算两个节点之间的切比雪夫距离，即 max(|dx|, |dy|)
• 欧几里得距离：计算两个节点之间的欧几里得距离，即 sqrt(|dx|^2 + |dy|^2)
• 曼哈顿距离：计算两个节点之间的曼哈顿距离，即 |dx| + |dy|
• 八分位距离：计算两个节点之间的八分位距离，当 |dx| < |dy| 时为 (sqrt(2) - 1) * |dx| + |dy|，否则为 (sqrt(2) - 1) * |dy| + |dx|
• 零距离：计算两个节点 A 和 B 之间的零或零距离，总是为 0

示例

地图的 ASCII 语法

• 路径: '.'
• 源: '>'
• 目标: '<'
• 墙壁: 'X'

SSP 解决方案

    require __DIR__ . '/vendor/autoload.php';
    
    use Letournel\PathFinder\Algorithms;
    use Letournel\PathFinder\Converters\Grid\ASCIISyntax;
    use Letournel\PathFinder\Core;
    use Letournel\PathFinder\Distances;
    
    function solve($map, $algorithm)
    {
        $converter = new ASCIISyntax();
        $grid = $converter->convertToGrid($map);
        $matrix = $converter->convertToMatrix($map);
        $source = $converter->findAndCreateNode($matrix, ASCIISyntax::IN);
        $target = $converter->findAndCreateNode($matrix, ASCIISyntax::OUT);
        
        $algorithm->setGrid($grid);
        $starttime = microtime(true);
        $path = $algorithm->computePath($source, $target);
        $endtime = microtime(true);
        
        if($path instanceof Core\NodePath)
        {
            echo "Path found in " . floor(($endtime - $starttime) * 1000) . " ms\n";
            echo $converter->convertToSyntaxWithPath($grid, $path);
        }
        else
        {
            echo "No path found\n";
        }
    }
    
    $map =
        '                ' . "\n" .
        '.XXXXXX XXXXXXXX' . "\n" .
        ' X   XX<X  X    ' . "\n" .
        ' X X  XXX X   X ' . "\n" .
        '   X           >' . "\n" ;
    
    $distance = new Distances\Euclidean();
    $heuristic = new Core\Heuristic(new Distances\Euclidean(), 1);
    
    echo "Solving SSP with AStar:\n";
    solve($map, new Algorithms\ShortestPath\AStar($distance, $heuristic));
    echo "\n\n\n";
    
    echo "Solving SSP with Dijkstra:\n";
    solve($map, new Algorithms\ShortestPath\Dijkstra($distance));
    echo "\n\n\n";

安装

使用 composer

{
    "require": {
        "letournel/path-finder" : "~1.0"
    }
}

法律

Letournel/PathFinder 版权所有(c) 2015 Letournel

代码在 MIT 许可下发布