问题描述:试设计一个用队列式分支限界法搜索一般解空间的函数,其参数包括结点可行性削定函数

问题描述:试设计一个用队列式分支限界法搜索子集空间树的函数,其参数包括结点可行性判定函数和上界函数等必要的函数,并将此函数用于解装载问题.

装载问题描述如下:有一批共n个集装箱要装上一艘载重量为c的轮船,其中集装箱i的重量为w_i找出一种最优装载方案,将轮船尽可能装满,即在装载体积不受限制的情况下,将尽可能重的集装箱装上轮船.

算法设计:对于给定的n个集装箱和轮船的载重量,计算最优装载方案.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是集装箱数,c是轮船的载重量.接下来的1行中有n个正整数,表示集装箱的重量.

结果输出:将计算的最大装载重量输出到文件output.txt.

问题描述:试设计一个用优先队列式分支限界法搜索排列空间树的函数,其参数包括结点可行性判定雨数和上界的数等必要的函数,并将此函数用于解批处理作业调度问题.给定n个作业的集合.每个作业J_i都有2项任务分别在2台机器上完成.每个作业必须先由机器1处理,再由机器2处理.作业J_i需要机器j的处理时间为t_ij(=1,2,...,n;j=1,2).对于一个确定的作业调度,设F_ij是作业i在机器j上完成处理的时间.所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和.

批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小.

算法设计:对于给定的n个作业,计算最佳作业调度方案.

数据输入:由文件input.txt提供输入数据.文件第1行有1个正整数n,表示作业数.接下来的n行中,每行有2个正整数i和j,分别表示在机器1和机器2上完成该作业所需的处理时间.

结果输出:将最佳作业调度方案及其完成时间和输出到文件output.txt.文件的第1行是完成时间和,第2行是最佳作业调度方案.

问题描述:试设计一个用回溯法搜索排列空间树的函数.该函数的参数包括结点可行性判定函数和上界函数等必要的函数,并将此的数用于解圆排列问题.

圆排列问题描述如下:给定n个大小不等的圆,现要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切.圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列.例如,当n=3,且所给的3个圆的半径分别为1、1、2时,这3个圆的最小长度的圆排列见图5-9,其最小长度为.

算法设计:对于给定的n个圆,计算最小长度圆排列.

数据输入:由文件input.txt提供输入数据.文件的第1行是1个正整数n,表示有n个圆.第2行有n个正数,分别表示n个圆的半径.

结果输出:将计算的最小长度输出到文件output.txt.文件的第1行是最小长度,保留5位小数.

问题描述:试设计一个用回溯法搜索子集空间树的函数.该函数的参数包括结点可行性判定函数和上界函数等必要的函数,并将此函数用于解装载问题.

装载问题描述如下:有一批共n个集装箱要装上艘载重量为c的轮船,其中集装箱i的重量为wi.找出一种最优装载方案,将轮船尽可能装满,即在装载体积不受限制的情况下,将尽可能重的集装箱装上轮船.

算法设计:对于给定的n个集装箱的重量和轮船的重量,计算最优装载方案.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是集装箱数,c是轮船的载重量.接下来的1行中有n个正整数,表示集装箱的重量.

结果输出:将计算的最大装载重量输出到文件output.txt.

问题描述:设计一个用回溯法搜索子集空间树的函数,参数包括结点可行性判定函数和上界函数等必要的函数,并将此的数用于解0-1背包问题.

0-1背包问题描述如下;给定n种物品和一个背包.物品i的重量是w_i,其价值为v_i背包的容量为C.应如何选择装入背包的物品,使装入背包中物品的总价值最大?

在选择装入肯包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包.不能将物品i装入背包多次,也不能只装入部分的物品i.

0-1背包问题形式化描述如下:给定,要求n元0-1向量,使得而且达到最大.

算法设计:对于给定的n种物品的重量和价值,以及背包的容量,计算可装入背包的最大价值.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是物品数,c是背包的容量.接下来的1行中有n个正整数,表示物品的价值.第3行中有n个正整数,表示物品的重量.

结果输出:将计算的装入背包物品的最大价值和最优装入方案输出到文件output.txt

A.在扩展结点处，先生成其所有的儿子结点(分支)

B.从当前的活结点表中选择上一个扩展结点。

C.为了有效地选择下一扩展结点，加速搜索的进程，在每一个活结点处，计算一个函数值(限界)

D.根据函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。

A.广度优先

B.活结点优先

C.扩展结点优先

D.深度优先

此题为判断题(对，错)。