问答题
用回溯法解布线问题时,求最优解的主要程序段如下:如果布线区域划分为n×m的方格阵列,扩展每个结点需O(1)的时间,L为最短布线路径的长度,则算法共耗时(O(mn)),构造相应的最短距离需要(O(L))时间。
问答题 用回溯法解0/1背包问题时,计算结点的上界的函数如下所示,请在空格中填入合适的内容。
问答题 请写出用回溯法解装载问题的函数。装载问题:有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船,其中集装箱i的重量为wi。装载问题要求确定是否有一个合理的装载方案可将这n个集装箱装上这2艘轮船。如果有,找出一种装载方案。
问答题 用分支限界法解装载问题时,对算法进行了一些改进,下面的程序段给出了改进部分;试说明斜线部分完成什么功能,以及这样做的原因,即采用这样的方式,算法在执行上有什么不同。