喜迎
春节

PHP 解决旅行商问题

PHP 2D 旅行商问题 最短路径
PHP
发布日期:   2024-12-24
文章字数:   729
阅读时长:   3 分

如果需要在二维地图上找到一条路径，使得从起点到终点经过所有有奖励的点，并且路径最短，可以考虑使用图搜索算法如A*算法或Dijkstra算法的变种。这类问题通常称为“旅行商问题”（TSP, Traveling Salesman Problem），是一种经典的组合优化问题。

以下是使用A*算法的一个基本示例，你可以根据需要进行扩展，以包括所有奖励点。

示例地图（带奖励点）

假设地图如下：

  • 0 表示可以通行的空地。
  • 1 表示障碍物。
  • R 表示奖励点。
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
71
72
73
74
75
76
<?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 findShortestPath($map, $start, $end, $rewards) {
    $rows = count($map);
    $cols = count($map[0]);
    $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // 右, 下, 左, 上

    $queue = new SplPriorityQueue();
    $queue->insert([$start, [$start], 0], 0); // 队列中存储当前点、路径、已走步数
    $visited = [];

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

        if ($x == $end->x && $y == $end->y && empty($rewards)) {
            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] != 1 && !isset($visited["$newX,$newY"])) {
                $newCost = $cost + 1;
                $newRewards = array_filter($rewards, function($reward) use ($newPoint) {
                    return !($reward->x == $newPoint->x && $reward->y == $newPoint->y);
                });

                $queue->insert([$newPoint, array_merge($path, [$newPoint]), $newCost], -$newCost);
                $visited["$newX,$newY"] = true;
            }
        }
    }
    return null; // 无路径
}

// 示例地图：0表示可以通行，1表示障碍物，R表示奖励点
$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);
$rewards = [new Point(2, 2), new Point(3, 1)]; // 奖励点的坐标

$path = findShortestPath($map, $start, $end, $rewards);

if ($path) {
    echo "Path found:\n";
    foreach ($path as $point) {
        echo $point . " ";
    }
} else {
    echo "No path found.";
}
?>

代码解释：

  1. Point类：用于表示地图上的点。
  2. findShortestPath函数：实现了一个基本的优先队列搜索算法，接收地图、起点、终点和奖励点作为参数，返回从起点到终点经过所有奖励点的路径。
  3. directions数组：表示四个可能的移动方向（右、下、左、上）。
  4. 队列（SplPriorityQueue）：用于存储当前点、路径和已走步数，并按优先级排序。
  5. visited数组：用于标记已访问的点，避免重复访问。

运行结果：

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

总结：

这个示例中的算法实现了一个基本的优先队列搜索，并且在每次移动时检查是否经过奖励点。对于更复杂的地图和更多的奖励点，可以使用更高级的图搜索算法，如A*算法，并结合动态规划或其他优化技术。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/php-2d-tsp-solution.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 2D 旅行商问题 最短路径
赏
评 论
 上一篇
斐波那契堆：一种高效的优先队列
斐波那契堆：一种高效的优先队列
斐波那契堆是什么？斐波那契堆是一种特殊的堆数据结构，它在插入、删除最小值、合并等操作上具有非常优秀的均摊时间复杂度。与传统的二项堆相比，斐波那契堆在某些操作上表现得更加高效。 斐波那契堆的结构 最小堆的集合: 斐波那契堆实际上是一组最小堆的
2024-12-24 数据结构
heap 数据结构
下一篇 
PHP 解决最短路径问题
PHP 解决最短路径问题
在二维地图上寻找从A点到B点的最短路径是一项常见的任务，通常可以使用图算法来解决。常用的算法包括广度优先搜索（BFS）、Dijkstra算法和A*算法。 使用广度优先搜索（BFS）算法寻找最短路径广度优先搜索是一种简单而有效的算法，对于在无
2024-12-24 PHP
PHP 2D 最短路径
PHP 2D 旅行商问题 最短路径
PHP
发布日期:   2024-12-24
文章字数:   729
阅读时长:   3 分

