有一张带点的地图:
每个点旁边的绿色数字是该点的 ID,红色数字是该点的奖励。我必须找到在 #1 点开始和结束的最快周期,并且至少获得 x(在这种情况下为 15)加分。我可以多次使用城市;但是,我只会获得一次奖励积分。我必须使用近似算法来做到这一点,但我真的不知道从哪里开始。
输出将如下所示:
(1,3,5,2,1) (11.813 length)
有一张带点的地图:
每个点旁边的绿色数字是该点的 ID,红色数字是该点的奖励。我必须找到在 #1 点开始和结束的最快周期,并且至少获得 x(在这种情况下为 15)加分。我可以多次使用城市;但是,我只会获得一次奖励积分。我必须使用近似算法来做到这一点,但我真的不知道从哪里开始。
输出将如下所示:
(1,3,5,2,1) (11.813 length)
这不是NP问题吗?如果是这样,如果不测试所有可能性,您将无法找到最快的,这将花费相当长的时间。
这个问题类似于旅行推销员,恕我直言。到目前为止,这个问题最著名的解决方案是Ant Colony 解决方案。此解决方案不能保证总是找到可能的最佳解决方案,但它会在可接受的时间内找到至少一个相当好的解决方案。
我认为可以通过以某种方式考虑奖励积分来修改 Ant Colony 解决方案以解决您的问题。可能不是您想听到的答案,而是我目前提供的最好的答案。