Go语言视频零基础入门到精通

五菱

定义：
    也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：
   从一条路往前走，能进则进， 不能进则退回来，换一条路再试。用回溯算法解决问题的一般步骤为：

　　一、定义一个解空间，它包含问题的解。

　　二、利用适于搜索的方法组织解空间。

　　三、利用深度优先法搜索解空间。

　　四、利用限界函数避免移动到不可能产生解的子空间。
  
   问题的解空间通常是在搜索问题的解的过程中动态产生的，这是回溯算法的一个重要特性。回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。

    回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。
    而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。

    这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。


最佳调度问题：
描述：
    假设有N个任务由M个可并行工作的机器来完成。完成任务t需要时间x，试设计最佳调度方案，使得完成全部任务的时间最早

输入：1.任务数N；2.机器数M；3.随机序列长度t,其中t=x表示第i个任务完成需要时间x。

输出：
1. 开销时间besttime，表示最佳调度需要时间；
2.最佳调度序列bestx[]，其中bestx=x，表示将第i个任务分配给第x个机器执行。


解空间的表示：一个深度为N的M叉树。

基本思路：
    搜索从开始结点（根结点）出发，以DFS搜索整个解空间。每搜索完一条路径则记录下besttime 和bestx[]序列,开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处向纵深方向移至一个新结点，并成为一个新的活结点，也成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向扩展，则当前扩展结点就成为死结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点；直至找到一个解或全部解。


代码:

import java.util.Random;
public class BestSchedule {
    int N;        //表示任务数
    int M;        //机器数
    int best;     //最优值
    int[] t;      //每个任务所需的时间序列
    int[] len;    //记录每台机器已经安排的时间
    int[] x;      //当前路径
    int[] bestx;  //最优调度：
    public static void main(String[] args) {
     BestSchedule bs =new BestSchedule();
     bs.showTest();
    }
    void showTest()
    {
        N=15; // 任务数
        M=6; //机器数目
        Random r =new Random();
        t=new int [N]; //每个任务的时间
        for (int i =0;i< N;i++)
        {
            t=r.nextInt(5*N);
            //sum+=t;
        }
        len =new int [M];   //记录每台机器已经安排的时间
        best = Integer.MAX_VALUE;
        bestx=new int [N];
        x =new int[N];
        Long startTime = System.nanoTime();
        backtrack(0);
        Long endTime = System.nanoTime();
        System.out.println("Totle time is" +(endTime - startTime) + " ns");
        System.out.println("best time:");
        System.out.println(best);
        System.out.println("each job costs:");
        for (int i=0;i< N;i++)
            System.out.print(t+"  ");
        System.out.println();
        System.out.println("best schedule:");
        for (int i=0;i< N;i++)
            System.out.print(bestx+"  ");
        }
    //回溯搜索
    void backtrack (int dep)
    {
        if (dep==N)//全部任务安排完毕
        {
            int tmp = comp();//此次调度的最大值
            if(tmp< best)
            {
                best=tmp;//最优值
                for(int i=0;i< N;i++)
                {
                    bestx=x;//最佳调度序列
                }
            }
            return;
        }
        for(int i=0;i< M;i++)
        {
            len+=t[dep];//将第dep个任务安排给第i个机器执行,增加第i个机器的安排时间
            x[dep]=i+1;//记录,输出时机器号从1开始
            if(len< best)
            {      
                backtrack(dep+1);//安排下一个任务               
            }
            len-=t[dep];   //回朔
        }
    }
    int comp()//全部任务安排完毕后,比较每台机器安排的时间,找出最大值
    {
        int tmp =0;
        for (int i=0;i< M;i++)
        {
            if(len>tmp)
            {
                tmp=len;
            }
        }
        return tmp;
      
    }
}