贪心算法马的遍历c程序解析！

1.此循环条件为什么可以去除无用结点。

答：因为首先sortnode将8个可能的“下一步”（也就是hn）按照其潜力（也就是waysout）从大到小排序了，因此从hn[0]开始，遍历到某一个hn[i]，如果其waysout已经是0或-1，则hn[i+1]直到hn[7]的waysout都是0或-1。从而可以跳过一些waysout是0或-1的死路。

【waysout的意思就是从某个节点出发能走到的下一步的数量。最小0，最大8】

2。贪心算法提高时间效率体现在这？

答：看遍整个代码，也就这里能稍~微提高一点效率。也就是每次先从潜力最大的下一步开始搜索。

贪婪法是一种不追求最优解，只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解，因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择，而不考虑各种可能的整体情况，所以贪婪法不要回溯。

贪婪算法的一般方法

1、问题描述

它有n个输入，而它的解就由这n个输入的某个子集组成，只是这个子集必须满足某些事先给定的条件。

2、约束条件 那些必须满足的条件称为约束条件。

3、可行解 满足约束条件的子集称为该问题的可行解。

4、目标函数 事先给定的衡量可行解优劣的量度标准，通常以函数的形式给出，称为目标函数。

5、最优解 使目标函数取极值（极大或极小）的可行解，称为最优解。

6、子结构模式 贪心技术中，问题的最优一般是原输入的子集，获取最优子集的贪心方法为子结构模式

7、有序模式 通过计算已有的判定而得出的最优条件，可以为下一步的判定提供依据，这种形式的贪心算法称为有序模式。

8、贪婪算法求解思想（分步处理）

�8�4 根据题意，选取一种量度标准；

�8�4 然后按这种量度标准对这n个输入排序，并按序一次输入一个量。

�8�4 如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生一个可行解，则不把此输入加到这部分解中。

这种能够得到某种意义下的最优解的分级处理方法称为贪心算法。

---