实验五 回溯算法

实验目的

掌握回溯法算法的设计与分析步骤以及算法的具体实现。

实验要求

实验时间：2学时，对于给定的问题描述，生成实验报告。

实验内容

问题描述：有 $n$ 种物品，每种物品只有 $1$ 个。第 $i$ 种物品价值为 $v_i$，重量为 $w_i$，$i = 1, 2, \dots, n$。问如何选择放入背包的物品，使得总重量不超过 $B$，而价值达到最大？

1. 使用回溯算法解决问题，给出分析过程。
2. 给出算法的具体实现过程（源码及其详细注释）
3. 给出算法的运行结果。

思路

分支限界法有许多种，为了便于理解，我们这里使用课堂上介绍的代价函数来求解。虽然课堂上介绍的代价函数是针对于“背包问题”的，但依然适用于“0-1背包问题”。 对于此问题，0-1 背包。每种物品只有选与不选的选项。由此构造一棵 $n$ 层二叉树，左为1，右为0，分别代表选与不选。 因为分支限界法基于是一种基于回溯算法的优化，关于此问题，具体可以参考前篇0_1背包问题的回溯解法。本文只介绍其优化的要点。

具体些

我们把一个结点以下所有以该点为根的子树所有可行解的值叫做上界或下界，通俗来说就是这个点以下所有点可能取到的最大值或最小值。 对于0-1背包，要在给定的重量里，求的价值的最大值，是极大化问题，所以要得到一个结点的上界的函数表达，我们称之为代价函数。 回到搜索结点这里来讲，当我们访问到下层孩子结点时，我们需要考虑

1. 还能装下这个结点吗？
2. 这个结点的上界（代价函数得到的值）是否高于现在的最优解？

对于能不能装下结点的物品，显然很容易得出答案。但如何知道这个节点的上界呢？ 不妨先对这几个物品按照其价值重量比排序，可以知道，其子树最高不可能超过当前结点的价值重量比*背包剩余重量。这就是其上界了。

形式化表达，有，

代价函数 = 已装入价值 + Δ Δ：还可继续装入最大价值的上界 Δ = 背包剩余重量 × $\frac {v_{k+1}}{w_{k+1}}$ (可装) Δ = 0(不可装)

如果其上界都不能超出现在的最优解，那么就剪掉该节点的子树，直接回溯。

如何回溯

函数回溯法。 根据函数递归的性质，在选择一颗子树时，通过“函数调用自身”来进行下层搜索，直到叶子结点，函数将在统计当前路径的价值，比较最大值后自动回溯。

结果

你也可以在下方操作此程序，注意使用英文逗号分隔数字

回溯法求0-1背包

最大载重
   价值   
   重量   
             

回溯法求最优价值：155
回溯法求出的最优选择：Y,Y,Y,Y,N

源程序

var n,w;
var ans=0;
var ans_num = new Array()
var path = new Array();
var bestpath = new Array();
var a =new Array();

function pan(x,y){
    return y.vpw - x.vpw 
}

// 当前结点的代价函数
// 如果剩下的所有重量的都用在
// 当前结点的这个最大价值比上，能不能超出最优解。
function bAndB(x,wi,vl)
{
    vl+=(w-wi)*a[x].vpw;
    if(vl<=ans)
        return true
    return false
}

// 初始化，将得到的信息重量和价值push到a变量中
// 同时算出vpw，并标记其初试序号
function init(values,weights)
{
    values.map((cur,index)=>
    {
        a.push(
        {
            'val': values[index],
            'wei': weights[index],
            'vpw': values[index]/weights[index],
            'ind': index
        })
    })
    a.sort(pan)
}

function search(x,wi,vl)
{
    // 如果已经到叶子结点
    if(x>=n)
    {
        // 那么检查是否是最优解
        if(vl>ans)
        {
            ans = vl;
            // 是最优解，记录路径
            for(var i = 0; i < n ; i++)
            {
                if(path[i])
                    bestpath[i] = 'Y';
                else
                    bestpath[i] = 'N';
            }
        }
        return;
    }
    // 如果当前结点的上界仍不能超出最优解，就放弃此结点
    if(bAndB(x,wi,vl))
        return ;
    //  如果还没有超出包的最大重量，那么选择这个结点，并且继续向下搜索
    if(wi+a[x].wei<=w)
    {
        path[x] = 1;
        search(x+1,wi+a[x].wei,vl+a[x].val);
        path[x] = 0;
    }
    // 如果不能选了，就放弃这个结点的左子树，向右子树搜索
    search(x+1,wi,vl);
}

function output()
{
    for(var i=0;i<n;i++)
        {
            //统计结果，对于选中的，输出其原始序号。
            if(bestpath[i]=='Y')
                ans_num.push(a[i].ind+1)
        }
        console.log()
        document.getElementById("mv").innerHTML = ans;
        document.getElementById("bp").innerHTML = ans_num;
}

document.getElementById('submit').onclick = function(event)
{
    //每次按钮初始化
    n=0;
    w=0;
    ans=0;
    ans_num.splice(0,ans_num.length);
    path.splice(0,path.length);
    bestpath.splice(0,bestpath.length);
    a.splice(0,a.length);

    // 总重量
    w =parseInt(document.getElementById('w').value);
    
    // 每个物品的价值
    var v_str =  document.getElementById('val').value ;
    var values = v_str.split( ',' );
    values=values.map(Number);
    // 获取物品的个数
    n = values.length;
    
    //每个物品的重量
    var w_str =  document.getElementById('wei').value ;
    var weights = w_str.split( ',' );
    weights=weights.map(Number);

    // 可行性检查
    if(values.length == weights.length)
    {
        init(values,weights)
        search(0,0,0)
        output()
    }
    else
        alert('重量 和 价值 不对应，数目不同。')
}

心得体会

熟能生巧

显而易见，分支限界法能够大大降低选择的次数。 仔细观察，蛮力算法、回溯法、分支限界法，你会发现，回溯法就是在蛮力上的一种及时止损，分支限界法同样也是在回溯法上的一种及时止损。 单就分支限界法来说，若能选择合适的代价函数，则能更快地解决问题，这是十分明显的。