Jer*_*oen 13 algorithm artificial-intelligence path shortest-path
假设我有10分.我知道每个点之间的距离.
我需要找到通过所有点的最短路线.
我已经尝试了几种算法(Dijkstra,Floyd Warshall,......),它们都给了我开始和结束之间的最短路径,但是它们没有制作一条包含所有点的路线.
排列工作正常,但它们太耗资源.
您可以建议我使用哪些算法来研究这个问题？或者是否有记录的方法使用上述算法执行此操作？
Gra*_*ton 26
看看旅行商问题.
您可能希望研究一些启发式解决方案.他们可能无法为您提供100%的确切结果,但通常他们可以在合理的时间内提出足够好的解决方案(距离最佳解决方案2%到3%).
Lar*_*rry 6
这显然是旅行商问题.特别是N=10,您可以尝试O(N!)使用简单算法,或使用动态编程,您可以O(n^2 2^n)通过交易空间将其减少.
N=10
O(N!)
O(n^2 2^n)
除此之外,由于这是一个NP难题,你只能希望得到一个近似或启发式,给出通常的警告.
归档时间：
15 年，7 月 前
查看次数：
18911 次
最近记录：
6 年，3 月 前