python - 组合太多

Question

嗨，我正在尝试生成所有可能的 worker 到建筑物的组合。 (让我解释一下我的场景):
我在玩 MineColonies在我的世界。在这个模组中，你有殖民者，他们可以在建筑物中分配工作。这些 worker 拥有技能和分配给他们的分数。 (例如敏捷:20，力量:5 等)并且当分配到技能与之相称的殖民者时，建筑物的工作会得到更好的执行...
因此，我创建了一个包含所有 worker 和建筑物的数据库，并希望优化哪些 worker 在哪些建筑物内工作。

buildings_dict = {1: ['Strength', 'Focus'],
                  2: ['Adaptability', 'Athletics'],
                  3: ['Knowledge', 'Dexterity'],
                  4: ['Adaptability', 'Knowledge'],
                  6: ['Stamina', 'Athletics'],
                  5: ['Athletics', 'Stamina'],
                  7: ['Focus', 'Agility'],
                  8: ['Dexterity', 'Creativity'],
                  9: ['Strength', 'Focus'],
                  10: ['Adaptability', 'Stamina'],
                  11: ['Agility', 'Adaptability'],
                  12: ['Mana', 'Knowledge'],
                  13: ['Strength', 'Stamina'],
                  14: ['Athletics', 'Strength'],
                  15: ['Creativity', 'Dexterity'],
                  16: ['Knowledge', 'Mana'],
                  17: ['Agility', 'Adaptability']}

