首页 > 考试题库

题目内容（请给出正确答案）

[主观题]

问题描述:试设计一个用回溯法搜索排列空间树的函数.该函数的参数包括结点可行性判定函数和上

界函数等必要的函数,并将此的数用于解圆排列问题.

圆排列问题描述如下:给定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位小数.

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

查看答案

如果结果不匹配，请联系老师获取答案

您可能会需要：

重置密码查看订单联系客服

安装优题宝APP，拍照搜题省时又省心！

更多“问题描述:试设计一个用回溯法搜索排列空间树的函数.该函数的参…”相关的问题

第1题

问题描述:试设计一个用回溯法搜索子集空间树的函数.该函数的参数包括结点可行性判定函数和上

界函数等必要的函数,并将此函数用于解装载问题.

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

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

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

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

点击查看答案

第2题

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

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

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

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

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

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

点击查看答案

第3题

问题描述:试设计一个用优先队列式分支限界法搜索子集空间树的函数.该函数的参数包括结点可行

性判定函数和上界函数等必要的函数,并将此函数用于解0-1背包问题.

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

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

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

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

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

点击查看答案

第4题

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

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

印制电路板将布线区域划分成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!".

点击查看答案

第5题

所谓半无穷范围查询（semi-infinite range query)，是教材8.4节中所介绍一般性范围查询的特例，具

所谓半无穷范围查询(semi-infinite range query)，是教材8.4节中所介绍一般性范围查询的特例，具体地，这里的查询区域是某一侧无界的广义矩形区域，比如R=[-1，+1]x[0，﹢∞)，即是对称地包含正半y坐标轴、宽度为2的一个广义矩形区域，当然，对查询的语义功能要求依然不变——从某一相对固定的点集中，找出落在任意指定区域R内部的所有点。

范围树(176页习题[8-20])稍作调整之后，固然也可交持半无穷范围查询，但若能针对这一特定问题所固有的性质，改用优先级搜索树(priority search tree，PST)之类的数据结构，则不仅可以保持O(r+logn)的最优时间效率，而且更重要的是，可以将空间复杂度从范围树的O(nlogn)优化至O(n)。

如图x10.3所示，优先级搜索树除了首先在拓扑上应是一棵二叉树，还同时遵守以下三条规则。

①首先，各节点的y坐标均不小于其左右孩子(如果存在)——因此，整体上可以视作为以y坐标为优先级的二叉堆。

②此外，相对于任一父节点，左子树中节点的x坐标均不得大于右子树中的节点。

③最后，互为兄弟的每一对左、右子树，在规模上相差不得超过一。

a)试按照以上描述，用C/C++定义并实现优先级搜索树结构;

b)试设计一个算法，在O(nlogn)时间内将平面上的n个点组织为一棵优先级搜索树;

c)试设计一个算法，利用已创建的优先级搜索树，在O(r+logn)时间内完成每次半无穷范围查询，其中r为实际命中并被报告的点数。

点击查看答案

第6题

问题描述:现有n种不同形状的宝石,每种n颗,共n颗.同一种形状的n颗宝石分别具有n种不同的颜色中

问题描述:现有n种不同形状的宝石,每种n颗,共n颗.同一种形状的n颗宝石分别具有n种不同的颜色中的一种颜色.欲将这n²颗宝石排列成n行n列的一个方阵,使方阵中每行和每列的宝石都存n种不同形状和n种不同颜色.试设计一个算法,计算出对于给定的,有多少种不同的宝右排列方案.

算法设计:对于给定的n计算出不同的宝石排列方案数.

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

结果输出:将计算的宝石排列方案数输出到文件output.txt.

点击查看答案

第7题

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

点击查看答案

第8题

一般图搜索过程是状态空间的一般图搜索算法，它具有通用性，盲目搜索和启发式搜索都是该过程的一个特例，各种搜索策略的主要区别在于对OPEN表中节点的排列顺序不同。（)

点击查看答案

第9题

问题描述:假设有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.

点击查看答案

第10题

Apriori挖掘算法描述正确的是（)。

A.通过使用先验原理对搜索空间进行剪枝，解决了候选频繁集组合爆炸的问题

B.候选集的产生：通过前一次迭代的(k-1)项频繁集产生新的k项候选频繁集

C.候选项集的剪枝：采用基于支持度的剪枝。原理：如果一个项是频繁集，则它的所有子集一定也是频繁集

D.规则产生：每个k项频繁集会产生多达2^k-2个关联规则，需要基于置信度进行剪枝

点击查看答案

长沙概率教育科技有限公司版权所有 ©2024

湘ICP备20014581号湘公安备案43019002002117号营业执照

违法和不良信息举报电话：400-118-7898

举报/反馈/投诉邮箱：deng＃ujigu.com（请将＃替换成@）