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

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

文章链接：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)

最后

以上就是伶俐萝莉为你收集整理的Python3 回朔法解决作业分配问题 （剪枝优化）的全部内容，希望文章能够帮你解决Python3 回朔法解决作业分配问题 （剪枝优化）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。