归档：2021/12 - Hi AM1ng！

回溯算法是一种选优搜索法，按选优条件向前搜索，以达到目标。简单的说是在搜索过程中寻找问题的解，当发现已不满足求解条件时，就回溯返回，尝试别的路径。

当探索到某一步时，发现原先选择不是目前的最优解或不满足问题条件时，就退回一步重新选择，并减去当前步骤的节点对应的值，这种方法为回溯法

回溯法解题步骤
(1)针对所给问题，确定问题的解空间：首先应明确定义问题的解空间，问题的解空间应至少包含问题的一个（最优）解。

(2)确定结点的扩展搜索规则 

(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

AM1ng’s Algorithm Blog！

实验题目：最小重量机器设计问题

设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j 处购得的部件i的重量，cij是相应的价格。试设计一个算法，给出总价格不超过d的最小重量机器设计。
输入格式：
第一行有3 个正整数n ，m和d，接下来的2n 行，每行n个数。前n行是c，后n行是w。
输出格式:
输出计算出的最小重量，以及每个部件的供应商

算法描述

void BackTrack(int t)
{
    if(t==n)//到达最后一层
        {
            for(int i=1; i<=m; i++)//遍历所有叶子节点
            {
                cw+=w[t][i];
                cc+=c[t][i];
                x[t]=i;
                if(cc<=max_c&&cw<bestw)//若费用不超过最大费用并且重量小于之前的最优解
                 {           
                    //更新最优解
                    bestw=cw;
                    for(int j=1; j<=n; j++)
                    bestx[j]=x[j];
                }
                cc-=c[t][i];//返回上一层
                cw-=w[t][i];
                x[t]=0;
                }
             }
else//未到达最后一层
    {
        for(int i=1; i<=m; i++)//遍历该层节点
            {
                x[t]=i;
                cw+=w[t][i];
                cc+=c[t][i];
                if(cc<max_c&&cw<bestw)//费用小于最小费用重量小于最优解时进入下一层
                    {
                        BackTrack(t+1);
                    }
            cc-=c[t][i];//返回上一层
            cw-=w[t][i];
            x[t]=0;

                }
            }
        }

思路描述

1.回溯法

初始化供应商数量及部件数量，然后初始化部件的一些属性作为测试数据。程序关键点是中间变量的总价值取较小的那个，
总重量与最小重量c的比对是否达到最小，最优。

2.算法解释

利用总长为l，利用数组存储每一个程序占用大小，每存储一个程序，总长l减去对应存储进去程序所需占用的大小，
此时计数器count加一，每次循环更新剩余的l的长度，判断是否够存储下一个程序。

贪回溯法心得体会

回溯法模板

void Backtrack(int t)
{//以深度优先的方式遍历第t层中的某棵子树
    if(t>n) { Output(x); return; }
    if (……) {  
        x[t]=1; Backtrack(t+1);
     }
    if (……)  {  
    x[t]=0; Backtrack(t+1);
     }
}

回溯法是一种选优搜索法，即探索与回溯法，又称为试探法，安选优条件向前搜索，以达到目标。
如果探索到某一步时，发现无法达到最优解或者无解，则退回到上一步，即回溯，直到选出最优解为止。
回溯过程中之前走到的位置，可以是上个选择，也可以是根据算法自定条件的位置，甚至可以是原点，但是一般不考虑原点，会出现死循环。
回溯算法解题的一个显著特征，是在搜索解的过程中动态的产生问题的解空间。在任何时候，算法只保存从根节点到当前扩展结点的路劲。
如果解空间树中从根节点到叶节点的最长路径的长度为h(n),则回溯法所需要的计算空间通常为O(h(n))。

More info: 回溯法

AM1ng’s Algorithm Blog！

实验题目： 最小重量机器设计问题

算法描述

思路描述

贪回溯法心得体会

See U next time！

实验题目：最小重量机器设计问题