如果需要在二维地图上找到一条路径，使得从起点到终点经过所有有奖励的点，并且路径最短，可以考虑使用图搜索算法如A*算法或Dijkstra算法的变种。这类问题通常称为“旅行商问题”（TSP, Traveling Salesman Problem），是一种经典的组合优化问题。

以下是使用A*算法的一个基本示例，你可以根据需要进行扩展，以包括所有奖励点。

示例地图（带奖励点）

假设地图如下：

  • 0 表示可以通行的空地。
  • 1 表示障碍物。
  • R 表示奖励点。
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
71
72
73
74
75
76
<?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 findShortestPath($map, $start, $end, $rewards) {
    $rows = count($map);
    $cols = count($map[0]);
    $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // 右, 下, 左, 上

    $queue = new SplPriorityQueue();
    $queue->insert([$start, [$start], 0], 0); // 队列中存储当前点、路径、已走步数
    $visited = [];

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

        if ($x == $end->x && $y == $end->y && empty($rewards)) {
            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] != 1 && !isset($visited["$newX,$newY"])) {
                $newCost = $cost + 1;
                $newRewards = array_filter($rewards, function($reward) use ($newPoint) {
                    return !($reward->x == $newPoint->x && $reward->y == $newPoint->y);
                });

                $queue->insert([$newPoint, array_merge($path, [$newPoint]), $newCost], -$newCost);
                $visited["$newX,$newY"] = true;
            }
        }
    }
    return null; // 无路径
}

// 示例地图：0表示可以通行，1表示障碍物，R表示奖励点
$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);
$rewards = [new Point(2, 2), new Point(3, 1)]; // 奖励点的坐标

$path = findShortestPath($map, $start, $end, $rewards);

if ($path) {
    echo "Path found:\n";
    foreach ($path as $point) {
        echo $point . " ";
    }
} else {
    echo "No path found.";
}
?>

代码解释：

  1. Point类：用于表示地图上的点。
  2. findShortestPath函数：实现了一个基本的优先队列搜索算法，接收地图、起点、终点和奖励点作为参数，返回从起点到终点经过所有奖励点的路径。
  3. directions数组：表示四个可能的移动方向（右、下、左、上）。
  4. 队列（SplPriorityQueue）：用于存储当前点、路径和已走步数，并按优先级排序。
  5. visited数组：用于标记已访问的点，避免重复访问。

运行结果：

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

总结：

这个示例中的算法实现了一个基本的优先队列搜索，并且在每次移动时检查是否经过奖励点。对于更复杂的地图和更多的奖励点，可以使用更高级的图搜索算法，如A*算法，并结合动态规划或其他优化技术。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/php-2d-tsp-solution.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 2D 旅行商问题 最短路径
赏
评 论
 上一篇
斐波那契堆：一种高效的优先队列
斐波那契堆：一种高效的优先队列
斐波那契堆是什么？斐波那契堆是一种特殊的堆数据结构，它在插入、删除最小值、合并等操作上具有非常优秀的均摊时间复杂度。与传统的二项堆相比，斐波那契堆在某些操作上表现得更加高效。 斐波那契堆的结构 最小堆的集合: 斐波那契堆实际上是一组最小堆的
2024-12-24 数据结构
heap 数据结构
下一篇 
PHP 解决最短路径问题
PHP 解决最短路径问题
在二维地图上寻找从A点到B点的最短路径是一项常见的任务，通常可以使用图算法来解决。常用的算法包括广度优先搜索（BFS）、Dijkstra算法和A*算法。 使用广度优先搜索（BFS）算法寻找最短路径广度优先搜索是一种简单而有效的算法，对于在无
2024-12-24 PHP
PHP 2D 最短路径
PHP 2D 旅行商问题 最短路径
PHP
发布日期:   2024-12-24
文章字数:   729
阅读时长:   3 分

