数据结构的图要求经过指定一些边，求最优解？

Question

数据结构的图要求经过指定一些边，求最优解？
能帮忙指点一下应该怎么去网上找资料吗，比如和哪个问题类似，应该用什么算法？这个问题是这样的,货运公司必须经过某一些城市,题目给出各个城市之间的花费,让用A*算法求最优解.

这是输入:
花费 360 Sydney 到 Wagga         
花费 200 Sydney 到 Bathurst      
花费 200 Dubbo 到 Grafton        
花费 240 Dubbo 到 Bathurst       
花费 480 Grafton 到 Wagga        
花费 440 Grafton 到 Bathurst     
花费 400 Wagga 到 Bathurst       

要求必须经过:
Grafton 到 Wagga
Dubbo 到 Grafton
Sydney 到 Wagga
Sydney 到 Bathurst

结果是:
Sydney 到 Bathurst
Bathurst 到 Dubbo
Dubbo 到 Grafton
Grafton 到 Wagga
Wagga 到 Sydney
Sydney 到 Wagga
总花费 1840

Answer 1

这个是一类比较开放的问题，个人认为还是属于图论的一个部分，但是他不能用现有的最短路径的相关算法比如SPFA，dijkstra算法来解决。曾今好像一个朋友问过我，是华为的一个什么比赛题目。这个题目用A*算法肯定可以，关键是在于如何去设计这个启发式函数？相关知识你可以搜索1.经过指定的中间节点集的最短路径算法2.启发式搜索算法 A*

Answer 2

我觉得这题不太像是有多项式解法。（欢迎打脸）设点数n，边数m，必须经过的边数k，n<=500,m<=5000,k<=500。考虑暴力做法，O(n^3)预处理任意两点之间的最短路（当然也可以n次堆优化dijkstra，但这不是瓶颈），O(k!)枚举经过的k条边的排列并计算答案，总复杂度O(k!*k)，显然不能接受。注意到最优解并不一定需要枚举全部排列才能得到，可以使用模拟退火等随机化算法获得较优解，使用合适的参数应该可以在大多数时候得到最优解。我想尝试证明这个问题是NPC或NPH。将原问题的m条边记为从from[i]至to[i]。新建一个k个点的图，对k条指定边中的第i条和第j条，如果to[i]可达到from[j]，则在新建的图中从i向j连一条dis[to[i]][from[j]]的边。于是原问题问题在多项式时间内规约成新问题：在k个点的图中找出一条经过所有点的可重复路径，使路径长度最小。这个新问题看起来就很像NPC或NPH。（滑稽）但是我还没有想好怎么把新问题规约回原问题。目前的想法是对新问题的每个点i，在原问题的i<<1到(i<<1)|1之间连一条+inf的边，对新问题的每条边i->j，在原问题的(i<<1)|1到j<<1之间连一条disi的边，但是好像会有些问题,还没有想清楚。

Answer 3

算法不懂，但是我知道一个通用的解决此类CSP问题的框架，你可以看一下：Optaplanner

Answer 4

这个问题应该是NP的。我们可以这么考虑，首先我们知道给定一张图要找哈密尔顿路径是NP的。我们假设问题是有多项式算法的，那么给定一张图后，我们将点i拆成两个点i1,i2，然后i1向i2连一条边。对于原本的边i→j，改成i2→j1。我们要求所有的i1,i2都要经过，然后在新的图上跑一遍这个问题。假如有多项式算法，就可以通过删去i1→i2的边，得到原图的一张哈密尔顿路径。于是哈密尔顿路径就能够有多项式算法了，这是不可能的，所以该问题是NP的。 你或许可以使用A*之类的算法来做这个题。如果数据比较好的话你可以试试把必须走过的边的权值减去无穷大，然后使用SPFA算法跑，有可能能跑出最优解。这么做的话，有可能会出现负环，而SPFA是无法处理负环的，所以这是一个错误的做法。但是如果没有遇到负环，SPFA就一定能算出一个最优解了。