喜迎
春节

PHP 解决最短路径问题

PHP 2D 最短路径
PHP
发布日期:   2024-12-24
文章字数:   592
阅读时长:   2 分

在二维地图上寻找从A点到B点的最短路径是一项常见的任务，通常可以使用图算法来解决。常用的算法包括广度优先搜索（BFS）、Dijkstra算法和A*算法。

使用广度优先搜索（BFS）算法寻找最短路径

广度优先搜索是一种简单而有效的算法，对于在无权图（即每条边的权重相同）中寻找最短路径非常适用。以下是在PHP中实现BFS算法的示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
<?php
class Point {
    public $x;
    public $y;

    public function __construct($x, $y) {
        $this->x = $x;
        $this->y = $y;
    }

    public function __toString() {
        return "($this->x, $this->y)";
    }
}

function bfs($map, $start, $end) {
    $rows = count($map);
    $cols = count($map[0]);
    $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // 右, 下, 左, 上
    $queue = new SplQueue();
    $queue->enqueue([$start, [$start]]); // 队列中存储当前点和路径
    $visited = [];

    while (!$queue->isEmpty()) {
        list($current, $path) = $queue->dequeue();
        $x = $current->x;
        $y = $current->y;

        if ($x == $end->x && $y == $end->y) {
            return $path; // 找到路径
        }

        foreach ($directions as $direction) {
            $newX = $x + $direction[0];
            $newY = $y + $direction[1];
            $newPoint = new Point($newX, $newY);

            if ($newX >= 0 && $newX < $rows && $newY >= 0 && $newY < $cols && $map[$newX][$newY] == 0 && !isset($visited["$newX,$newY"])) {
                $queue->enqueue([$newPoint, array_merge($path, [$newPoint])]);
                $visited["$newX,$newY"] = true;
            }
        }
    }
    return null; // 无路径
}

// 示例地图：0表示可以通行，1表示障碍物
$map = [
    [0, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0]
];

$start = new Point(0, 0);
$end = new Point(4, 4);

$path = bfs($map, $start, $end);

if ($path) {
    echo "Path found:\n";
    foreach ($path as $point) {
        echo $point . " ";
		// output: (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4) 
    }
} else {
    echo "No path found.";
}
?>

代码解释：

  • Point类：用于表示地图上的点。
  • bfs函数：实现广度优先搜索算法，接收地图、起点和终点作为参数，返回从起点到终点的路径。
  • directions数组：表示四个可能的移动方向（右、下、左、上）。
  • 队列（SplQueue）：用于存储当前点和路径。
  • visited数组：用于标记已访问的点，避免重复访问。

运行结果：

如果找到路径，程序将输出从起点到终点的路径。如果没有路径，则输出“无路径”。

总结：

广度优先搜索适用于在无权图中寻找最短路径。如果地图中有不同权重的边或者需要考虑效率，可以考虑使用Dijkstra算法或A*算法。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/php-2d-shortest-route.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 2D 最短路径
赏
评 论
 上一篇
PHP 解决旅行商问题
PHP 解决旅行商问题
如果需要在二维地图上找到一条路径，使得从起点到终点经过所有有奖励的点，并且路径最短，可以考虑使用图搜索算法如A*算法或Dijkstra算法的变种。这类问题通常称为“旅行商问题”（TSP, Traveling Salesman Problem
2024-12-24 PHP
PHP 2D 旅行商问题 最短路径
下一篇 
PHP SplQueue 类使用指南
PHP SplQueue 类使用指南
什么是 SplQueue？SplQueue 是 PHP 标准库 (SPL) 提供的一个类，用于实现队列这种数据结构。队列遵循先进先出的原则（FIFO：First In, First Out），即先进入队列的元素会先被取出。 为什么使用 Sp
2024-12-23 PHP
PHP SplQueue
PHP 2D 最短路径
PHP
发布日期:   2024-12-24
文章字数:   592
阅读时长:   2 分

在二维地图上寻找从A点到B点的最短路径是一项常见的任务，通常可以使用图算法来解决。常用的算法包括广度优先搜索（BFS）、Dijkstra算法和A*算法。

使用广度优先搜索（BFS）算法寻找最短路径

广度优先搜索是一种简单而有效的算法，对于在无权图（即每条边的权重相同）中寻找最短路径非常适用。以下是在PHP中实现BFS算法的示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
<?php
class Point {
    public $x;
    public $y;

    public function __construct($x, $y) {
        $this->x = $x;
        $this->y = $y;
    }

    public function __toString() {
        return "($this->x, $this->y)";
    }
}

function bfs($map, $start, $end) {
    $rows = count($map);
    $cols = count($map[0]);
    $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // 右, 下, 左, 上
    $queue = new SplQueue();
    $queue->enqueue([$start, [$start]]); // 队列中存储当前点和路径
    $visited = [];

    while (!$queue->isEmpty()) {
        list($current, $path) = $queue->dequeue();
        $x = $current->x;
        $y = $current->y;

        if ($x == $end->x && $y == $end->y) {
            return $path; // 找到路径
        }

        foreach ($directions as $direction) {
            $newX = $x + $direction[0];
            $newY = $y + $direction[1];
            $newPoint = new Point($newX, $newY);

            if ($newX >= 0 && $newX < $rows && $newY >= 0 && $newY < $cols && $map[$newX][$newY] == 0 && !isset($visited["$newX,$newY"])) {
                $queue->enqueue([$newPoint, array_merge($path, [$newPoint])]);
                $visited["$newX,$newY"] = true;
            }
        }
    }
    return null; // 无路径
}

// 示例地图：0表示可以通行，1表示障碍物
$map = [
    [0, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0]
];

