优化产品组装/拆卸
我有一个商店，里面有各种商品。每个商品要么是一个基本组件（就是最小的单元），要么是由多个组件组合而成的产品（但不会有两个或更多相同的组件）。
现在，当我想从商店里拿出一个产品时，会有几种情况：
- 商店里有足够的这个产品。
- 商店里有可以用来组装这个产品的组件。
- 商店里有其他产品，它们和我需要的产品有一些相同的组件。我可以把这些产品拆开，然后组装出我需要的产品。
- 以上情况的任意组合。
下面是我目前的代码（getAssemblyPath）。它能找到组装所需产品的方法，但没有优化组装的路径。
我想从两个方面来优化这个路径：
- 首先，选择需要的组装/拆解动作最少的路径。
- 其次，如果有多条这样的路径，选择在商店里留下的拆解组件最少的路径。
现在，我完全不知道该如何进行这个优化（我甚至不确定这是一个适合在StackOverflow上提问的问题，还是数学问题）。
我该如何修改getAssemblyPath，使其符合我的优化要求？
这是我目前的代码：
#! /usr/bin/python
class Component:
def __init__ (self, name): self.__name = name
def __repr__ (self): return 'Component {}'.format (self.__name)
class Product:
def __init__ (self, name, components):
self.__name = name
self.__components = components
@property
def components (self): return self.__components
def __repr__ (self): return 'Product {}'.format (self.__name)
class Store:
def __init__ (self): self.__items = {}
def __iadd__ (self, item):
item, count = item
if not item in self.__items: self.__items [item] = 0
self.__items [item] += count
return self
@property
def items (self): return (item for item in self.__items.items () )
@property
def products (self): return ( (item, count) for item, count in self.__items.items () if isinstance (item, Product) )
@property
def components (self): return ( (item, count) for item, count in self.__items.items () if isinstance (item, Component) )
def getAssemblyPath (self, product, count):
if product in self.__items:
take = min (count, self.__items [product] )
print ('Take {} of {}'.format (take, product) )
count -= take
if not count: return
components = dict ( (comp, count) for comp in product.components)
for comp, count in self.components:
if comp not in components: continue
take = min (count, components [comp] )
print ('Take {} of {}'.format (take, comp) )
components [comp] -= take
if not components [comp]: del components [comp]
if not components: return
for prod, count in self.products:
if prod == product: continue
shared = set (prod.components) & set (components.keys () )
dis = min (max (components [comp] for comp in shared), count)
print ('Disassemble {} of {}.'.format (dis, prod) )
for comp in shared:
print ('Take {} of {}.'.format (dis, comp) )
components [comp] -= take
if not components [comp]: del components [comp]
if not components: return
print ('Missing components:')
for comp, count in components.items ():
print ('{} of {}.'.format (count, comp) )
c1 = Component ('alpha')
c2 = Component ('bravo')
c3 = Component ('charlie')
c4 = Component ('delta')
p1 = Product ('A', [c1, c2] )
p2 = Product ('B', [c1, c2, c3] )
p3 = Product ('C', [c1, c3, c4] )
store = Store ()
store += (c2, 100)
store += (c4, 100)
store += (p1, 100)
store += (p2, 100)
store += (p3, 10)
store.getAssemblyPath (p3, 20)
这个输出结果是：
Take 10 of Product C
Take 10 of Component delta
Disassemble 10 of Product A.
Take 10 of Component alpha.
Disassemble 10 of Product B.
Take 10 of Component charlie.
这个结果是有效的，但它不必要地拆解了产品A，因为产品B已经包含了所需的两个组件alpha和charlie。
--
编辑：
回答Blckknght提出的非常合理的问题：
当你说你想要“最少的组装/拆解动作”时，是指最少的物品数量，还是最少的不同产品数量？
一个“组装/拆解动作”是指组装或拆解一个产品的动作，不管涉及多少个组件。我希望减少接触的物品数量，不管它们是否不同。
也就是说，拆解20个产品A比拆解10个产品A和额外的5个产品B更好？
后者更接近最佳方案。
此外，你说你想避免留下很多组件，但在你当前的代码中，所有未被请求产品使用的拆解组件都会被丢弃。这是故意的吗（也就是说，你想丢掉其他组件），还是一个错误？
方法getAssemblyPath只是确定了获取物品的路径。它并没有实际操作商店。在任何时候，它都没有给self.__items赋值。可以把它想象成一个函数，它给商店老板发出指令，让他在不久的将来做什么，以便从商店里拿出所需数量的所需物品。
--
编辑2：
解决这个问题的第一个明显（或者至少对我来说是明显的）方法，是先寻找那些与所需产品共享最多组件的产品，因为这样每次拆解可以获得更多所需组件。但不幸的是，这不一定能得到最佳路径。举个例子：
产品A由组件α、β、γ、δ、ε和ζ组成。
产品B由组件α、β、η、δ、ε和θ组成。
产品C由组件α、β、γ、ι、κ和λ组成。
产品D由组件μ、ν、ξ、δ、ε和ζ组成。
我们在商店里有0个A，100个B，100个C和100个D。我们需要10个A。现在如果我们首先寻找与A共享最多组件的产品，我们会找到B。我们拆解10个B，得到10个α、β、δ和ε。但接着我们需要拆解10个C（以获得γ）和10个D（以获得ζ）。这样总共需要40个动作（30个拆解和10个组装）。但最佳方案是拆解10个C和10个D（总共30个动作，20个拆解和10个组装）。
--
编辑3：
你不需要发布Python代码来赢得奖励。只需向我解释算法，并证明它确实能得到最佳路径，或者如果有多个最佳路径，能得到其中之一。
3 个回答
我觉得这里的关键是要搞清楚每种购买情况可能产生的费用，这样才能找到合适的购买组合，最小化成本函数。（这其实就是一个背包问题）
接下来可能不是最优的，但我给你举个例子：
1. 任何最终产品的“成本”就是它的实际价格（用货币表示）。
2. 任何可以组装成最终产品的组件或产品（前提是有其他单独的产品/组件）但不需要拆解的，成本就是它的真实价格（用货币表示）加上一点小税（待定）。
3. 任何可以帮助组装最终产品但需要拆解的组件或产品，成本是它的价格加上一点小税用于组装成最终产品，还有每次拆解需要的另一点小税。（可能和组装税是一样的？）
注意：这些“税”会适用于所有占用同一情况的子产品。
……其他可能的情况也是如此
然后，找出所有可以在商店里组装成最终产品的组件和产品的组合。把这些“组装清单”放进一个按照你选择的成本函数排序的列表中。接下来，尽量多地创建第一个（最低成本的）“组装清单”（通过检查组装清单中的所有物品是否仍然在商店里可用——也就是说，你之前没有用过它们进行其他组装）。一旦你不能再创建这个情况，就把它从列表中移除。重复这个过程，直到你需要的所有最终产品都“组装”完成。
注意：每次你“组装”一个最终产品时，都需要减少当前“组装清单”中每个产品的全局计数器。
希望这能让讨论朝着正确的方向发展。祝好运！
- N个产品的最佳路径和单个产品的最佳路径是相同的。
没错，如果我们需要最优地组装N个X产品，在我们最优地（利用现有库存）组装一个产品之后，接下来的问题就是如何利用剩余的库存最优地组装(N-1)个X产品。
=> 因此，只需要提供一个算法来逐个最优地组装一个X产品。
- 假设我们需要为这个产品准备组件x1,..xn（这里我们只考虑那些库存中没有的组件）。
对于每个组件xk，找出所有包含这个组件的产品。我们会为每个组件得到一个产品列表——比如，产品A1(1),..,A1(i1)包含组件x1，产品A(1),..,A(i2)包含组件x2，依此类推（有些产品可能出现在多个列表A1,A2,..,An中）。
如果任何一个列表是空的，那就没有解决方案。
我们需要一个最小的产品集合，使得这个集合中的每个产品都包含在每个列表中。最简单但效率不高的解决方案是暴力破解——尝试所有的集合，找出最小的：
- 将A1,..,An的并集取出来，称之为A（只包括唯一的产品）。
a. 从A中取一个产品，如果它包含在所有的A1,..,An中，那我们只需要拆解这个产品一次。
b. 尝试A中两个产品的所有组合，如果任何组合(a1,a2)满足条件，即a1或a2都包含在每个列表A1,..,An中，那就是一个解决方案。
...
当然，在深度n的情况下，总会有一个解决方案——每个列表A1,..,An中各取一个组件。如果之前没有找到解决方案，这就是最好的解决方案。
现在，我们只需要考虑比暴力破解更好的策略，我认为这是可能的——我需要再想想，但这个暴力破解的方法肯定能找到严格的最优解。
编辑：
更准确的解决方案是按长度对列表进行排序。然后在检查K个产品是否为解决方案时，只需要检查前K个列表中每个列表的1个项目的所有可能组合，如果没有解决方案，那就没有深度K的最小集合能解决这个问题。这种检查的计算量也不会太大——也许这样可以行得通？？？
这是我解决这个问题的方法。我本来想写代码，但我觉得没时间。
你可以通过递归找到一个最优解。首先，创建一个数据结构来表示零件商店的状态和当前的需求。然后，对于你需要的每个零件，进行一系列递归调用，尝试不同的方式来满足订单。关键在于，通过尝试满足订单的一种方式，你实际上是在完成一部分工作，因此这个递归调用就变成了一个稍微简单一点的同类问题。
这里有一个具体的例子，基于你的情况。我们需要满足产品3（p3）的订单，它由组件c1、c3和c4组成。我们的订单是20个p3，而我们库存中有10个p3，所以我们可以轻松满足前10个p3的订单。现在我们的订单变成了10个p3，但我们可以把它看作是10个c1、10个c3和10个c4的订单。在第一次递归调用中，我们拆解一个p1，满足一个c1的订单，并在商店里放一个额外的c2；所以这次递归调用的需求变成了9个c1、10个c3和10个c4，并更新了商店的库存。第二次递归调用中，我们拆解一个p2，满足一个c1和一个c4的订单，并在商店里放一个额外的c2；所以这次递归调用的需求变成了9个c1、10个c3和9个c4，并更新了商店的库存。
由于每次调用都会减少问题的复杂度，递归调用最终会结束。递归调用应该返回一个成本指标，这个指标要么表示调用未能找到解决方案，要么表示找到的解决方案的成本；函数会选择成本最低的解决方案。
我不太确定，但你可能可以通过记忆化来加速这个过程。Python在3.x版本中有一个非常方便的内置功能，functools.lru_cache()；因为你把问题标记为“Python 3.2”，所以你可以使用这个功能。
记忆化的工作原理是识别出函数已经用相同的参数被调用过，然后直接返回之前的结果。所以它就像一个缓存，把参数映射到答案。如果参数中包含一些非必要的数据（比如商店里有多少个c2），那么记忆化的效果就会降低。但如果我们想象有产品p1和p9，而p9包含组件c1和c9，那么对于我们的目的来说，拆解p1或p9应该是等价的：它们的拆解成本相同，且都能产生我们需要的组件（c1）和一个不需要的组件（c2或c9）。所以如果我们把递归调用的参数设置正确，记忆化就可以在我们尝试p9时立即返回答案，这样可以节省很多时间。
嗯，现在想想，我们可能不能使用functools.lru_cache()，但我们可以自己实现记忆化。我们可以创建一个解决方案的缓存：一个字典，把元组映射到值，并构建只包含我们想要缓存的参数的元组。然后在我们的函数中，第一件事就是检查解决方案的缓存，如果这个调用等同于一个缓存的解决方案，就直接返回它。
编辑：这是我到目前为止写的代码。我还没有完成调试，所以它可能还不能产生正确的答案（我不确定，因为它运行时间很长，我还没让它完成）。这个版本传入的是字典，这与我关于记忆化的想法不太兼容，但我想先让一个简单的版本工作，然后再考虑加速。
另外，这段代码会拆解产品并将它们作为组件添加到商店中，所以最终的解决方案会先说“拆解10个产品A”，然后会说“取20个组件alpha”或者其他的。换句话说，组件的数量可能会显得很高，因为它没有区分商店里已经有的组件和通过拆解产品放进去的组件。
我现在没时间了，可能一段时间内都不会继续做这个，抱歉。
#!/usr/bin/python3
class Component:
def __init__ (self, name): self.__name = name
#def __repr__ (self): return 'Component {}'.format (self.__name)
def __repr__ (self): return 'C_{}'.format (self.__name)
class Product:
def __init__ (self, name, components):
self.__name = name
self.__components = components
@property
def components (self): return self.__components
#def __repr__ (self): return 'Product {}'.format (self.__name)
def __repr__ (self): return 'P_{}'.format (self.__name)
class Store:
def __init__ (self): self.__items = {}
def __iadd__ (self, item):
item, count = item
if not item in self.__items: self.__items [item] = 0
self.__items [item] += count
return self
@property
def items (self): return (item for item in self.__items.items () )
@property
def products (self): return ( (item, count) for item, count in self.__items.items () if isinstance (item, Product) )
@property
def components (self): return ( (item, count) for item, count in self.__items.items () if isinstance (item, Component) )
def get_assembly_path (self, product, count):
store = self.__items.copy()
if product in store:
take = min (count, store [product] )
s_trivial = ('Take {} of {}'.format (take, product) )
count -= take
if not count:
print(s_trivial)
return
dict_decr(store, product, take)
product not in store
order = {item:count for item in product.components}
cost, solution = solver(order, store)
if cost is None:
print("No solution.")
return
print("Solution:")
print(s_trivial)
for item, count in solution.items():
if isinstance(item, Component):
print ('Take {} of {}'.format (count, item) )
else:
assert isinstance(item, Product)
print ('Disassemble {} of {}'.format (count, item) )
def getAssemblyPath (self, product, count):
if product in self.__items:
take = min (count, self.__items [product] )
print ('Take {} of {}'.format (take, product) )
count -= take
if not count: return
components = dict ( (comp, count) for comp in product.components)
for comp, count in self.components:
if comp not in components: continue
take = min (count, components [comp] )
print ('Take {} of {}'.format (take, comp) )
components [comp] -= take
if not components [comp]: del components [comp]
if not components: return
for prod, count in self.products:
if prod == product: continue
shared = set (prod.components) & set (components.keys () )
dis = min (max (components [comp] for comp in shared), count)
print ('Disassemble {} of {}.'.format (dis, prod) )
for comp in shared:
print ('Take {} of {}.'.format (dis, comp) )
components [comp] -= take
if not components [comp]: del components [comp]
if not components: return
print ('Missing components:')
for comp, count in components.items ():
print ('{} of {}.'.format (count, comp) )
def str_d(d):
lst = list(d.items())
lst.sort(key=str)
return "{" + ", ".join("{}:{}".format(k, v) for (k, v) in lst) + "}"
def dict_incr(d, key, n):
if key not in d:
d[key] = n
else:
d[key] += n
def dict_decr(d, key, n):
assert d[key] >= n
d[key] -= n
if d[key] == 0:
del(d[key])
def solver(order, store):
"""
order is a dict mapping component:count
store is a dict mapping item:count
returns a tuple: (cost, solution)
cost is a cost metric estimating the expense of the solution
solution is a dict that maps item:count (how to fill the order)
"""
print("DEBUG: solver: {} {}".format(str_d(order), str_d(store)))
if not order:
solution = {}
cost = 0
return (cost, solution)
solutions = []
for item in store:
if not isinstance(item, Component):
continue
print("...considering: {}".format(item))
if not item in order:
continue
else:
o = order.copy()
s = store.copy()
dict_decr(o, item, 1)
dict_decr(s, item, 1)
if not o:
# we have found a solution! Return it
solution = {}
solution[item] = 1
cost = 1
print("BASIS: solver: {} {} / {} {}".format(str_d(order), str_d(store), cost, str_d(solution)))
return (cost, solution)
else:
cost, solution = solver(o, s)
if cost is None:
continue # this was a dead end
dict_incr(solution, item, 1)
cost += 1
solutions.append((cost, solution))
for item in store:
if not isinstance(item, Product):
continue
print("...Product components: {} {}".format(item, item.components))
assert isinstance(item, Product)
if any(c in order for c in item.components):
print("...disassembling: {}".format(item))
o = order.copy()
s = store.copy()
dict_decr(s, item, 1)
for c in item.components:
dict_incr(s, c, 1)
cost, solution = solver(o, s)
if cost is None:
continue # this was a dead end
cost += 1 # cost of disassembly
solutions.append((cost, solution))
else:
print("DEBUG: ignoring {}".format(item))
if not solutions:
print("DEBUG: *dead end*")
return (None, None)
print("DEBUG: finding min of: {}".format(solutions))
return min(solutions)
c1 = Component ('alpha')
c2 = Component ('bravo')
c3 = Component ('charlie')
c4 = Component ('delta')
p1 = Product ('A', [c1, c2] )
p2 = Product ('B', [c1, c2, c3] )
p3 = Product ('C', [c1, c3, c4] )
store = Store ()
store += (c2, 100)
store += (c4, 100)
store += (p1, 100)
store += (p2, 100)
store += (p3, 10)
#store.getAssemblyPath (p3, 20)
store.get_assembly_path(p3, 20)