算法第四次作业-回溯法求解作业分配问题

一、运行环境：

Win7、Spyder、Python3.7

二、运行过程说明:

数据文件格式：输入数据来源于文件，input_assign04_0*.dat。文件内是n*n矩阵的元素，每行的元素代表每个工人完成该任务所需要的时间，每列代表某个工人完成每个工作需要的时间，读出的数据放在嵌套了列表的列表matrix中。

输入格式：

在Spyder中运行程序，输入测试数据集文件编号。

或者在cmd中：

输出：

 

三、算法设计

3.1问题描述：

n份作业分配给n个人去完成，每人完成一份作业。假定第i个人完成第j份作业需要花费cij时间，cij>0,1≦i,j≦n。试设计一个回溯算法，将n份作业分配给n个人完成，使得总花费时间最少。

3.2解题思路：

通过将问题进行适当的转化，得出解空间树为排列树。这棵树的每条完整路径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况，找出能得到最小花费的结果。其中，通过构造约束函数，可以删除一些不可能的解，从而大大提升程序效率。

（1）写出作业分配问题的解空间。

解的形式：（x1 ,x2,x3,…,xn ），其中，xi =1,2,3,…,n表示第i个人安排的工作号，解空间为{（x1 ,x2,x3,…,xn ）| xi =1,2,3,…,n ，0 < i < n+1}。

（2）以n=3为例，画出作业分配问题的解空间树。

 

（3）用Python语言使用递归回溯法求解作业分配问题，求解时，不仅求出所花费的最小总费用（即最优值），还求出最佳的作业分配方案（即最优解）。

3.3数据结构的选择：

参数：

1. 字符串类型input_file 保存输入文件名
2. 字符串类型output_file保存输出文件名
3. n是数据矩阵的大小 n*n
4. 列表matrix存放数据矩阵，大小为n*n，为单个任务每个工人完成所要的时间。其中的每行代表每个工人完成该任务所需要的时间，每列代表某个工人完成每个工作需要的时间。matrix[i][j]表示第j个工人完成第i个任务需要的时间。
5. 列表worker_mark，长度为n，标记每位工人是否被分配了任务0/1
6. 列表user_work，长度为n，保存每次找到更适合的解的时候，编号从1~n的工人们他们各自被分配的工作的编号
7. 列表pt_nodes存放可扩展的节点
8. max 是花费的上界，通过贪心算法找出近似值
9. min是花费的下界，由每组的最小值组成
10. min_cost 保存最终求解的最小花费

类 Worker 中的函数：

1. 初始化函数__init__完成初始化相关变量的工作
2. init_worker初始化工人分配标记
3. read_data完成从文件中读取数据 初始化数据矩阵
4. get_low_limit利用最小值之和获取数据下界
5. get_up_limit使用贪心算法获取数据上界 
6. branch_limit剪枝优化后的回朔算法，deep 表示当前分配到第几个任务了，total用来记录本次求解的花费情况
7. write_into_file函数将结果写入文件

四、算法详细描述：

4.1步骤

首先：

1. 描述解的形式，定义一个解空间，它包含问题的所有解。
2. 构造状态空间树。
3. 构造约束函数（用于杀死节点）。

然后通过深度优先搜索思想完成回溯，完整过程如下：

1. 设置初始化方案。
2. 变换方式去试探，若全部试完则转7.
3. 判断此法是否成功（通过约束函数），不成功则转2.
4. 试探成功则前进一步再试探。
5. 正确方案还未找到则转2。
6. 已找到一种方案则记录并打印。
7. 退回一步（回溯），若未退到头则转2。
8. 已退到头则结束或打印无解。

可以概括为以下一般化的步骤：

/**

 * output(x)     记录或输出得到的可行解x

 * constraint(t)   当前结点的约束函数

 * bount(t)      当前结点的限界函数

 * @param t  t为当前解空间的层数

 */

void backtrack(int t){

           if(t >= n)

                    output(x);

           else

                    for (int i = t; i <= n; i++) {

                             swap(x[t], x[i]);

                             if(constraint(t) && bount(t))

                                       backtrack(t+1);

                             swap(x[t], x[i]);

                    }

}

