如果问题存在最优解,则下面几种搜索算法中,()可以认为是“智能程度相对比较高”的算法。
A.有界深度优先搜索
B.启发式搜索
C.深度优先搜索
D.宽度优先搜索
A.有界深度优先搜索
B.启发式搜索
C.深度优先搜索
D.宽度优先搜索
(1)写出可行区域D中的所有顶点;
(2)证明若一个线性规划问题在两个顶点上达到最优值,则此线性规划问题必有无穷多个最优解。
设bi>0,i=1,…,m;cj≥0,j=1,…,n(m<n)。写出下面线性规划的对偶问题,证明对偶问题有唯一最优解,并找出对偶问题的这一最优解。
证明下列规划为凸规划:
问:该问题是否存在最优解?
其中A是一个mxn的矩阵,秩(A)=n。符号||x||2表示向量x的模的平方,即||x||2=xTx。
A.res1表示最优函数取值,res2表示最优解
B.res1表示最优解,res2表示最优函数值
C.res1表示最优解,res2表示中止标识
D.res1表示中止标识,res2表示最优解
A.线性在直角坐标系中表现为一根直线
B.线性是非线性在一定条件下的特例
C.人们通过傅里叶变换、拉普拉斯变换等方法来解决线性问题
D.线性作用在自然界中极其少见
用罚函数法求解问题
(1)写出ck=0,1,10时相应的增广目标函数,并画出它们对应的图形;
(2)取ck=k-1(k=1,2,...)求出近似最优解的迭代点列;
(3)利用(2)求问题的最优解。
印制电路板将布线区域划分成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!".
装载问题描述如下:有一批共n个集装箱要装上艘载重量为c的轮船,其中集装箱i的重量为wi.找出一种最优装载方案,将轮船尽可能装满,即在装载体积不受限制的情况下,将尽可能重的集装箱装上轮船.
算法设计:对于给定的n个集装箱的重量和轮船的重量,计算最优装载方案.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是集装箱数,c是轮船的载重量.接下来的1行中有n个正整数,表示集装箱的重量.
结果输出:将计算的最大装载重量输出到文件output.txt.
问题描述:设p是奇素数,1≤x≤p-1,如果存在一个整数y(1≤y≤p-1),使得x=y2(modp),则称y是x的模p平方根.例如,63是55的模103平方根.试设计一个求整数x的模p平方根的拉斯维加斯算法.算法的计算时间应为logp的多项式.
算法设计:设计一个拉斯维加斯算法,对于给定的奇素数p和整数x,计算x的模p平方根.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数p和x.
结果输出:将计算的x的模p平方根输出到文件output.txt.当不存在x的模p平方根时,输出0.