贪心算法-SRP问题

Question

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

我的想法是

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

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

再继续下一次循环

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

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

Answer 1

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

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

如果目标数量庞大的话，可以折衷先把所有目标排序，然后取前n位做排列组合。

然后再以各个组合做头跟你的算法配合使用，选出最优组合。

我的算法更贪婪

Answer 2

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

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