4.2使用python编写的代码：

# -*- coding: utf-8 -*-

"""

Created on Tue Nov  5 16:24:27 2019

@author: Administrator

"""

class Worker:

    input_file = ''  # 输入文件名

    output_file = ''  # 输出文件名

    n = 0  # 数据矩阵的大小 n*n

    matrix = []  # 存放数据矩阵  行为单个任务 每个工人 完成所要的时间

    worker_mark = []  # 标记每位工人是否被分配了任务0/1

    user_work = []  # 保存编号从1~n的工人们他们各自被分配的工作的编号

    pt_nodes = []  # 存放可扩展的节点

    max = 0  # 上界 通过贪心算法找出近似值

    min = 0  # 下界 由每组的最小值组成

    min_cost = 10000    #保存最终最小花费

    #  初始化参数

    def __init__(self, input_file, output_file):

        self.input_file = input_file

        self.output_file = output_file

        self.read_data()

        self.n = len(self.matrix)

        self.get_low_limit()

        self.get_up_limit()

        print("输入数据为：")

        print(self.matrix)

        print("人数：",self.n)

    #  从文件中读取数据 初始化数据矩阵

    def read_data(self):

        with open(self.input_file) as source:

            for line in source:

                data_cluster = line.split(',')

                temp = []

                for value in data_cluster:

                    temp.append(int(value))

                self.matrix.append(temp)

                #print(self.matrix)

    #  获取数据下界  最小值之和

    def get_low_limit(self):

        for i in range(self.n):

            self.min += min(self.matrix[i])

    #  获取数据上界  贪心算法

    def get_up_limit(self):

        #  初始化工人使用标记

        worker_mark = []

        for i in range(self.n):

            worker_mark.append(0)

            self.user_work.append(0)

        # 贪心算法 取得 近似最优解

        for i in range(self.n):

            temp = self.matrix[i]

            min_value = 5000

            index = 0

            for k in range(self.n):

                if worker_mark[k] == 0 and min_value > temp[k]:

                    min_value = temp[k]

                    index = k

            worker_mark[index] = 1  # 标记工人是否被分配

            self.max += min_value  # 累积上限值

    #  初始化工人分配标记

    def init_worker(self):

        self.worker_mark = []

        for i in range(self.n):

            self.worker_mark.append(0)

    #  剪枝优化后的回朔算法

    def branch_limit(self, deep, total):

        if deep == self.n:#到了最后一层

            # print('最短距离', total)

            if  total<self.min_cost: #花费比最小值小，记录

                self.min_cost = total

                #记录

                for i in range(self.n):

                    self.user_work[i]=self.worker_mark[i]

            return

        #还没有到最后一层

        temp = self.matrix[deep]

        for i in range(self.n):

            if self.worker_mark[i] == 0:

                if (temp[i] + total) > self.max:  ##剪枝 使用约束函数，超出上界的节点直接舍弃

                    continue

                else:#继续探索

                    self.worker_mark[i] = deep+1

                    self.branch_limit(deep+1, total+temp[i])

                    self.worker_mark[i] = 0             

 # 将算法执行结果存入文件中

    def write_into_file(self):

        file = open(self.output_file, 'a')

        file.write('最优解消耗总时间为：' + str(self.min_cost) + '\n')

        for i in range(self.n):

            file.write('第' + str(i+1) + '位工人完成第' + str(self.user_work[i]) + '份工作\n')

x=input("请输入文件编号（1~6）：")

input_file = 'input_assgin04_0'+x+'.dat'

output_file = 'output_0'+x+'.dat'

l1=[1,2,3,4,5]#工人编号

worker = Worker(input_file, output_file)#对象

worker.init_worker()#初始化

worker.branch_limit(0, 0)

print("最小花费：",worker.min_cost)

print("分配结果：")

print("工人编号：",l1)

print("工作编号：",worker.user_work)

worker.write_into_file()

五、算法分析

由于本问题的解空间是排列树，这类排列树通常有n!个叶结点。所以最坏时间复杂度是O(n!)；

由于需要额外的数组保存选择的路径，所以最坏的空间复杂度是O(n)。