经典问题的回溯算法
在生活实际中有些问题是不能用数学公式去解决的,它需要通过一个过程,此过程要经过若干个步骤才能完成,每一个步骤又分为若干种可能;同时,为了完成任务,还必须遵守一些规则,但这些规则无法用数学公式表示,对于这样一类问题,一般采用搜索的方法来解决,回溯法就是搜索算法中的一种控制策略,它能够解决许多搜索中问题。该算法的基本思想方法是:在搜索过程中,由于求解失败,为了摆脱当前失败状态,返回搜索步骤中的上一点,去寻求新的路径,以求得答案。要返回搜索,那么前进中的某些状态必须保存,才能使得退回到某种状态后能继续向前。保存状态的比较好的方法,采用一种叫“栈”的数据存放方式,即将前进中的状态象“栈”一样一层层堆放,取出时从最上层一一取出。本节中重点介绍用数组实现栈的功能,存放前边