Python3 回朔法完成作业分配

我会带着你远行 2022-06-17 10:55 108阅读 0赞

学号:S201625005
    姓名：梁勋
    联系电话：13126734215
    运行环境：MacOS serria 10.12.4 Beta (16E163f)
    程序语言：Python3

分析设计：
    
    有n份作业分配给n个人去完成，每人完成一份作业。
    假定第i个人完成第j份作业需要花费cij时间，cij>0,1≦i,j≦n。试设计一个回溯算法，将n份作业分配给n个人完成，使得总花费时间最少。
    
    这是一个寻找最优解的问题，通常的解决办法就是穷举出所有结果，找出最优解
    
    数据结构：
    
    输入数据来源于文件，input_assign04_o*.dat.
    文件内是n*n矩阵的元素，每行的元素代表完每个工人成该任务所需要的时间，每列代表某个工人完成每个工作需要的时间，读出的数据放在matrix中。
    matrix[i][j]表示第j个工人完成第i个任务需要的时间。
    
    Class Worker 中
    使用user_distributed来标记在某一次求解中某工人是否被分配了任务
    使用user_work来记录每次找到更适合的解的时候，工人工作分配情况
    使用min_cost来记录最小的时间消耗和
    使用n来记录用户或者作业的数量，题设中二者相等
    
    初始化函数中完成从文件中读取数据，初始化相关变量的工作
    back_track函数为回朔算法的主体部分deep 表示当前分配到第几个任务了，cost用来记录本次求解的花费情况
    write_into_file函数将结果写入文件

附上代码：

class Worker:
    
        input_file = ''
        output_file = ''
        n = 0  # 矩阵大小n*n
        matrix = []  # 存放每人解决没个问题时间的矩阵
        user_distributed = []  # 用户是否分配了工作
        min_cost = 8000  # 默认一个最大的时间消费值
        user_work = []  # 接受用户分配的工作
    
        # 初始化必要参数
        def __init__(self, input_file, output_file):
            self.input_file = input_file
            self.output_file = output_file
            with open(self.input_file) as file:
                for line in file:
                    # print(line)
                    data_source = line.split(',')
                    temp = []
                    for time in data_source:
                        temp.append(int(time))
                    self.matrix.append(temp)
    
            self.n = len(self.matrix)
    
            # 初始化 工人是否分配标记 工人最有分配结果
            for i in range(self.n):
                self.user_distributed.append(0)
                self.user_work.append(0)
    
        # 回朔法寻找最优解
        def back_track(self, deep, cost):
            if deep == self.n:
                if cost < self.min_cost:
                    self.min_cost = cost
                    for k in range(self.n):
                        self.user_work[k] = self.user_distributed[k]
                # print(self.user_distributed)
                # print('到底了 花费时间为：', cost)
                return
            else:
                for i in range(self.n):
                    if self.user_distributed[i] == 0:  # 没有分配工作的人
                        self.user_distributed[i] = deep+1  # 标记当前公认已经被标记分配了工作
                        time = self.matrix[deep][i]
                        self.back_track(deep+1, cost+time)
                        self.user_distributed[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')
    
    
    # 算法启动
    # input_file = 'input_assign04_01.dat'
    # input_file = 'input_assign04_02.dat'
    input_file = 'input_assign04_03.dat'
    # output_file = 'output_01.dat'
    # output_file = 'output_02.dat'
    output_file = 'output_03.dat'
    worker = Worker(input_file,output_file)
    worker.back_track(0, 0)
    print(worker.min_cost)
    print(worker.user_work)
    
    worker.write_into_file() 测试结果： 输入》》》 10,12,20,30,18
    23,30,8,12,22
    11,21,23,40,16
    33,34,23,19,20
    21,32,11,14,21 输出》》》 最优解消耗总时间为：65
    第1位工人完成第3份工作
    第2位工人完成第1份工作
    第3位工人完成第2份工作
    第4位工人完成第5份工作
    第5位工人完成第4份工作 
     本算法是基于穷举解决该问题的，之后对该回朔算法做了剪枝优化，文章链接如下： http://blog.csdn.net/liangxun0712/article/details/70808210