您尚未登录。

楼主 # 2023-05-10 16:00:44

dykxjh
会员
注册时间: 2020-03-25
已发帖子: 148
积分: 178

最短路径算法探讨

1.png

已知二维平面有N个点,要求遍历所有的已知点,求最短路径算法


注意:不是A点到B点的最短路径,是遍历所有点的最短路径。

离线

#1 2023-05-10 16:25:43

skrlaoshiren
会员
注册时间: 2019-12-03
已发帖子: 25
积分: 85

Re: 最短路径算法探讨

搜了一下,stackoverflow有类似的问题,贴几个看看是不是楼主想要的。
https://stackoverflow.com/questions/1511585/algorithm-optimization-shortest-route-between-multiple-points
https://gis.stackexchange.com/questions/50150/how-to-find-the-best-route-through-multiple-points

最近编辑记录 skrlaoshiren (2023-05-10 16:48:29)

离线

楼主 #2 2023-05-11 10:12:29

dykxjh
会员
注册时间: 2020-03-25
已发帖子: 148
积分: 178

Re: 最短路径算法探讨

这个问题在现实生活中的应用,比如送外卖,外卖员需要把外卖送到每个客户手中,怎么走路径最短?

以下是 Dijkstra 算法的 C 语言实现:

#include <stdio.h>
#include <limits.h>

#define V                   10 // 给定点的数量
#define AMI_INT_MAX         AMI_INT

int graph[V][V] = { // 给定的邻接矩阵
    { 0, 4, 3, 0, 0, 0, 0, 8, 0, 0 },
    { 4, 0, 0, 0, 0, 0, 0, 11, 0, 0 },
    { 3, 0, 0, 7, 0, 0, 0, 0, 0, 0 },
    { 0, 0, 7, 0, 9, 14, 0, 0, 0, 0 },
    { 0, 0, 0, 9, 0, 10, 0, 0, 0, 0 },
    { 0, 0, 0, 14, 10, 0, 2, 0, 0, 0 },
    { 0, 0, 0, 0, 0, 2, 0, 1, 6, 0 },
    { 8, 11, 0, 0, 0, 0, 1, 0, 7, 0 },
    { 0, 0, 0, 0, 0, 0, 6, 7, 0, 5 },
    { 0, 0, 0, 0, 0, 0, 0, 0, 5, 0 },
};

int minDistance(int dist[], int visited[]) {
    int minDist = AMI_INT_MAX, minDistIndex;
    for (int i = 0; i < V; i++) {
        if (!visited[i] && dist[i] <= minDist) {
            minDist = dist[i];
            minDistIndex = i;
        }
    }
    return minDistIndex;
}

void dijkstra(int src) {
    int dist[V], visited[V];
    for (int i = 0; i < V; i++) {
        dist[i] = AMI_INT_MAX;
        visited[i] = 0;
    }
    dist[src] = 0;
    for (int i = 0; i < V - 1; i++) {
        int u = minDistance(dist, visited);
        visited[u] = 1;
        for (int v = 0; v < V; v++) {
            if (!visited[v] && graph[u][v] && dist[u] != AMI_INT_MAX
                && dist[u] + graph[u][v] < dist[v]) {
                dist[v] = dist[u] + graph[u][v];
            }
        }
    }
    printf("顶点\t距离\n");
    for (int i = 0; i < V; i++) {
        printf("%d\t%d\n", i, dist[i]);
    }
}

int main() {
    dijkstra(0);
    return 0;
}

离线

#3 2023-05-11 18:39:02

Fomalhaut
会员
注册时间: 2021-10-28
已发帖子: 36
积分: 31

Re: 最短路径算法探讨

这个不是NP完全问题吗?算法应该都是指数时间的。

最近编辑记录 Fomalhaut (2023-05-11 18:39:38)

离线

楼主 #4 2023-05-17 09:21:55

dykxjh
会员
注册时间: 2020-03-25
已发帖子: 148
积分: 178

Re: 最短路径算法探讨

Fomalhaut 说:

这个不是NP完全问题吗?算法应该都是指数时间的。

是的,最后还是放弃了,点太多,没有找到好的算法。穷尽法CPU根本算不过来

离线

#5 2023-05-17 11:18:48

mojerro
会员
注册时间: 2023-05-16
已发帖子: 14
积分: 4

Re: 最短路径算法探讨

是不是可以尝试强化学习这种,不过如何设计正向激励可能得研究一下

离线

#6 2023-05-23 00:19:52

lyxmoo
会员
注册时间: 2022-04-23
已发帖子: 2
积分: 22

Re: 最短路径算法探讨

dykxjh 说:
Fomalhaut 说:

这个不是NP完全问题吗?算法应该都是指数时间的。

是的,最后还是放弃了,点太多,没有找到好的算法。穷尽法CPU根本算不过来

首先,绝对最小的最短路径很难求得;

不过可以求近似最优解。
1.先套一层kNN,分割成k个区域,在每个区域内求最小;然后求区-区最短路径;
2.套一层欧式区域分割成MxN块,在每个区域用欧式距离搜索,然后近邻搜索最短路径;

。。。。
10086. 用 Swarm Search,缺点是,搜索时间可能也是未知的。

离线

页脚

工信部备案:粤ICP备20025096号 Powered by FluxBB

感谢为中文互联网持续输出优质内容的各位老铁们。 QQ: 516333132, 微信(wechat): whycan_cn (哇酷网/挖坑网/填坑网) service@whycan.cn