Python3 回朔法解决作业分配问题（剪枝优化）

灰太狼 2022-06-17 12:52 115阅读 0赞

本文是在上次的基础上做的优化，解决了穷举结果的尴尬

文章链接：Python3 回朔法解决作业分配问题（http://blog.csdn.net/liangxun0712/article/details/70598467）

废话不多说，直接上优化后的代码

class Worker:
        max = 0  # 上界 通过贪心算法找出近似值
        min = 0  # 下界 由每组的最小值组成
        pt_nodes = []  # 存放可扩展的节点
        input_file = ''  # 输入文件名
        output_file = ''  # 输出文件名
        matrix = []  # 存放数据矩阵  行为单个任务 每个工人 完成所要的时间
        n = 0  # 数据矩阵的大小 n*n
        min_cost = 10000
        worker_mark = []  # 标记工人是否被分配了任务
    
        #  初始化参数
        def __init__(self, input_file, output_file):
            self.input_file = input_file
            self.output_file = output_file
            self.read_data_from_file()
            self.n = len(self.matrix)
            self.get_low_limit()
            self.get_up_limit()
    
            print(self.matrix)
            print(self.n)
            print(self.max)
            print(self.min)
    
        #  从文件中读取数据 初始化数据矩阵
        def read_data_from_file(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)
    
        #  获取数据下界  最小值之和
        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)
            # 贪心算法 取得 近似最优解
            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 self.min_cost > total:
                    self.min_cost = total
                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] = 1
                        self.branch_limit(deep+1, total+temp[i])
                        self.worker_mark[i] = 0
    
    
    input_file = 'input_assign05_01.dat'
    # input_file = 'input_assign05_02.dat'
    # input_file = 'input_assign05_03.dat'
    output_file = 'output_01.dat'
    # output_file = 'output_02.dat'
    # output_file = 'output_03.dat'
    
    worker = Worker(input_file, output_file)
    worker.init_worker()
    worker.branch_limit(0, 0)
    print(worker.min_cost)