$start = new Point(0, 0);
$end = new Point(4, 4);

$path = bfs($map, $start, $end);

if ($path) {
    echo "Path found:\n";
    foreach ($path as $point) {
        echo $point . " ";
		// output: (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4) 
    }
} else {
    echo "No path found.";
}
?>

代码解释：

  • Point类：用于表示地图上的点。
  • bfs函数：实现广度优先搜索算法，接收地图、起点和终点作为参数，返回从起点到终点的路径。
  • directions数组：表示四个可能的移动方向（右、下、左、上）。
  • 队列（SplQueue）：用于存储当前点和路径。
  • visited数组：用于标记已访问的点，避免重复访问。

运行结果：

如果找到路径，程序将输出从起点到终点的路径。如果没有路径，则输出“无路径”。

总结：

广度优先搜索适用于在无权图中寻找最短路径。如果地图中有不同权重的边或者需要考虑效率，可以考虑使用Dijkstra算法或A*算法。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/php-2d-shortest-route.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 2D 最短路径
赏
评 论
 上一篇
PHP 解决旅行商问题
PHP 解决旅行商问题
如果需要在二维地图上找到一条路径，使得从起点到终点经过所有有奖励的点，并且路径最短，可以考虑使用图搜索算法如A*算法或Dijkstra算法的变种。这类问题通常称为“旅行商问题”（TSP, Traveling Salesman Problem
2024-12-24 PHP
PHP 2D 旅行商问题 最短路径
下一篇 
PHP SplQueue 类使用指南
PHP SplQueue 类使用指南
什么是 SplQueue？SplQueue 是 PHP 标准库 (SPL) 提供的一个类，用于实现队列这种数据结构。队列遵循先进先出的原则（FIFO：First In, First Out），即先进入队列的元素会先被取出。 为什么使用 Sp
2024-12-23 PHP
PHP SplQueue
PHP 2D 最短路径
PHP
发布日期:   2024-12-24
文章字数:   592
阅读时长:   2 分

在二维地图上寻找从A点到B点的最短路径是一项常见的任务，通常可以使用图算法来解决。常用的算法包括广度优先搜索（BFS）、Dijkstra算法和A*算法。

使用广度优先搜索（BFS）算法寻找最短路径

广度优先搜索是一种简单而有效的算法，对于在无权图（即每条边的权重相同）中寻找最短路径非常适用。以下是在PHP中实现BFS算法的示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
<?php
class Point {
    public $x;
    public $y;

    public function __construct($x, $y) {
        $this->x = $x;
        $this->y = $y;
    }

    public function __toString() {
        return "($this->x, $this->y)";
    }
}

function bfs($map, $start, $end) {
    $rows = count($map);
    $cols = count($map[0]);
    $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // 右, 下, 左, 上
    $queue = new SplQueue();
    $queue->enqueue([$start, [$start]]); // 队列中存储当前点和路径
    $visited = [];

    while (!$queue->isEmpty()) {
        list($current, $path) = $queue->dequeue();
        $x = $current->x;
        $y = $current->y;

        if ($x == $end->x && $y == $end->y) {
            return $path; // 找到路径
        }

        foreach ($directions as $direction) {
            $newX = $x + $direction[0];
            $newY = $y + $direction[1];
            $newPoint = new Point($newX, $newY);

            if ($newX >= 0 && $newX < $rows && $newY >= 0 && $newY < $cols && $map[$newX][$newY] == 0 && !isset($visited["$newX,$newY"])) {
                $queue->enqueue([$newPoint, array_merge($path, [$newPoint])]);
                $visited["$newX,$newY"] = true;
            }
        }
    }
    return null; // 无路径
}

// 示例地图：0表示可以通行，1表示障碍物
$map = [
    [0, 0, 1, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 0, 0, 0]
];

$start = new Point(0, 0);
$end = new Point(4, 4);

$path = bfs($map, $start, $end);

if ($path) {
    echo "Path found:\n";
    foreach ($path as $point) {
        echo $point . " ";
		// output: (0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4) 
    }
} else {
    echo "No path found.";
}
?>

代码解释：

  • Point类：用于表示地图上的点。
  • bfs函数：实现广度优先搜索算法，接收地图、起点和终点作为参数，返回从起点到终点的路径。
  • directions数组：表示四个可能的移动方向（右、下、左、上）。
  • 队列（SplQueue）：用于存储当前点和路径。
  • visited数组：用于标记已访问的点，避免重复访问。

运行结果：

如果找到路径，程序将输出从起点到终点的路径。如果没有路径，则输出“无路径”。

总结：

广度优先搜索适用于在无权图中寻找最短路径。如果地图中有不同权重的边或者需要考虑效率，可以考虑使用Dijkstra算法或A*算法。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/php-2d-shortest-route.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 2D 最短路径
赏
评 论
 上一篇
PHP 解决旅行商问题
PHP 解决旅行商问题
如果需要在二维地图上找到一条路径，使得从起点到终点经过所有有奖励的点，并且路径最短，可以考虑使用图搜索算法如A*算法或Dijkstra算法的变种。这类问题通常称为“旅行商问题”（TSP, Traveling Salesman Problem
2024-12-24 PHP
PHP 2D 旅行商问题 最短路径
下一篇 
PHP SplQueue 类使用指南
PHP SplQueue 类使用指南
什么是 SplQueue？SplQueue 是 PHP 标准库 (SPL) 提供的一个类，用于实现队列这种数据结构。队列遵循先进先出的原则（FIFO：First In, First Out），即先进入队列的元素会先被取出。 为什么使用 Sp
2024-12-23 PHP
PHP SplQueue
  目录
  目录
  目录
hexo