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

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

阅读 5.3k
4 个回答

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

我觉得这题不太像是有多项式解法。(欢迎打脸)
设点数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的边,但是好像会有些问题,还没有想清楚。

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

这个问题应该是NP的。
我们可以这么考虑,首先我们知道给定一张图要找哈密尔顿路径是NP的。
我们假设问题是有多项式算法的,那么给定一张图后,我们将点i拆成两个点i1,i2,然后i1向i2连一条边。
对于原本的边i→j,改成i2→j1。
我们要求所有的i1,i2都要经过,然后在新的图上跑一遍这个问题。
假如有多项式算法,就可以通过删去i1→i2的边,得到原图的一张哈密尔顿路径。
于是哈密尔顿路径就能够有多项式算法了,这是不可能的,所以该问题是NP的。

你或许可以使用A*之类的算法来做这个题。如果数据比较好的话你可以试试把必须走过的边的权值减去无穷大,然后使用SPFA算法跑,有可能能跑出最优解。
这么做的话,有可能会出现负环,而SPFA是无法处理负环的,所以这是一个错误的做法。
但是如果没有遇到负环,SPFA就一定能算出一个最优解了。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题