Chr*_*ass 9 algorithm search routes mathematical-optimization
问题:我有很多积分.这些点中的每一个都有一个列表,其中包含对已经计算和存储它们之间距离的其他点的引用.我需要确定从原点开始并通过特定数量的点到达任何目的地的最短路线.
例如:我正在度假,我住在一个特定的城市.我正在做一个单程旅行,看到任何四个城市,我想尽可能少地旅行.我不能不止一次访问同一个城市.
当前解决方案:现在我只是手动迭代每个可能性并存储最短路径.这有效,但感觉效率低下.此外,这个问题最终将扩展到包括从多个原点搜索到多个目标点,所以我认为这可能会爆炸搜索空间.
搜索最短路径的更好方法是什么？
回答更新的帖子,你检查每种可能性的解决方案是最佳的(至少,到目前为止还没有人发现更好的算法).是的,那是一个旅行推销员,他的本能并不是触及每个城市,而是触及每个城市一次.如果您不想搜索可能的最佳解决方案,您可能会发现使用更快工作的启发式方法很有用,但允许与理想解决方案有限的差异.
对于未来的回答者:Floyd-Warshall算法和所有类似Floyd的变体在这里都不适用.