workers_dict = {3: {'Mana': 30,
  'Focus': 1,
  'Agility': 3,
  'Stamina': 3,
  'Knowlege': 30,
  'Strenght': 8,
  'Athletics': 13,
  'Dexterity': 6,
  'Creativity': 10,
  'Adaptability': 10,
  'Intelligence': 10},
 4: {'Mana': 29,
  'Focus': 32,
  'Agility': 22,
  'Stamina': 28,
  'Knowlege': 21,
  'Strenght': 30,
  'Athletics': 20,
  'Dexterity': 31,
  'Creativity': 31,
  'Adaptability': 8,
  'Intelligence': 18},
 5: {'Mana': 13,
  'Focus': 1,
  'Agility': 9,
  'Stamina': 27,
  'Knowlege': 9,
  'Strenght': 13,
  'Athletics': 15,
  'Dexterity': 21,
  'Creativity': 16,
  'Adaptability': 13,
  'Intelligence': 28},
 6: {'Mana': 17,
  'Focus': 14,
  'Agility': 10,
  'Stamina': 17,
  'Knowlege': 13,
  'Strenght': 5,
  'Athletics': 10,
  'Dexterity': 15,
  'Creativity': 1,
  'Adaptability': 11,
  'Intelligence': 4},
 7: {'Mana': 1,
  'Focus': 8,
  'Agility': 6,
  'Stamina': 27,
  'Knowlege': 11,
  'Strenght': 17,
  'Athletics': 30,
  'Dexterity': 1,
  'Creativity': 5,
  'Adaptability': 11,
  'Intelligence': 5},
 8: {'Mana': 6,
  'Focus': 1,
  'Agility': 12,
  'Stamina': 30,
  'Knowlege': 20,
  'Strenght': 15,
  'Athletics': 30,
  'Dexterity': 9,
  'Creativity': 17,
  'Adaptability': 30,
  'Intelligence': 19},
 9: {'Mana': 5,
  'Focus': 7,
  'Agility': 19,
  'Stamina': 5,
  'Knowlege': 22,
  'Strenght': 18,
  'Athletics': 26,
  'Dexterity': 10,
  'Creativity': 24,
  'Adaptability': 20,
  'Intelligence': 22},
 10: {'Mana': 8,
  'Focus': 12,
  'Agility': 27,
  'Stamina': 3,
  'Knowlege': 17,
  'Strenght': 1,
  'Athletics': 5,
  'Dexterity': 9,
  'Creativity': 7,
  'Adaptability': 29,
  'Intelligence': 1},
 11: {'Mana': 1,
  'Focus': 4,
  'Agility': 5,
  'Stamina': 30,
  'Knowlege': 16,
  'Strenght': 11,
  'Athletics': 28,
  'Dexterity': 11,
  'Creativity': 5,
  'Adaptability': 12,
  'Intelligence': 4},
 12: {'Mana': 7,
  'Focus': 1,
  'Agility': 17,
  'Stamina': 25,
  'Knowlege': 23,
  'Strenght': 4,
  'Athletics': 8,
  'Dexterity': 26,
  'Creativity': 15,
  'Adaptability': 29,
  'Intelligence': 22},
 13: {'Mana': 2,
  'Focus': 1,
  'Agility': 5,
  'Stamina': 21,
  'Knowlege': 24,
  'Strenght': 18,
  'Athletics': 20,
  'Dexterity': 10,
  'Creativity': 12,
  'Adaptability': 30,
  'Intelligence': 5},
 14: {'Mana': 9,
  'Focus': 16,
  'Agility': 14,
  'Stamina': 25,
  'Knowlege': 14,
  'Strenght': 24,
  'Athletics': 30,
  'Dexterity': 9,
  'Creativity': 19,
  'Adaptability': 23,
  'Intelligence': 18},
 15: {'Mana': 23,
  'Focus': 15,
  'Agility': 5,
  'Stamina': 12,
  'Knowlege': 24,
  'Strenght': 12,
  'Athletics': 20,
  'Dexterity': 29,
  'Creativity': 5,
  'Adaptability': 19,
  'Intelligence': 12},
 17: {'Mana': 21,
  'Focus': 23,
  'Agility': 30,
  'Stamina': 18,
  'Knowlege': 27,
  'Strenght': 7,
  'Athletics': 30,
  'Dexterity': 10,
  'Creativity': 5,
  'Adaptability': 22,
  'Intelligence': 18},
 18: {'Mana': 11,
  'Focus': 11,
  'Agility': 4,
  'Stamina': 7,
  'Knowlege': 28,
  'Strenght': 11,
  'Athletics': 20,
  'Dexterity': 28,
  'Creativity': 13,
  'Adaptability': 12,
  'Intelligence': 30},
 19: {'Mana': 11,
  'Focus': 11,
  'Agility': 4,
  'Stamina': 7,
  'Knowlege': 28,
  'Strenght': 11,
  'Athletics': 20,
  'Dexterity': 28,
  'Creativity': 13,
  'Adaptability': 12,
  'Intelligence': 30},
 20: {'Mana': 15,
  'Focus': 20,
  'Agility': 28,
  'Stamina': 22,
  'Knowlege': 18,
  'Strenght': 15,
  'Athletics': 23,
  'Dexterity': 19,
  'Creativity': 20,
  'Adaptability': 27,
  'Intelligence': 20},
 21: {'Mana': 30,
  'Focus': 7,
  'Agility': 9,
  'Stamina': 7,
  'Knowlege': 30,
  'Strenght': 3,
  'Athletics': 6,
  'Dexterity': 17,
  'Creativity': 4,
  'Adaptability': 11,
  'Intelligence': 28},
 22: {'Mana': 9,
  'Focus': 10,
  'Agility': 28,
  'Stamina': 26,
  'Knowlege': 1,
  'Strenght': 8,
  'Athletics': 5,
  'Dexterity': 26,
  'Creativity': 1,
  'Adaptability': 14,
  'Intelligence': 16},
 23: {'Mana': 4,
  'Focus': 14,
  'Agility': 19,
  'Stamina': 5,
  'Knowledge': 21,
  'Strength': 25,
  'Athletics': 12,
  'Dexterity': 23,
  'Creativity': 26,
  'Adaptability': 21,
  'Intelligence': 22},
 24: {'Mana': 1,
  'Focus': 1,
  'Agility': 18,
  'Stamina': 24,
  'Knowledge': 25,
  'Strength': 20,
  'Athletics': 9,
  'Dexterity': 14,
  'Creativity': 19,
  'Adaptability': 30,
  'Intelligence': 7},
 25: {'Mana': 12,
  'Focus': 13,
  'Agility': 21,
  'Stamina': 23,
  'Knowledge': 11,
  'Strength': 16,
  'Athletics': 18,
  'Dexterity': 24,
  'Creativity': 1,
  'Adaptability': 20,
  'Intelligence': 1},
 26: {'Mana': 10,
  'Focus': 14,
  'Agility': 12,
  'Stamina': 27,
  'Knowledge': 17,
  'Strength': 24,
  'Athletics': 23,
  'Dexterity': 21,
  'Creativity': 5,
  'Adaptability': 5,
  'Intelligence': 28},
 27: {'Mana': 11,
  'Focus': 23,
  'Agility': 21,
  'Stamina': 12,
  'Knowledge': 15,
  'Strength': 24,
  'Athletics': 17,
  'Dexterity': 12,
  'Creativity': 1,
  'Adaptability': 11,
  'Intelligence': 9},
 28: {'Mana': 7,
  'Focus': 21,
  'Agility': 22,
  'Stamina': 21,
  'Knowledge': 14,
  'Strength': 15,
  'Athletics': 9,
  'Dexterity': 16,
  'Creativity': 2,
  'Adaptability': 11,
  'Intelligence': 5},
 29: {'Mana': 12,
  'Focus': 25,
  'Agility': 29,
  'Stamina': 6,
  'Knowledge': 7,
  'Strength': 10,
  'Athletics': 14,
  'Dexterity': 15,
  'Creativity': 6,
  'Adaptability': 13,
  'Intelligence': 29},
 30: {'Mana': 21,
  'Focus': 17,
  'Agility': 8,
  'Stamina': 21,
  'Knowledge': 22,
  'Strength': 22,
  'Athletics': 26,
  'Dexterity': 13,
  'Creativity': 15,
  'Adaptability': 24,
  'Intelligence': 13}}