如果需要在二维地图上找到一条路径，使得从起点到终点经过所有有奖励的点，并且路径最短，可以考虑使用图搜索算法如A*算法或Dijkstra算法的变种。这类问题通常称为“旅行商问题”（TSP, Traveling Salesman Problem），是一种经典的组合优化问题。

以下是使用A*算法的一个基本示例，你可以根据需要进行扩展，以包括所有奖励点。

示例地图（带奖励点）

假设地图如下：

  • 0 表示可以通行的空地。
  • 1 表示障碍物。
  • R 表示奖励点。
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
71
72
73
74
75
76
<?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 findShortestPath($map, $start, $end, $rewards) {
    $rows = count($map);
    $cols = count($map[0]);
    $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // 右, 下, 左, 上

    $queue = new SplPriorityQueue();
    $queue->insert([$start, [$start], 0], 0); // 队列中存储当前点、路径、已走步数
    $visited = [];

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

        if ($x == $end->x && $y == $end->y && empty($rewards)) {
            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] != 1 && !isset($visited["$newX,$newY"])) {
                $newCost = $cost + 1;
                $newRewards = array_filter($rewards, function($reward) use ($newPoint) {
                    return !($reward->x == $newPoint->x && $reward->y == $newPoint->y);
                });

                $queue->insert([$newPoint, array_merge($path, [$newPoint]), $newCost], -$newCost);
                $visited["$newX,$newY"] = true;
            }
        }
    }
    return null; // 无路径
}

// 示例地图：0表示可以通行，1表示障碍物，R表示奖励点
$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);
$rewards = [new Point(2, 2), new Point(3, 1)]; // 奖励点的坐标

$path = findShortestPath($map, $start, $end, $rewards);

if ($path) {
    echo "Path found:\n";
    foreach ($path as $point) {
        echo $point . " ";
    }
} else {
    echo "No path found.";
}
?>

代码解释：

  1. Point类：用于表示地图上的点。
  2. findShortestPath函数：实现了一个基本的优先队列搜索算法，接收地图、起点、终点和奖励点作为参数，返回从起点到终点经过所有奖励点的路径。
  3. directions数组：表示四个可能的移动方向（右、下、左、上）。
  4. 队列（SplPriorityQueue）：用于存储当前点、路径和已走步数，并按优先级排序。
  5. visited数组：用于标记已访问的点，避免重复访问。

运行结果：

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

总结：

这个示例中的算法实现了一个基本的优先队列搜索，并且在每次移动时检查是否经过奖励点。对于更复杂的地图和更多的奖励点，可以使用更高级的图搜索算法，如A*算法，并结合动态规划或其他优化技术。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/php-2d-tsp-solution.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 2D 旅行商问题 最短路径
赏
评 论
 上一篇
斐波那契堆：一种高效的优先队列
斐波那契堆：一种高效的优先队列
斐波那契堆是什么？斐波那契堆是一种特殊的堆数据结构，它在插入、删除最小值、合并等操作上具有非常优秀的均摊时间复杂度。与传统的二项堆相比，斐波那契堆在某些操作上表现得更加高效。 斐波那契堆的结构 最小堆的集合: 斐波那契堆实际上是一组最小堆的
2024-12-24 数据结构
heap 数据结构
下一篇 
PHP 解决最短路径问题
PHP 解决最短路径问题
在二维地图上寻找从A点到B点的最短路径是一项常见的任务，通常可以使用图算法来解决。常用的算法包括广度优先搜索（BFS）、Dijkstra算法和A*算法。 使用广度优先搜索（BFS）算法寻找最短路径广度优先搜索是一种简单而有效的算法，对于在无
2024-12-24 PHP
PHP 2D 最短路径
PHP 2D 旅行商问题 最短路径
PHP
发布日期:   2024-12-24
文章字数:   729
阅读时长:   3 分

