首页 > 继续教育
题目内容 (请给出正确答案)
[主观题]

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

和上界函数等必要的函数,并将此函数用于解布线问题.

印制电路板将布线区域划分成n×m个方格阵列(见图6-3(a).精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案.在布线时,电路只能沿直线或直角布线(见图6-3(b).为了避免线路相交,已布线了的方格做了封锁标记,其他线路不允许穿过被封锁的方格.

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

算法设计:对于给定的布线区域,计算最短布线方案.

数据输入:由文件input.txt给出输入数据.第1行有3个正整数n、m.k,分别表示布线区域方格阵列的行数、列数和封闭的方格数.接下来的k行中,每行2个正整数,表示被封闭的方格所在的行号和列号.最后的2行,每行也有2个正整数,分别表示开始布线的方格(p,q)和结束布线的方格(r,s).

结果输出:将计算的最短布线长度和最短布线方案输出到文件output.txt.文件的第1行是最短布线长度.从第2行起,每行2个正整数,表示布线经过的方格坐标.如果无法布线,则输出“NoSolution!".

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

查看答案
答案
收藏
如果结果不匹配,请 联系老师 获取答案
您可能会需要:
您的账号:,可能还需要:
您的账号:
发送账号密码至手机
发送
安装优题宝APP,拍照搜题省时又省心!
更多“问题描述:试设计一个用队列式分支限界法搜索一般解空间的函数,…”相关的问题
第1题
问题描述:试设计一个用队列式分支限界法搜索子集空间树的函数,其参数包括结点可行性判定函数
和上界函数等必要的函数,并将此函数用于解装载问题.

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

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

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

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

点击查看答案
第2题
问题描述:假设要将一组元件安装在一块线路板上.为此需要设计一个线路板布线方案.各元件的连线
数由连线矩阵conn给出.元件i和元件j之间的连线数为conn(i,j).如果将元件i安装在线路板上位置r处,而将元件j安装在线路板上位置s处,则元件i和元件j之间的距离为dist(r,s)确定了所给的n个元件的安装位置,就确定了一个布线方案.与此布线方案相应的布线成本为.试设计一个优先队列式分支限界法,找出所给n个元件的布线成本最小的布线方案.

算法设计:对于给定的n个元件,改计一个优先队列式分支限界法,计算最佳布线方案,使布线费用达到最小.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数n(1≤n≤20).接下来的n-1行,每行n-1个数,表示元件i和元件j之间连线数(1≤i<j≤20).

结果输出:将计算的最小布线费川以及相应的最佳布线方案输出到文件output.txt.

点击查看答案
第3题
问题描述:假设有n个任务由k个可并行工作的机器完成.完成任务i需要的时间为ti试设计一个算法找
出完成这n个任务的最佳调度,使得完成全部任务的时间最早.

算法设计:对任意给定的整数n和k,以及完成任务i需要的时间为ti(i=1,2,...,n).设计一个优先队列式分支限界法,计算完成这n个任务的最佳调度.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和k.第2行的n个正整数是完成n个任务需要的时间.

结果输出:将计算的完成全部任务的最早时间输出到文件output.txt.

点击查看答案
第4题
问题描述:试设计一个用优先队列式分支限界法搜索子集空间树的函数.该函数的参数包括结点可行
性判定函数和上界函数等必要的函数,并将此函数用于解0-1背包问题.

0-1背包问题描述如下:给定n种物品和一背包.物品i的重量是wi,其价值为vi,背包的容量为C.问应如何选择装入背包的物品,使得装入背包中物品的总价值最大,在选择装入背包的物品时,对每种物品i只有两种选择,即装入背包或不装入背包.不能将物品i装入背包多次,也不能只装入部分的物品i.

0-1背包问题形式化描述如下:给定C>0,wi>0,vi>0(1≤i≤n),要求n元0-1向量,使得,而且达到最大.因此,0-1背包问题是一个特殊的整数规划问题.

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

数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和C,分别表示有n种物品,背包的容量为C.接下来的2行中,每行有n个数、分别表示各物品的价值和重量.

结果输出:将最佳装包方案及其最大价值输出到文件output.txt.文件的第1行是最大价值,第2行是最佳装包方案.

点击查看答案
第5题
问题描述:在n×n格的棋盘.上放置彼此不受攻击的n个皇后.按照国际象棋的规则,皇后可以攻击与之处
在同一行或同一列或同一斜线上的棋子.n皇后问题等价于在n×n格的棋盘上放置n个皇后,任何两个皇后不放在同一行或同一列或同一斜线上.

算法设计:设计一个解n后问题的队列式分支限界法,计算在n×n个方格上放置彼此不受攻击的n个皇后的一个放置方案.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数n.

结果输出:将计算的彼此不受攻击的n个皇后的一个放置方案输出到文件output.txt文件的第1行是n个皇后的放置方案.

点击查看答案
第6题
问题描述:羽毛球队有男女运动员各n人.给定2个n×n矩阵P和Q.P[i][j]是男运动员i和女运动员j配对
组成混合双打的男运动员竞赛优势;Q[i][j]是女运动英i和男运动员j配合的女运动员竞赛优势.由于技术配合和心理状态等因素影响,P[i][j]不体定等于Q[i][j].

男运动员i和女运动员j配对组成混合双打的男女双方竞赛优势为.设计一个算法,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大.

算法设计:设计一个优先队列式分支限界法,对于给定的男女运动员竞赛优势,计算男女运动员最佳配对法,使各组男女双方竞赛优势的总和达到最大.

数据输入:由文件input.txt给出输入数据.第1行有1个正整数n(1≤n≤20).接下来的2n行,每行n个数.前n行是p,后n行是q.

结果输出:将计算的男女双方竞赛优势的总和的鼓大值输出到文件output.txt.

点击查看答案
第7题
在解最大团问题的优先队列式分支限界法中,当前扩展结点满足cn+n-i≥bestn的右儿子结点被插入到优先队列中.如果将这个条件修改为满足cn+n-i>bestn右儿子结点插入优先队列,仍能保证算法的正确性吗?为什么?

点击查看答案
第8题
问题描述:给定一个赋权无向图G=(V,E),每个顶点都有权值w(v).如果,且对任意(u,V)∈E有u∈U或v∈U,

问题描述:给定一个赋权无向图G=(V,E),每个顶点都有权值w(v).如果,且对任意(u,V)∈E有u∈U或v∈U,就称U为图G的一个顶点覆盖.G的最小权顶点覆盖是指G中所含顶点权之和最小的顶点覆盖.

算法设计:对于给定的无向图G,设计一个优先队列式分支限界法,计算G的最小权顶点覆盖.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和m,表示给定的图G有n个顶点和m条边,顶点编号为1,2,...,n.第2行有n个正整数表示n个顶点的权.接下来的m行中,每行有2个正整数u和v,表示图G的一条边(u,v).

结果输出:将计算的最小权顶点覆盖的顶点权值和以及最优解输出到文件output.txt.文件的第1行是最小权顶点覆盖顶点权之和;第2行是最优解xi(1≤i≤n),xi=0表示顶点i不在最小权顶点覆盖中,xi=1表示顶点i在最小权顶点覆盖中.

点击查看答案
第9题
试修改解旅行售货员问题的分支限界法,使得s=n-2的结点不插入优先队列,而是将当前最优排列存储于bestp中.这样修改后,算法在下一个扩展结点满足条件Lcost≥bestc时结束.

点击查看答案
第10题
试修改解旅行售货员问题的分支限界法,使得算法保存已产生的排列树.

点击查看答案
退出 登录/注册
发送账号至手机
密码将被重置
获取验证码
发送
温馨提示
该问题答案仅针对搜题卡用户开放,请点击购买搜题卡。
马上购买搜题卡
我已购买搜题卡, 登录账号 继续查看答案
重置密码
确认修改