回溯算法

1 算法原理

回溯法有通用解法的美称，对于很多问题，如迷宫等都有很好的效果。回溯算法实际上一个类似枚举的深度优先搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回（也就是递归返回），尝试别的路径。许多复杂的，规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。回溯法说白了就是穷举法。回溯法一般用递归来解决。

2 算法流程图

过程：
1 搜索第N层。
2 判断第N可行的值是那些值。value1,value2,value3,value4…valueM
3 给第N层，依次赋值{value1,value2,value3,value4…valueM}
4 判断第N层赋值valueM，判断条件是否还满足。f(N,valueM)
5 如果f(N,valueM) == true。向下再次搜索(N+1,valueM)
6 回退相关资源

算法骨架：

//限制条件
function check(n,value,result)
{
    return false;
    return true;
}

function search(n,result)
{
    if(n > 总层数)
    {
         echo '可行的值';
         return;
    }

    //找到第N层，可以赋值valueM
    values = array(value1,value2,value3,value4...valueM);

    //给第N依次赋值
    for(value in values)
    {
        //给第N层赋值
        result[n] = value;

        //判断是否限制条件,然后向下一层搜索
        if(check(n,value,result))
        {
           search(n+1,result) 
        }

        //回退第N层资源

        result[n] = null;
    }

}

3 样例题

3.1 01背包问题

有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

<?php
//有编号分别为a,b,c,d,e的五件物品，它们的重量分别是2,2,6,5,4，它们的价值分别是6,3,5,4,6，现在给你个承重为10的背包，如何让背包里装入的物品具有最大的价值总和？

$weight = array(2,2,6,5,4); //物品重量
$price = array(6,3,5,4,6); //物品值
$packageWeight = 10;//背包重量

$maxPrice = 0;//结果
$maxResult = array();//结果的保留至

//限制条件，1-n的总质量<=背包总重量
function check($n,$result)
{/*{{{*/
    $totalWeight = 0;
    global $weight;
    for($i = 0;$i<=$n;$i++)
    {
        if(1 != $result[$i])
        {
           continue; 
        }
        $totalWeight += isset($weight[$i]) ? $weight[$i] : 0;
    }

    //如果当前总重量<= packageWeight
    global $packageWeight;
    if($totalWeight <= $packageWeight)
    {
       return true;    
    }
    return false;
}/*}}}*/


function search($n,$result)
{/*{{{*/
    global $weight;
    $count = count($weight);
    if($n > $count - 1)
    {
        $totalPrice = 0;
        global $price;
        foreach($result as $key => $val)
        {
            if(1 != $val)
            {
                continue;
            }
            $totalPrice += isset($price[$key]) ? $price[$key] : 0;    
        }

        global $maxPrice;
        if($totalPrice > $maxPrice)
        {
            global $maxResult ;
            $maxPrice = $totalPrice;
            $maxResult = $result;
        }
        return ;
    }

    $values = array(0,1); //每一层的可以取的值都一样都是0,1。（有些搜索每层的可以的取值是不一样的）
    foreach($values as $value)
    {
        $result[$n] = $value;//第n件物品，取或者不取

        //是否满足限制条件
        if(check($n,$result))
        {
            //向下搜索
            search($n + 1,$result);

        }
        //回退相关资源
        $result[$n] = 0;
    }
}/*}}}*/

$result = array();
search(0,$result);

print_r($maxPrice);
echo "\n";
print_r($maxResult);

?>

3.2 8皇后问题

在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

<?php
// 在8×8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

function check($row,$result)
{
    if($row == 1)
    {
        return true;    
    }

    $col = $result[$row];

    //第row，和第row-1行之前的数据对比
    for($tmpRow = 1;$tmpRow <= $row -1;$tmpRow++)
    {
        //行肯定不一样。如果存在同列或者同斜线。则不能放置
        //col列，已经在第tmpRow放了皇后
        if($col == $result[$tmpRow])
        {
            return false;    
        }

        //同斜线
        if( abs($row - $tmpRow) == abs($col - $result[$tmpRow]) )
        {
            return false;    
        }
    }

   return true;
}

function search($row,$result)
{/*{{{*/
    if($row > 8) 
    {
        print_r($result);
        return;     
    }

    $values = array(1,2,3,4,5,6,7,8);//每层可以取到的值都一样1-8
    foreach($values as $value)
    {
        //在第row行，第value列放置一个皇后
        $result[$row] = $value;

        //是否满足向下搜索条件
        if(check($row,$result))
        {
            search($row+1,$result);  
        }
        //回退条件
        $result[$row] = 0;
    }
}/*}}}*/

$result = array();
search(1,$result);

?>