[已解决]python回溯法 解 作业分配问题

gcaxuxi

1. # -*- coding: utf-8 -*-
   
2. """
   
3. Created on Sun Apr  2 09:20:43 2017
   
4. 
   
5. @author: xuxi
   
6. """
   
7. def assign(k,cost,n,mincost,c,job,task,bestSolution):
   
8. 
   
9.     if (k > n and cost < mincost):
   
10.         mincost = cost
    
11.         for i in range(n):
    
12.             bestSolution[i+1] = task[i+1]  
    
13.     else:     
    
14.         for i in range(n):
    
15.             if (job[i+1] == 0 and (cost+int(c[k-1][i]))>0):
    
16.                 job[i+1] = 1
    
17.                 task[k] = i + 1
    
18.                 assign(k+1,cost+int(c[k-1][i]),n,mincost,c,job,task,bestSolution)
    
19.                 job[i+1] = 0
    
20.                 task[k] = 0            
    
21.     #return mincost,bestSolution
    
22.    
    
23. def output(mincost,n,bestSolution):
    
24.     print('最小总费用%s'%mincost)
    
25.     for i in range(n):
    
26.         print('员工：%s执行任务%s'%(i+1,bestSolution[i+1]))
    
27. 
    
28. def main():
    
29.     f = open('input_assign04_01.dat')
    
30.     c = []
    
31.     for item in f.readlines():
    
32.         c.append(item.rstrip('\n').split())
    
33.     n = len(c)
    
34.     mincost = 65535
    
35.     job = []
    
36.     task = []
    
37.     bestSolution = []
    
38.     for i in range(n+1):
    
39.         job.append(0)
    
40.         task.append(0)
    
41.         bestSolution.append(0)
    
42.     assign(1,0,n,mincost,c,job,task,bestSolution)
    
43.     output(mincost,n,bestSolution)
    
44. 
    
45.    
    
46. if __name__ == '__main__':
    
47.     main()

复制代码

问题为：有n份作业分配给n个人去完成，每人完成一份作业。假定第i个人完成第j份作业需要花费cij时间，cij>0,1≦i,j≦n。试设计一个回溯算法，将n份作业分配给n个人完成，使得总花费时间最短。
我是按照回溯法求解的，得出结果为：
结果明显不对，看了很久，希望有大神帮助看看

最佳答案

月排行榜 / 总排行榜

jerryxjr1220

2017-4-2 22:00:52

n个人完成n项工作，每人完成1项，其实这是n的全排列问题。
如果用全排列解就很方便了，当然递归也可以，只是要设置边界条件，比较麻烦，而且效率比全排列低

例如，假定N=4的情况。

1. from itertools import permutations as pt
   
2. 
   
3. #Define
   
4. cij = [[1,2,3,4],
   
5.        [2,4,6,8],
   
6.        [3,5,7,9],
   
7.        [4,5,6,7]]
   
8. 
   
9. def assign(n,cij=cij):
   
10.     comb = pt(range(n),n)
    
11.     min_comb = 9999
    
12.     for c in comb:
    
13.         temp = 0
    
14.         for i in range(n):
    
15.             temp += cij[i][c[i]]
    
16.         if temp < min_comb:
    
17.             min_comb = temp
    
18.             min_c = c
    
19.     return min_comb, min_c
    
20. 
    
21. print assign(4)

复制代码

输出：
(17, (2, 0, 1, 3))
表示第0个人做第2项工作，第1个人做第0项工作，第2个人做第1项工作，第3个人做第3项工作，总共17个单位时间。

跳转到最佳答案楼层

gcaxuxi

输入的文本内容为：
1 2 3 4
3 2 1 4
3 1 1 4
1 1 1 1
主要是结果明显不对，输入的数据初始化没问题，原因肯定出在assign函数中

jerryxjr1220

n个人完成n项工作，每人完成1项，其实这是n的全排列问题。
如果用全排列解就很方便了，当然递归也可以，只是要设置边界条件，比较麻烦，而且效率比全排列低

例如，假定N=4的情况。

1. from itertools import permutations as pt
   
2. 
   
3. #Define
   
4. cij = [[1,2,3,4],
   
5.        [2,4,6,8],
   
6.        [3,5,7,9],
   
7.        [4,5,6,7]]
   
8. 
   
9. def assign(n,cij=cij):
   
10.     comb = pt(range(n),n)
    
11.     min_comb = 9999
    
12.     for c in comb:
    
13.         temp = 0
    
14.         for i in range(n):
    
15.             temp += cij[i][c[i]]
    
16.         if temp < min_comb:
    
17.             min_comb = temp
    
18.             min_c = c
    
19.     return min_comb, min_c
    
20. 
    
21. print assign(4)

复制代码

输出：
(17, (2, 0, 1, 3))
表示第0个人做第2项工作，第1个人做第0项工作，第2个人做第1项工作，第3个人做第3项工作，总共17个单位时间。

gcaxuxi

jerryxjr1220 发表于 2017-4-2 22:00
n个人完成n项工作，每人完成1项，其实这是n的全排列问题。
如果用全排列解就很方便了，当然递归也可以，只 ...

感谢，原来 python还有这个模块。这个我也吸收吸收