英国游客

Question

“一名游客想从利物浦到悉尼，在此过程中访问其他一些城市。

对于每一对城市，他可以乘坐汽车、火车或渡船，每个选项都有一个和Time。

目标是前往syndey，在此过程中横穿所有城市，同时将时间和成本控制在最低限度。“

如何验证这个问题是NP问题？给定总时间T和总成本C？

如果我有5个节点，由4个边连接，每个边有3个选项(汽车、渡船、火车)，每个选项都有成本和时间。

如何处理这些约束？我要试一下所有的排列吗？

我需要关于实际解决方案的指导，我意识到这是最小生成树的一个子集，但是现在我有了两个约束，时间和cost..how来解决这个问题？

Answer 1

这类问题是用匈牙利算法解决的。