算法设计笔记（三）货郎问题与计算复杂性理论

能不能有效计算的临界问题
问题简述：

如下红色路线就是本题的解

对货郎问题进行建模

从城市C1到C2的距离加上从Ck2到Ck3的距离，一直加到Ck(n-1)到达Cnk城市的距离,再加上从第n个城市回到第n个城市的距离。
这就是在所有城市的排列下，长度的总和，而我们的求解即为此长度达到最小的排列。
红框中为我们的目标函数
然而，到现在为止还没有有效的算法

另一个 “0-1背包”问题

希望找到最好的装法
问题的解是一个0-1向量：若X1=1那么X1装入背包，若X1=0那么X1不装入背包
使目标函数最大化，且装入物品重量有限制，装入的总重量不超过B

双机调度

如：任务集中有六个任务，分别对应六个加工时间

其中一个解：可以把1，2，4号任务放到机器1上
3，5，6号任务放到机器2上

同样我们把解写成0-1向量

我们的想法是：让第一台机器的操作时间在不超过第二台机器操作时间一半的前提下尽可能的大，这样第二台机器的操作时间才能尽可能的小
这类问题我们统称为NP难问题