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?
正如@kiheru 所说，A* 不起作用。
这是旅行商问题，是一个NP完全问题。更换行驶距离的通行费，您会遇到同样的问题。Traveling Salesman 链接有几个这样的算法。
您会根据城市的数量找到不同的算法，但是当您将城市添加到计算机不是精确解决方案的最佳选择时，它的计算成本会更高。有许多不同的技术可以获得近似值，但这不是一个可解决的问题。
如果我要编写代码，我会使用一种叫做语言几何的东西（我在研究生院学到的东西）。基本上，您将节点视为一个游戏板，并且一次向您想要的答案迈出一步并对其进行评估。这不会解决它，但它会在很短的时间内给你一个很好的近似值。
这被称为旅行商问题，并且是NP-Complete。这意味着没有比暴力破解更快的方法来解决这个问题（嗯，实际上有一个基于动态编程O(2^n*n^2)的解决方案）。由于您只处理 6 个节点，即 6 个！= 720 条可能的检查路径，最简单的解决方案是尝试每个不同的城市排序并记录哪个最快。
（此外，与上面@kiheru 的评论相反，A* 不是启发式方法。它使用启发式方法，但仍能找到最短路径问题的精确解决方案。但是，无论哪种方式，它都不适用于您的问题）