哈工大算法设计与分析期末试题解析

试题内容来自https://www.cnblogs.com/fyunaru/archive/2019/07/02/11123804.html

本文基于该试题添加了解析，仅供参考

1.A*算法一定可以得到最优解。正确

A*算法定义：

（1）使用最佳优先策略搜索

（2）节点n的代价函数：f(n)=g(n)+h(n)，g(n)是起点到节点n的最短路径代价，h(n)是节点n到目标节点的估计代价

（3）h(n)0，x > x0时，c1*g(x) 0，x > x1时，g(x) < c*h(x)

当x>max(x0,x1)时，f(x) f(x) < c2*c*h(x) = C*h(x)，其中C=c2*c

因此f(x) = o(h(x))

3.写出0-1背包问题的输入规模和时间复杂性

输入：C>0, w_i>0, v_i>0, 1