管理员 萨卡 发布于四月 6, 2020 管理员 发布于四月 6, 2020 不想算...但扫了一眼..这不就类似用dijkstra算法么, 只有最坏项式所以是NP 注释 摸鱼奇才咖啡喵 1.00节操 蹭一蹭萨卡大人的热度～ ベルンカステル 1.00节操 捕獲稀有度SSR野生薩卡大人! 1 1
管理员 萨卡 发布于四月 7, 2020 管理员 发布于四月 7, 2020 1 小时前, Mr.K 018 说道: 这个题可以证明是个NP完全，所以Dijkstra这种多项式时间的算法肯定是不行的。 证明的大概思路：这个问题可以规约到若干种不同的NP完全问题。例如，当船的出港时间为0，也没有货物要起吊（就是说只需要入港即可）的情况下，这个问题就退化成多机调度问题。众所周知，多机调度问题是个NP完全问题，因此本题也是一个NP完全问题。假设能找到本题的多项式时间算法，相当于证明了P=NP dijkstra并没多项式时间啊....
管理员 萨卡 发布于四月 7, 2020 管理员 发布于四月 7, 2020 2 分钟前, Mr.K 018 说道: 别吧，那阁下说的是哪个迪杰斯特拉…… 我还以为是最短路那个迪杰斯特拉 我说的就最基础的啊...他不一定是NP完整但肯定是NP.. 相关的旅行推销员问题都是NP的
推荐贴