启发式算法（heuristic algorithm)是相对于最优化算法提出的。一个问题的最优算法求得该问题每个实例的最优解。也就是说，在允许运行时长足够长的 情况下，确保得到一个最优方案。但是大量重要的ILP和INLP问题，并不存在多项式时间的解法，因此，启发式算法可以这样定义：一个基于直观或经验构造的算法，在可接受的花费（指计算时间和空间）下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度一般不能被预计。

计算机科学的两大基础目标，就是发现可证明其执行效率良好且可得最佳解或次佳解的算法。而启发式算法则试图一次提供一或全部目标。 例如它常能发现很不错的解，但也没办法证明它不会得到较坏的解；它通常可在合理时间解出答案，但也没办法知道它是否每次都可以这样的速度求解。

有时候人们会发现在某些特殊情况下，启发式算法会得到很坏的答案或效率极差，然而造成那些特殊情况的数据组合，也许永远不会在现实世界出现。因此现实世界中启发式算法常用来解决问题。启发式算法处理许多实际问题时通常可以在合理时间内得到不错的答案。

启发式算法可分为传统启发式算法和元启发式算法。传统启发式算法包括构造型方法、局部搜索算法、松弛方法、解空间缩减算法等。 元启发式算法包括禁忌搜索算法、模拟退火算法、遗传算法、蚁群优化算法、粒子群优化算法、人工鱼群算法、人工蜂群算法、人工神经网络算法等。

该算法逐个选择离散决策变量的值，直到得到一个完整的可行解位置。该方法从部分解开始，一次只选择一个决策变量的值，经常在完成第一次可行方案时停止。

基础的构造性搜索算法，从每一个自由决策变量的离散分类开始，在每次迭代中，在当前决策解固定的情况下，一个先前的自由变量固定为一个可行值，也就是说，当我们替换以前的固定值并且采用自由变量时，为新分量所选定的值不应该产生违反约束的情况。在最简单的情况下，当没有自由变量存在时，搜索过程停止。

构造性搜索的主要难点在于，如何选择下一个待固定的自由变量并且确定它的值，而贪婪或者短视算法是解决这一问题最常见的方法。

贪婪算法的规则是，在目前已知内容的基础上，选择固定被选中概率最大的变量，从而得到更好的可行解。由于该算法在进行下次选择时只能依靠局部信息，因此在一般情况下这样做存在一定风险，在贪婪算法中一个只有少数变量固定的并且看起来变现很好的解实际上会迫使搜索进入可行空间中非常差的区域。

实际上，构造性搜索算法更适合求解大规模，并且通常是非线性的高度组合的离散模型或者需要快速求解的情况下，一般采用分支定界，分支切割等。

在搜索过程中，始终选择当前点的邻居中与离目标最近者的方向搜索。

算法过程

（1）随机选择一个初始的可能解x0 ∈D，xb=x0,P=N(xb);      //D是问题的定义域， xb用于记录到目标位置的最优解，P为xb的邻域。 （2）如果不满足结束条件，则：      //结束条件为循环次数或P为空等 （3）Begin； （4）选择P的一个子集P'，xn为P’的最优解 ；           //P’可根据问题特点，选择适当大小的子集。可按概率选择 （5）如果f(xn)