懂图论的可以进!TSP问题与最短路问题杂合的 属于什么类型?
问题描述:
懂图论的可以进!TSP问题与最短路问题杂合的 属于什么类型?
出发点就是终点,且要求所有的节点都要去.
最短路问题,则没有强制去所有节点.
但我现在 有些节点必去,有些节点不必去,则请问它是属于哪种类型?
答
你把不需要去的节点全部删去(当然连与它相关的边删去),剩下的就是都要去的节点,这就是一个哈密顿问题,而且简化了你的图.对于哈密顿问题现在没有一个完美的算法,不过可以找到一些可用的定理作为判断.
你可以把你的图发给我看看,我和你一起讨论行不?