题目
以下不属于贪心算法的是（ ）A) Dijkstra算法B) Prim算法C) 折半查找算法D) 哈夫曼编码[1]
以下不属于贪心算法的是（ ）
A) Dijkstra算法
B) Prim算法
C) 折半查找算法
D) 哈夫曼编码[1]
题目解答
答案
答案：C) 折半查找算法
解析：
贪心算法是在对问题求解时，总是做出在当前看来是最好的选择，即不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。Dijkstra算法用于求解图中的最短路径问题，Prim算法用于找到最小生成树[2]，哈夫曼编码则用于数据压缩[3]，这三种算法都涉及到在每步选择中追求局部最优的策略。而折半查找算法，是一种在已排序的数组中查找特定元素的方法，它通过比较数组中间元素和目标值来消除不必要的搜索区域，这属于分治[4]策略而非贪心算法。因此，折半查找算法不是一个贪心算法。
解析
贪心算法的核心在于每一步都选择当前局部最优解，期望最终得到全局最优解。其关键特征是贪心选择性质和最优子结构性质。而分治策略则通过分解问题为子问题，分别解决再合并结果。
本题需判断四个算法中哪一种不属于贪心算法。需明确：
- Dijkstra算法（单源最短路径）：每步选择当前未访问的最近顶点扩展。
- Prim算法（最小生成树）：每步选择当前最小权值的边连接。
- 哈夫曼编码（数据压缩）：每步合并当前两个最小频率的节点。
- 折半查找：通过分治思想缩小搜索范围，与贪心无关。
选项分析
A) Dijkstra算法
- 贪心选择：每一步从未访问的顶点中选择距离起点最小的顶点，扩展其邻接边。
- 局部最优：保证当前路径的最短性，最终得到全局最短路径。
B) Prim算法
- 贪心选择：每一步从已选顶点集到未选顶点集中选择权值最小的边扩展。
- 局部最优：逐步构建最小生成树，保证最终总权值最小。
C) 折半查找算法
- 分治思想：将有序数组不断对半分割，比较中间元素后排除一半区域。
- 非贪心：未在每一步选择局部最优解，而是通过递归缩小问题规模。
D) 哈夫曼编码
- 贪心选择：每一步合并当前两个最小的权值节点，构建最优前缀码。
- 局部最优：保证最终编码总长度最小。