抱歉，代码块太长，是的，我意识到 ID 不一定正确(希望使其可重现)。
所以我正在使用 itertools.permutations将所有 worker 组合到建筑物中:

import itertools
workers_ls = list(workers_dict.keys())
combinations = list(itertools.permutations(workers_ls, len(buildings_dict))

(我打算在之后对组合进行评分)
这显然从未完成运行，因为它类似于 27! = 1×10²⁸。
我想知道是否有其他解决方案可以解决我的问题，或者是否有一种无需经过所有组合即可确定最佳解决方案的方法。 (我愿意用其他编码语言工作)
谢谢!

Answer 1

我假设你想最大化总产量的总和。例如，当没有分配 worker 时，总产量为零(或某个不依赖于 worker 分配的常数)。如果您将 worker 与 Agility 配对2 和 Focus 3 带建筑属性[Agility, Focus] ，您添加 2+3=5到总产量。
像这样的问题通常用线性规划来解决。我会用 pulp帮助制定线性规划问题。我还建议查看 Julia包裹JuMP .
计算总产量的实际规则可能更复杂。如果(1)您可以定义生产矩阵的一些模拟，并且(2)总产量可以表示为( worker ，建筑)对的生产总和，您仍然可以使用线性规划。
这里有两种方法可以解决这个问题。第一个允许每个建筑物有多个 worker ，第二个不允许。
设置

import pandas as pd
import numpy as np
# !pip install pulp
import pulp

df_buildings = pd.DataFrame(buildings_dict).T
df_workers = pd.DataFrame(workers_dict).T

# there are a few typos, e.g. Strenght vs. Strength and Knowlege vs. Knowledge
# let's fix this first
df_workers.Knowledge.fillna(df_workers.Knowlege, inplace=True)
df_workers.Strength.fillna(df_workers.Strenght, inplace=True)
del df_workers["Strenght"], df_workers["Knowlege"]

# fixing some notation
workers = df_workers.index.tolist() # list of workers
buildings =  df_buildings.index.tolist() # list of building

# next, we define production matrix
# production[i,j] will contain the productivity of 
# worker i when assigned to building j
# you could vectorize this step, though it seems fast enough here
production = pd.DataFrame(index=workers, columns=buildings)
for i in df_workers.index:
  for j in df_buildings.index:
    production.loc[i, j] = df_workers.loc[i, df_buildings.loc[j]].sum()

print(production.head())
#    1   2   3   4   6   5   7   8   9   10  11  12  13  14  15  16  17
# 3   9  23  36  40  16  16   4  16   9  13  13  60  11  21  16  60  13
# 4  62  28  52  29  48  48  54  62  62  36  30  50  58  50  62  50  30
# 5  14  28  30  22  42  42  10  37  14  40  22  22  40  28  37  22  22
# 6  19  21  28  24  27  27  24  16  19  28  21  30  22  15  16  30  21
# 7  25  41  12  22  57  57  14   6  25  38  17  12  44  47   6  12  17

每栋楼允许多名 worker

prob = pulp.LpProblem("MineColoniesProblem", pulp.LpMaximize)

# in the solved problem, assignment[i,j] == 1 whenever i is assigned to j
assignment = pulp.LpVariable.dicts("Assignment", (workers, buildings), cat="Binary")

# our objective is to maximize the sum of production
prob += sum(assignment[i][j] * production.loc[i,j]
            for i in workers for j in buildings)

# each worker can be assigned to at most one building:
for i in workers:
  prob += sum(assignment[i][j] for j in buildings) <= 1

prob.solve()
# make sure that we got an optimal solution
assert prob.status == 1

# generically, we get an integer solution
assignment_dict = {i: j for i in workers for j in buildings
                   if assignment[i][j].varValue == 1}
print(f"Total production is {prob.objective.value()}") # 1401

# here is the the solution
# assignment_dict_saved = {3: 12, 4: 1, 5: 5, 6: 16, 7: 5, 8: 6, 9: 2, 10: 17, 11: 6, 12: 10, 13: 4, 14: 6, 15: 3, 17: 7, 18: 3, 19: 3, 20: 11, 21: 12, 22: 17, 23: 15, 24: 4, 25: 10, 26: 13, 27: 9, 28: 7, 29: 7, 30: 2}

每栋楼最多一名 worker

prob = pulp.LpProblem("MineColoniesProblem", pulp.LpMaximize)

# in the solved problem, assignment[i,j] == 1 whenever i is assigned to j
assignment = pulp.LpVariable.dicts("Assignment", (workers, buildings), cat="Binary")

# our objective is to maximize the sum of production
prob += sum(assignment[i][j] * production.loc[i,j]
            for i in workers for j in buildings)

# each worker can be assigned to at most one building:
for i in workers:
  prob += sum(assignment[i][j] for j in buildings) <= 1

# each building has at most one worker
for j in buildings:
  prob += sum(assignment[i][j] for i in workers) <= 1

prob.solve()
# make sure that we got an optimal solution
assert prob.status == 1

# generically, we get an integer solution
assignment_dict = {i: j for i in workers for j in buildings
                   if assignment[i][j].varValue == 1}
# assignment_dict_saved = {3: 16, 4: 9, 7: 5, 8: 2, 10: 11, 11: 6, 12: 10, 14: 14, 18: 3, 19: 8, 20: 17, 21: 12, 23: 15, 24: 4, 26: 13, 27: 1, 29: 7}
print(f"Total production is {prob.objective.value()}") # 929

我们可以看到，当每个建筑物允许多个 worker 时，总产量会更高。这是意料之中的，因为最大化问题的约束较少。
我们还可以将优化的生产与将 worker 随机分配到建筑物时的生产进行比较。垂直线对应于最佳生产。看起来我们做得很好。