优化产品装配/拆卸
我有一家商店，里面有物品。每个项目要么是一个组件(这是原子的)，要么是由各种组件组成的产品(但从未包含两个或更多相同的组件)。
现在，当我想从商店里拿出一个产品时，有各种各样的场景：
- 商店包含产品的必要号码。
- 商店里有我可以组装产品的组件。
- 存储包含与所需产品共享组件的产品。我可以拆开它们并组装所需的物品。
- 以上的任何组合。
下面您可以看到我的代码(getAssemblyPath)。如果可能的话，它确实找到了一种组装所需项的方法，但是它并没有优化程序集路径。
我想通过两种方式来优化路径：
- 首先，选择使用最少数量的程序集/反汇编操作的路径。
- 第二，如果有各种这样的路径，请选择在存储中保留最少数量的拆卸组件的路径。
现在，我完全不知道如何完成这个优化(我甚至不确定这是一个针对SO的问题还是一个数学的问题)。
如何修改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。
--
编辑：
回答布莱克纽特提出的非常明智的问题：
当您说要“最小数量的组装/拆卸操作”时，您指的是最小数量的项目，还是最小数量的不同产品？
“asm/ disassembling”是指无论涉及多少个组件，都要对一个产品进行组装或拆卸。我正在寻找最少数量的触摸项目，无论它们是否是不同的。
也就是说，拆20件A产品比拆10件A件和5件B件好吗？
后者更接近最优。
此外，您还说您希望避免留下许多组件，但是在当前代码中，所有未被请求的产品使用的拆卸组件都丢失了。这是故意的(也就是说，你想扔掉其他组件)，还是一个bug？
方法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
Stack Overflow用户
发布于 2013-03-06 20:03:25
以下是我如何解决这个问题的方法。我想为此编写代码，但我想我没有时间了。
您可以递归地找到最优解决方案。创建一个表示部件存储和当前请求状态的数据结构。现在，针对您需要的每个部分，进行一系列递归调用，尝试各种方法来填充订单。关键是，通过尝试一种填充顺序的方法，您将完成部分工作，因此递归调用现在是相同问题的一个稍微简单的版本。
下面是一个具体的例子，基于您的示例。我们需要填写产品3 (p3)的订单，该产品由c1、c3和c4组成。我们的订单是20欧元的p3，我们有10 p3的存货，所以我们只需要为p3的前10款做一些小的补充。现在我们的订单是为10的p3，但我们可以把它看作是10的c1，10的c3，和10的c4。对于第一个递归调用，我们分解一个p1，并为单个c1填充一个订单，并在存储中放置一个额外的c2；因此，这个递归调用针对c1的9个、c3的10个和c4的10个，并更新了存储中的可用性。对于第二个递归调用，我们分解一个p2，填充一个c1和一个c4的订单，并将一个额外的c2放入存储中；因此，这个递归调用是针对c1的9个、c3的10个和c4的9个，并更新了存储中的可用性。
由于每次调用都减少了问题，递归的一系列调用将终止。递归调用应该返回成本度量，它要么表示调用找不到解决方案，要么指示找到解决方案的成本；函数通过选择成本最低的解决方案来选择最佳解决方案。
我不确定，但你可以通过回忆录来加速这件事。Python在3.x系列functools.lru_cache()中有一个非常漂亮的内置组件；因为您将问题标记为“Python3.2”，所以您可以使用它。
What is memoization and how can I use it in Python?
回忆录的工作方式是认识到函数已经被用相同的参数调用，并且只返回与以前相同的解决方案。因此，它是一个将参数映射到答案的缓存。如果这些参数包含非必要的数据(比如存储了多少组件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)Stack Overflow用户
发布于 2013-03-06 22:27:34
- N乘积的最优路径单乘积的<=>最优路径。
实际上，如果我们需要对产品X的N进行最优装配，那么在我们优化(使用当前库存)组装一个产品之后，问题就变成了如何使用剩余库存来最优地组装产品X (N-1)。
因此，提供一次优化组装一个产品X的算法就足够了。
- 假设我们需要产品的组件x1、..xn (这里我们只包括无法作为库存组件使用的组件)
对于每个组件xk，请查找所有具有此组件的产品。我们将得到每个组件的产品列表--产品A1(1)、.、A1(i1)有组件x1、产品A(1)、.、A(i2)有组件x2等等(一些产品可以包含在多个列表( A1、A2、.、列表)中)。
如果列表中的任何一个是空的，则没有解决方案。
我们需要最低限度的产品集，以便该集合中的产品包含在每个列表中。最简单但不具有计算效率的解决方案是使用蛮力--尝试所有集合并选择最小值：
- 以A1的联合，.，也就是A(只包括联盟中唯一的产品).
从a获取单个产品，如果它包含在所有的A1中. An -我们只需要一个拆卸(这个产品)。尝试来自A的两个产品的所有组合，如果任何组合( a1，a2)都满足条件，即a1或a2包含在每个列表A1中，……这是一个解决方案。
..。
当然，从每个列表A1中都有一个深入的n个组件的解决方案，.如果我们之前没有找到解决方案，这是最好的解决方案。
现在，我们只需要考虑更好的策略，然后是蛮力检查，我认为这是可能的--我需要考虑它，但是这个蛮力方法确实找到了严格的最优解。
编辑：
更准确的解决方案是按长度对列表进行排序。然后，当检查K积的集合是否为解时，只需要检查来自第一个K列表的每个列表中的所有可能的1项组合，如果没有解，则没有最小深度K集来解决问题。这种检查在计算上也不会有那么糟糕--也许它能起作用？
Stack Overflow用户
发布于 2013-02-28 04:40:58
我认为这里的关键是确定每个采购案例的潜在成本，从而使采购案例的适当组合使成本函数最小化。(然后简单地简化为背包问题)
下面的内容可能不是最优的，但下面是我所指的一个例子：
1.任何作为最终产品“成本”的产品-它是实际成本(以货币计算)。
2.可组装成最终产品的任何部件或产品(鉴于其他单独的产品/组件)，但不需要被拆掉的成本-它的实际价格(以货币计)加上一小部分税。
3.任何能促进最终产品装配但需要拆解的部件或产品，其价格以货币计算，并对装配品征收小额税，并对所需的每件产品征收一小部分税。(可能与集会税的价值相同？)
注:这些“税”将适用于所有的子产品，在同一情况下。
..。在其他可能的情况下，等等
然后，找到所有可能的组合，组件和产品可以在店面，能够组装成最终产品。将这些“组装列表”放入按所选成本函数确定的成本排序列表中。在此之后，开始创建尽可能多的第一个(最低成本)“组装列表”(检查程序集列表中的所有项是否仍可在存储区中使用-即您已经将它们用于以前的程序集)。一旦无法创建更多的这种情况，就从列表中弹出它。重复，直到你需要的所有最终产品都被“制造”。
注意:每次你“组装”一个最终产品时，你都需要为当前“装配列表”中的每一个产品配置一个全局计数器。
希望这能让讨论朝着正确的方向发展。祝好运!
https://stackoverflow.com/questions/15071659
复制相似问题
腾讯云开发者
