递归算法地优缺点.doc

word
word
2 / 10
word
递归算法的优缺点：
优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。
缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占v[j]=;
//加入活结点优先队列
MinHeapNode <type> N;
=j;
=dist[j];
(N);
}
//取下一个扩展结点
try { (E); }
//优先队列为空
catch (OutOfBounds) {break;}
}
}
word
word
8 / 8
word
(1)数值随机化算法: ß求解数值问题,得到近似解
(2)Monte Carlo算法:ß 问题准确性,但却无法确定解正确性
(3)Las Vegas算法:ß获得正确解,但存在找不到解的可能性
(4)Sherwood算法:ß保证能获得正确解
旅行售货员问题:(优先队列式分支限界法)
word
word
5 / 10
word
Type Travding (int v[])
{ MinHeapNode H(1000)；
Type Minout[N+1]；
//计算 Minout[i]=顶点 i的最小出边费用
Type Minsurn=0；//最小出边费用和
for（i=1;i＜＝n；i++）{
Min=NoEdge；
for（ j=1；j＜＝n；j++）
if（a[i][j]!=NoEdge＆＆(a[i][j]<Min || Min==NoEdge) Min=a[i][j]；
if（Min==NoEdge） return(NoEdge)； //无回路
MinOut[i]= Min；
MinSum+=Min；
}
//初始化
MinHeapNode E；
for（i= 0；i＜ n；i++）
［i］= i+ 1；
=0；
=0；
=MinSum；
Bestc=NoEdge；
while（＜n-1) //非叶结点
if（<n-1）{ //当前扩展结点是叶结点的父结点
if（a[[n-2][[n-1]]!=NoEdge ＆＆a[[n-2][1]!=NoEdge&&（+
a[[n-2]][[n-1]]+a[[n-1]][1]<
bestc || bestc==NoEdge）{
//费用更小的回路
bestc=Ecc+a[[n-2]][[n-1]]
+a[[n-1]][1]；
＝bestc；
=bestc；
++；
Insert（H,E）