北京工业大学研究生算法作业(五)——分支限界法作业分配

2023-09-23 31 0

Readme

运行环境:
Win10+python3.7.3

IDE:Pycharm

分析设计:
有n份作业分配给n个人去完成,每人完成一份作业。
假定第i个人完成第j份作业需要花费cij时间,cij>0,1≦i,j≦n。试设计一个分支界限算法,将n份作业分配给n个人完成,使得总花费时间最少。
这是一个寻找最优解的问题,通常的解决办法就是穷举出所有结果,找出最优解。分支界限算法是为了有效的避免穷举结果,这是一个广度优先的搜索操作

数据结构:
输入数据来源于文件:input_assign04_01.dat. input_assign04_02.dat. input_assign04_03.dat. input_assign04_04.dat. input_assign04_05.dat. input_assign04_06.dat. input_assign04_07.dat.
Node 类:
self.deep = 0 # 标记该节点的深度
self.cost = 0 # 标记到达该节点的总消费
self.father = None # 标记该节点的父节点
self.value = 0 # 本节点的消费值
self.worker = None # 本节点的该任务由第几位工人完成
Node类用来存放分支树上的所有有效节点

Worker 类:
max = 0 # 上界 通过贪心算法找出近似值
min = 0 # 下界 由每组的最小值组成
pt_nodes = [] # 存放可扩展的节点 FIFO
pt_flag = 0 # 标记队列是否被使用 用于结束算法
input_file = ‘’ # 输入文件名
output_file = ‘’ # 输出文件名
matrix = [] # 存放数据矩阵 行为单个任务 每个工人 完成所要的时间
n = 0 # 数据矩阵的大小 n*n
min_leaf_node = None # 消耗最小的节点

function:read_data_from_file  从文件中读取数据get_low_limit 计算下界get_up_limit  计算上界branch_limit  执行分支界限算法output_result  结果输出到文件

算法思路:
1 将数据用n*n的矩阵来描述 M[i,j]表示第i个任务由第j位工人完成所耗时间
2 使用贪心算法计算一个近似的最优解作为上界
3 最小值求和法得到最优解的下界
4 针对第一个任务,检查每人的耗时是否超过上界,是则舍弃,否则创建节点加入队列
5 开始处理队列元素,先进先出,如果是子节点,判断是否是最优节点,否则 检查累积上下一个任务每人的耗时后是否超过上界,否则继续创建节点加入队列,是则舍弃
6 当队列处理完毕后,层层遍历最优节点的father节点,输出结果

代码

from time import sleep#分支算法执行类
class Worker:#  初始化参数def __init__(self, input_file, output_file):max = 0  # 上界 通过贪心算法找出近似值min = 0  # 下界 由每组的最小值组成pt_nodes = []  # 存放可扩展的节点pt_flag = 0  # 标记队列是否被使用 用于结束算法matrix = []  # 存放数据矩阵  行为单个任务 每个工人 完成所要的时间n = 0  # 数据矩阵的大小 n*nmin_leaf_node = None  # 消耗最小的节点self.max = maxself.min = minself.pt_nodes = pt_nodesself.pt_flag = pt_flagself.input_file = input_fileself.output_file = output_fileself.matrix = matrixself.n = nself.min_leaf_node = min_leaf_nodeself.read_data_from_file()self.n = len(self.matrix)self.get_low_limit()self.get_up_limit()#  从文件中读取数据 初始化数据矩阵def read_data_from_file(self):with open(self.input_file) as source:for line in source:data_cluster = line.rstrip().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 = 5000index = 0for k in range(self.n):if worker_mark[k] == 0 and min_value > temp[k]:min_value = temp[k]index = kworker_mark[index] = 1  # 标记工人是否被分配self.max += min_value  # 累积上限值#  分支界限算法def branch_limit(self):if self.pt_flag == 0:  # 从第一层开始for i in range(self.n):time = self.matrix[0][i]if time <= self.max:  # 没达到上限,创建节点,加入队列node = Node()node.deep = 0node.cost = timenode.value = timenode.worker = iself.pt_nodes.append(node)self.pt_flag = 1while self.pt_flag == 1:  # 永久循环 等队列空了在根据条件判断来结束if len(self.pt_nodes) == 0:breaktemp = self.pt_nodes.pop(0)  # 先进先出present_node = temptotal_cost = temp.costpresent_deep = temp.deep#  初始化工人分配标记worker_mark = []for i in range(self.n):worker_mark.append(0)#  检查本节点下的作业分配情况worker_mark[temp.worker] = 1while temp.father is not None:temp = temp.fatherworker_mark[temp.worker] = 1if present_deep + 1 == self.n:  # 最后一排的叶子节点 直接分配结果if self.min_leaf_node is None:self.min_leaf_node = present_nodeelse:if self.min_leaf_node.cost > present_node.cost:self.min_leaf_node = present_nodeelse:children = self.matrix[present_deep + 1]#  检查本节点的子节点是否符合进入队列的要求for k in range(self.n):if children[k] + total_cost <= self.max and worker_mark[k] == 0:node = Node()node.deep = present_deep + 1node.cost = children[k] + total_costnode.value = children[k]node.worker = knode.father = present_nodeself.pt_nodes.append(node)#  输出算法执行的结果def output_result(self):file = open(self.output_file,'a')temp = self.min_leaf_nodefile.write('最少工作时间为:' + str(temp.cost) + '\n')print('最少工作时间为:',str(temp.cost))file.write('第'+str(temp.worker+1) + '位工人完成第'+str(temp.deep+1) + '份工作\n')print('第{}位工人完成第{}份工作'.format(temp.worker+1,temp.deep+1))while temp.father is not None:temp = temp.fatherfile.write('第' + str(temp.worker + 1) + '位工人完成第' + str(temp.deep + 1) + '份工作\n')print('第{}位工人完成第{}份工作'.format(temp.worker + 1, temp.deep + 1))return temp.cost#  分支节点类
class Node:def __init__(self):self.deep = 0  # 标记该节点的深度self.cost = 0  # 标记到达该节点的总消费self.father = None  # 标记该节点的父节点self.value = 0  # 本节点的消费值self.worker = None  # 本节点的该任务由第几位工人完成# 主函数
def main():for i in range(7):input_file = 'input_assign05_0{}.dat'.format(i+1)output_file = 'output_0{}.dat'.format(i+1)#  初始化算法执行类worker = Worker(input_file, output_file)#  执行分支界限算法worker.branch_limit()#  输出结果print('第{}组输入'.format(i + 1))worker.output_result()sleep(300)# 算法启动
if __name__ == '__main__':main()
代码编程
赞赏

相关文章

数商云食品行业解决方案:新技术加持食品行业,为企业快速发展提供有力支撑
星期零斩获2021新消费领域“投资界50强企业”和“中国食品工业创新品牌”奖项
2022-2028年中国食品产业园区行业市场运行格局及发展策略分析报告
工业互联网业务知识
劲牌公司荣获2020年度“中国食品工业协会科学技术奖”特等奖
面试3_:不修改数组找出重复的数字