问题描述:欧氏旅行售货员问题是对给定的平面上n个点确定一条连接这n个点的长度最短的哈密顿回
算法设计:给定平面上n个点,计算这n个点的最短双调TSP回路.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n,表示给定的平面上的点数.在接下来的n行中,每行2个实数,分别表示点的x坐标和y坐标.
结果输出:将计算的最短双调TSP回路的长度(保留2位小数)输出到文件output.txt.
算法设计:给定平面上n个点,计算这n个点的最短双调TSP回路.
数据输入:由文件input.txt给出输入数据.第1行有1个正整数n,表示给定的平面上的点数.在接下来的n行中,每行2个实数,分别表示点的x坐标和y坐标.
结果输出:将计算的最短双调TSP回路的长度(保留2位小数)输出到文件output.txt.
设G是一个有n个顶点的有向图,从顶点i发出的边的最大费用记为max(i).
(1)证明旅行售货员回路的费用不超过.
(2)在旅行售货员问题的回溯法中,用上面的界作为bestc的初始值,重写该算法,并尽可能地简化代码.
设G是一个有n个顶点的有向图,从顶点i发出的边的最小费用记为min(i).
(1)证明图G的所有前缀为x[1,i]的旅行售货员问路的费用至少为:
式中,a(u,v)是边(u,v)的费用.
(2)利用上述结论设计一个高效的上界函数,重写旅行售货员问题的回溯法,并与主教材中的算法进行比较.
A.生产要素包括劳动、土地、资本和企业家才能
B.生产要素在世界上均匀分布
C.企业家才能是种无形的生产要素
D.生产要素的配置问题是“生产什么”、“如何生产”、及“为谁生产”的问题
在扩大的欧氏平面上,给出了的欧氏直线在仿射坐标中的方程,求由它确定的射影直线在齐次坐标中的方程,并求出它上面的无穷远点:
(1)x+2y-1=0;(2)x=0;
(3)y=1;(4)3x-2y=0.
A.加入更多层,使神经网络的深度增加
B.有维度更高的数据
C.当这是一个图形识别的问题时
D.以上都不正确
a)若套用Kruskal或Prim算法构造EMST(G),各需多少时间?
b)试设计一个算法,在o(nlogn)时间内构造出EMST(G);
c)试证明你的算法已是最优的(亦即,在坏情况下,任何此类算法都需要o(nlogn)时间)。