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

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就一定能算出一个最优解了。