娱乐 这波啊，这波是最优化

[萨卡]

不想算...但扫了一眼..这不就类似用dijkstra算法么, 只有最坏项式所以是NP

[萨卡]

2 分钟前, 随性而为 说道:

啊？迪杰斯特拉可以用在这个上吗，我觉得这个很难构成一个图啊

不知道, 也许可以用变种的? 

 

[萨卡]

1 小时前, Mr.K 018 说道:

这个题可以证明是个NP完全，所以Dijkstra这种多项式时间的算法肯定是不行的。

证明的大概思路：这个问题可以规约到若干种不同的NP完全问题。例如，当船的出港时间为0，也没有货物要起吊（就是说只需要入港即可）的情况下，这个问题就退化成多机调度问题。众所周知，多机调度问题是个NP完全问题，因此本题也是一个NP完全问题。假设能找到本题的多项式时间算法，相当于证明了P=NP

dijkstra并没多项式时间啊....

[萨卡]

2 分钟前, Mr.K 018 说道:

别吧，那阁下说的是哪个迪杰斯特拉……

我还以为是最短路那个迪杰斯特拉

我说的就最基础的啊...他不一定是NP完整但肯定是NP.. 相关的旅行推销员问题都是NP的