回溯算法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。

现在来实际操练几题

假如我们有1,2,3,4允许数字重复有多少种排列组合,这个题我们用程序实现。

直接来代码:

$result = array();
function pailie($arr, $res = array())
{
    global $result;
    static $arr_count;
    if(empty($arr_count))
    {
        $arr_count = count($arr);
    }
    if(count($res) == $arr_count)
    {
        $result[] = $res;
        return;
    }
    foreach($arr as $key => $num)
    {
        $res[] = $num;
        pailie($arr, $res);
        array_pop($res);
    }
}

$arr = array(1, 2, 3, 4);

pailie($arr);

echo count($result) . ‘<br>‘;

foreach($result as $r)
{
    echo implode(‘,‘, $r);
    echo ‘<br>‘;
}

假如我把上一题改成数字不能重复的排列组合，我们只需要稍微改改函数：

function pailie($arr, $res = array())
{
    global $result;
    static $arr_count;
    if(empty($arr_count))
    {
        $arr_count = count($arr);
    }
    if(count($res) == $arr_count)
    {
        $result[] = $res;
        return;
    }
    foreach($arr as $key => $num)
    {
        $res[] = $num;
        //回溯的时候删掉当前这个数字
        $tm_arr = $arr;
        unset($tm_arr[$key]);
        pailie($tm_arr, $res);
        array_pop($res);
    }
}

再来一题:

有一个N阶的楼梯，一步可以上一阶或两阶。设计一个函数，传入任意正整数N，列出所有可能的走法。例如台阶数为4走法如下:
1,1,1,1
1,2,1
1,1,2
2,1,1
2,2
如果这个人腿比较长，一次有可能跨好几阶例如传入阶梯数组{3,5,7}的那么该函数如何设计呢?

个人用回溯算法解题代码如下:

$result = array();
function zoulu($n, $exist = array(), $res = array())
{
    global $result;
    if(!empty($res))
    {
        $sum = array_sum($res);
        if($sum > $n)
            return false;
        else if($sum == $n)
        {
            $result[] = $res;
        }
    }
    foreach($exist as $e_one)
    {
        $res[] = $e_one;
        zoulu($n, $exist, $res);
        array_pop($res);
    }
}

$exist = array(4, 7);
zoulu(30, $exist);

echo count($result) . ‘<br>‘;

foreach($result as $r)
{
    echo implode(‘,‘, $r);
    echo ‘<br>‘;
}

回溯算法

原文：http://blog.51cto.com/chinalx1/2111035