-4

I am currently in the process of going through old programming olympiad questions, and found question 5 rather difficult. The problem is based in some category of graph theory and involves computing the most inexpensive path and visiting all nodes. Full details can be found here: problem

Would it be suitable to use A* search algorithm? What kind of algorithm would you use to solve the problem, which is fast to implement and can solve the problem in the given time period?

4

2 回答 2

1

正如@kiheru 所说,A* 不起作用。

这是旅行商问题,是一个NP完全问题。更换行驶距离的通行费,您会遇到同样的问题。Traveling Salesman 链接有几个这样的算法。

旅行推销员

您会根据城市的数量找到不同的算法,但是当您将城市添加到计算机不是精确解决方案的最佳选择时,它的计算成本会更高。有许多不同的技术可以获得近似值,但这不是一个可解决的问题。

如果我要编写代码,我会使用一种叫做语言几何的东西(我在研究生院学到的东西)。基本上,您将节点视为一个游戏板,并且一次向您想要的答案迈出一步并对其进行评估。这不会解决它,但它会在很短的时间内给你一个很好的近似值。

于 2013-07-18T15:46:19.513 回答
0

这被称为旅行商问题,并且是NP-Complete。这意味着没有比暴力破解更快的方法来解决这个问题(嗯,实际上有一个基于动态编程O(2^n*n^2)的解决方案)。由于您只处理 6 个节点,即 6 个!= 720 条可能的检查路径,最简单的解决方案是尝试每个不同的城市排序并记录哪个最快。

(此外,与上面@kiheru 的评论相反,A* 不是启发式方法。它使用启发式方法,但仍能找到最短路径问题的精确解决方案。但是,无论哪种方式,它都不适用于您的问题)

于 2013-07-18T16:07:33.167 回答