srp问题是一个寻找最短时间的问题有一艘支援船在港口(假设坐标是0,0)，要去访问此时在海上航行的所有船只，问，按照什么顺序访问才会使得支援船的航行时间最短？我的想法是定义一个solution列表，保存找到的索引先遍历所有需要访问的船只，计算从支援船当前位置到当前船只的相遇时间，存入一个列表里面。然后对这个列表进行排序，从中选出时间最短的船的索引加入到solution列表中，然后把这个船从待访问的船中删除，更新支援船的坐标为这个相遇的坐标其他船只的坐标也更新为其速度乘以这个最短时间再继续下一次循环不知道这这样算不算是贪心算法？如果是贪心算法，不是贪心算法会有失效的情况吗？不知道这样会在什么情况下导致这个算法失效，找到的并不是全局最优。求各位大佬给我解惑...
2 回答
慕后森
TA贡献1802条经验 获得超5个赞
这个嘛，我对算法这方面不了解，我是个编程业余爱好者，算法平常也不太接触。不过对你上面描述的情况，我有一些看法。如果没有理解错的话，应该是每次都先访问与自己最接近的目标，对吧？这样的话可能会出现一种状况：当时间等于100的时候，你把大部分目标都访问了，你已经航行得远远，发现身后还有1个目标未曾访问，然后要再花50的时间回去访问那个目标，其实那个目标在当初第一轮排序的时候排第2位。只是每次做排序的时候都不首位。如果换做是我的话，一，我会先得出所有目标的所有排列组合，二，然后计算各个组合顺序访问所有目标所需的总时间，取最短时间的那个组合。三，然后每访问一个目标之后，以剩余的目标再作上述第一和第二步，取最短时间组合，以此类推。这样的好处是解决了我上面提到的问题，坏处是多了大量的计算。如果目标数量庞大的话，可以折衷先把所有目标排序，然后取前n位做排列组合。然后再以各个组合做头跟你的算法配合使用，选出最优组合。我的算法更贪婪
一只斗牛犬
TA贡献1784条经验 获得超2个赞
emmmm..这不就是旅行商问题嘛，这当然是个贪心算法因为这是个NP-Hard的问题，对于这种问题多采用近似算法求得一个可以接受的相似解就行了如果你一定要找个最优解的算法可以用动态规划，不过数据一多就跑不动了，普通计算机的话估计30个地点就得跑上几年了...
添加回答
举报
0/150
提交
取消