贪心算法-SRP问题

monsterzzz
  • 131

srp问题是一个寻找最短时间的问题
有一艘支援船在港口(假设坐标是 0,0),要去访问此时在海上航行的所有船只,问,按照什么顺序访问才会使得支援船的航行时间最短?

我的想法是

定义一个solution列表,保存找到的索引

先遍历所有需要访问的船只,计算从支援船当前位置到当前船只的相遇时间,存入一个列表里面。
然后对这个列表进行排序,从中选出时间最短的船的索引加入到 solution 列表中,
然后把这个船从待访问的船中删除,
更新支援船的坐标为 这个相遇的坐标
其他船只的坐标也更新为其速度乘以这个最短时间

再继续下一次循环

不知道这这样算不算是贪心算法?
如果是贪心算法,不是贪心算法会有失效的情况吗?
不知道这样会在什么情况下导致这个算法失效,找到的并不是全局最优。

求各位大佬给我解惑...

回复
阅读 1.2k
2 个回答

这个嘛,我对算法这方面不了解,我是个编程业余爱好者,算法平常也不太接触。
不过对你上面描述的情况,我有一些看法。
如果没有理解错的话,应该是每次都先访问与自己最接近的目标,对吧?
这样的话可能会出现一种状况:
当时间等于100的时候,你把大部分目标都访问了,你已经航行得远远,发现身后还有1个目标未曾访问,
然后要再花50的时间回去访问那个目标,其实那个目标在当初第一轮排序的时候排第2位。只是每次做排序的时候都不首位。

如果换做是我的话,
一,我会先得出所有目标的所有排列组合,
二,然后计算各个组合顺序访问所有目标所需的总时间,取最短时间的那个组合。
三,然后每访问一个目标之后,以剩余的目标再作上述第一和第二步,取最短时间组合,以此类推。
这样的好处是解决了我上面提到的问题,坏处是多了大量的计算。

如果目标数量庞大的话,可以折衷先把所有目标排序,然后取前n位做排列组合。
然后再以各个组合做头跟你的算法配合使用,选出最优组合。

我的算法更贪婪

emmmm..这不就是旅行商问题嘛,这当然是个贪心算法
因为这是个NP-Hard的问题,对于这种问题多采用近似算法求得一个可以接受的相似解就行了

如果你一定要找个最优解的算法可以用动态规划,不过数据一多就跑不动了,普通计算机的话估计30个地点就得跑上几年了...

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