如果需要在二维地图上找到一条路径，使得从起点到终点经过所有有奖励的点，并且路径最短，可以考虑使用图搜索算法如A*算法或Dijkstra算法的变种。这类问题通常称为“旅行商问题”（TSP, Traveling Salesman Problem），是一种经典的组合优化问题。

以下是使用A*算法的一个基本示例，你可以根据需要进行扩展，以包括所有奖励点。

示例地图（带奖励点）

假设地图如下：

  • 0 表示可以通行的空地。
  • 1 表示障碍物。
  • R 表示奖励点。
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
71
72
73
74
75
76
<?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 findShortestPath($map, $start, $end, $rewards) {
    $rows = count($map);
    $cols = count($map[0]);
    $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]]; // 右, 下, 左, 上

    $queue = new SplPriorityQueue();
    $queue->insert([$start, [$start], 0], 0); // 队列中存储当前点、路径、已走步数
    $visited = [];

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

        if ($x == $end->x && $y == $end->y && empty($rewards)) {
            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] != 1 && !isset($visited["$newX,$newY"])) {
                $newCost = $cost + 1;
                $newRewards = array_filter($rewards, function($reward) use ($newPoint) {
                    return !($reward->x == $newPoint->x && $reward->y == $newPoint->y);
                });

                $queue->insert([$newPoint, array_merge($path, [$newPoint]), $newCost], -$newCost);
                $visited["$newX,$newY"] = true;
            }
        }
    }
    return null; // 无路径
}

// 示例地图：0表示可以通行，1表示障碍物，R表示奖励点
$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);
$rewards = [new Point(2, 2), new Point(3, 1)]; // 奖励点的坐标

$path = findShortestPath($map, $start, $end, $rewards);

if ($path) {
    echo "Path found:\n";
    foreach ($path as $point) {
        echo $point . " ";
    }
} else {
    echo "No path found.";
}
?>

代码解释：

  1. Point类：用于表示地图上的点。
  2. findShortestPath函数：实现了一个基本的优先队列搜索算法，接收地图、起点、终点和奖励点作为参数，返回从起点到终点经过所有奖励点的路径。
  3. directions数组：表示四个可能的移动方向（右、下、左、上）。
  4. 队列（SplPriorityQueue）：用于存储当前点、路径和已走步数，并按优先级排序。
  5. visited数组：用于标记已访问的点，避免重复访问。

运行结果：

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

总结：

这个示例中的算法实现了一个基本的优先队列搜索，并且在每次移动时检查是否经过奖励点。对于更复杂的地图和更多的奖励点，可以使用更高级的图搜索算法，如A*算法，并结合动态规划或其他优化技术。

文章作者: Crazy Boy
文章链接: https://crazy-boy.com/posts/php-2d-tsp-solution.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Crazy Boy !
PHP 2D 旅行商问题 最短路径
赏
评 论
 上一篇
斐波那契堆：一种高效的优先队列
斐波那契堆：一种高效的优先队列
斐波那契堆是什么？斐波那契堆是一种特殊的堆数据结构，它在插入、删除最小值、合并等操作上具有非常优秀的均摊时间复杂度。与传统的二项堆相比，斐波那契堆在某些操作上表现得更加高效。 斐波那契堆的结构 最小堆的集合: 斐波那契堆实际上是一组最小堆的
2024-12-24 数据结构
heap 数据结构
下一篇 
PHP 解决最短路径问题
PHP 解决最短路径问题
在二维地图上寻找从A点到B点的最短路径是一项常见的任务，通常可以使用图算法来解决。常用的算法包括广度优先搜索（BFS）、Dijkstra算法和A*算法。 使用广度优先搜索（BFS）算法寻找最短路径广度优先搜索是一种简单而有效的算法，对于在无
2024-12-24 PHP
PHP 2D 最短路径
  目录
  目录
  目录
  目录
hexo