2

有一张带点的地图:

带有多个节点的地图,每个节点旁边都有一个绿色和红色数字

每个点旁边的绿色数字是该点的 ID,红色数字是该点的奖励。我必须找到在 #1 点开始和结束的最快周期,并且至少获得 x(在这种情况下为 15)加分。我可以多次使用城市;但是,我只会获得一次奖励积分。我必须使用近似算法来做到这一点,但我真的不知道从哪里开始。

输出将如下所示:

(1,3,5,2,1) (11.813 length)

与以前相同的地图,预期的输出路线以橙色突出显示

4

1 回答 1

0

这不是NP问题吗?如果是这样,如果不测试所有可能性,您将无法找到最快的,这将花费相当长的时间。

这个问题类似于旅行推销员,恕我直言。到目前为止,这个问题最著名的解决方案是Ant Colony 解决方案。此解决方案不能保证总是找到可能的最佳解决方案,但它会在可接受的时间内找到至少一个相当好的解决方案。

我认为可以通过以某种方式考虑奖励积分来修改 Ant Colony 解决方案以解决您的问题。可能不是您想听到的答案,而是我目前提供的最好的答案。

于 2013-01-20T01:11:07.633 回答