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

[Mr.K 018]

@ZERC大佬弄了个每日数学挑战， @Xchara大佬也做了个逻辑分析https://sstm.moe/topic/252606-数学做累了？那就来试试这个简单的逻辑分析题吧/ 诶，莫非我也能用这种方式水节操？

我也来蹭蹭热度！

这道题是从一个老旧PPT上扒来的问题，名字叫“港口调度问题”（名字估计也是瞎起的，反正我百度这个名字百度不出啥来）。这道题题目如下：

港口调度问题

已知若干货轮(C1~Cn)要在港口停泊卸货。港口具有：

• 2个相同的泊位M1、M2
• 2个相同的起吊设备T1、T2
• 2辆相同的运输车V1、V2
• 3个仓库S1~S3

起吊设备不与泊位绑定。起吊设备在一个泊位起吊完成后，移动到另一泊位（若需要）的时间忽略不计。运输车空闲时停留在港口缓冲区等待被吊车运送至此的货物。运送到目的仓库后，运输车立刻返回缓冲区等待下次运输。

船上的货物首先要随船入港，之后被起吊设备运送到港口缓冲区，随后被运输车运送到指定仓库。每个货物起吊时间不一定相同，货轮出入泊位时间也不一定相同。4艘货轮均在0时刻抵达，现要规划入泊、吊送货物方案，通过设置合理的轮船出入泊位、吊车吊运货物和运输车运输顺序，使总的调度用时尽可能短。

“总的调度用时”的定义：从0时刻各货轮抵达起至最后一个货物进入仓库、货船全部离港且运输车全部返回缓冲区为止所花费的时间。

作为数据，货轮、货物和仓库的相关信息列如下。

表1：货轮信息表

货轮序号	入港用时	离港用时
C1	26	20
C2	15	10
C3	30	24
C4	40	26
C5	50	25

表2：货物信息表

编号	所属货轮	目的仓库	起吊用时
P11	C1	S1	15
P12	C1	S1	26
P13	C1	S2	37
P14	C1	S3	9
P15	C1	S2	32
P21	C2	S3	8
P22	C2	S2	9
P23	C2	S3	27
P24	C2	S1	11
P25	C2	S2	4
P26	C2	S3	5
P31	C3	S3	8
P32	C3	S1	51
P33	C3	S2	27
P34	C3	S1	13
P35	C3	S3	29
P41	C4	S1	10
P42	C4	S2	22
P43	C4	S1	25
P51	C5	S1	17
P52	C5	S3	26
P53	C5	S3	7
P54	C5	S2	30
P55	C5	S2	43

表3 仓库信息表

编号	往返时间
C1	16
C2	20
C3	24

构造出各位认为总用时足够短的调度方案，说明轮船、货物起吊、运输车的调度顺序并推算出方案的调度时间，相应定义见题干。

由于数据是我瞎编的，我也不知道准确的最短用时是多少（被打死）。因此，从现在到明天（即4月7日）21点为止为有效时间，将会选出得出调度时间最短的解的作者，给予我自掏腰包的100节操奖励！（多人给出的解均为最优的，奖励只颁给第一个给出已知最优解的作者；同一个人的多个解以最优的为准；奖励颁发之后给出的解很遗憾是无效的）

p.s. 这道题是个NP-完全问题，大家可以说说为什么？（不要求严谨的证明，思路也可；证明无奖励）

四月 6, 2020，由Mr.K 018修改

[Mr.K 018]

8 小时前, 原初の冷火 说道:

有个疑问  把货物吊到缓冲区的时候 需要缓冲区里有车嘛

就是这个货物是直接吊到车上  还是在缓冲区里车自己去取

缓冲区是无限大的，送到那里去就好

[Mr.K 018]

9 小时前, 萨卡 说道:

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

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

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

[Mr.K 018]

24 分钟前, 萨卡 说道:

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

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

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