python - 优化产品组装/拆卸

Question

我有一个商店，里面有元素。每个项目要么是一个组件(它是原子的)，要么是由各种组件(但绝不是 2 个或更多相同组件)组成的产品。

现在，当我想从商店取货时，有多种情况:

商店包含必要数量的产品。

商店包含我可以组装产品的组件。

该商店包含与所需产品共享组件的产品。我可以拆卸它们并组装所需的元素。

以上任意组合。

到目前为止，您可以在下面看到我的代码( 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。

——

编辑:

回答 Blckknght 非常明智的问题:

When you say you want "the least number of assembly/disassembly actions", do you mean the smallest number of items, or the smallest number of different products?

“组装/拆卸 Action ”是组装或拆卸一个产品的 Action ，无论涉及多少个组件。我正在寻找最少数量的触摸项目，无论它们是否不同。

That is, is is better to dissassemble 20 of Product A than to dissassemble 10 of Product A and an additional 5 of Product B?

后者更接近最优。

Further, you say you want to avoid leaving many components behind, but in your current code all disassembled components that are not used by the requested Product are lost. Is that deliberate (that is, do you want to be throwing away the other components), or is it a 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 个 Action (30 个拆卸和 10 个组装)。
但最好的方法是拆10个C和10个D(30个 Action ，20个拆解，10个组装)。

——

编辑 3:

你不需要发布 python 代码来赢得赏金。只需向我解释该算法并表明它确实产生了最佳路径，或者如果存在多个最佳路径，则是其中之一。

Answer 1

这是我将如何解决这个问题。我想为此编写代码，但我认为我没有时间。

您可以递归地找到最佳解决方案。制作一个表示零件存储状态和当前请求的数据结构。现在，对于您需要的每个部分，进行一系列递归调用，尝试使用各种方法来填充订单。关键是通过尝试填充订单的方法，您完成了部分工作，因此递归调用现在是同一问题的稍微简单的版本。

这是一个基于您的示例的特定示例。我们需要填写由组件 c1、c3 和 c4 组成的产品 3 (p3) 的订单。我们的订单是 20 个 p3，我们有 10 个 p3 的库存，所以我们随便填写了 p3 的前 10 个订单。现在我们的订单是 p3 的 10，但我们可以将其视为 c1 的 10、c3 的 10 和 c4 的 10 的订单。对于第一次递归调用，我们拆解一个 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() ;由于您将问题标记为“Python 3.2”，因此您可以使用它。

What is memoization and how can I use it in Python?

memoization 的工作原理是识别出该函数已经使用相同的参数被调用，并且只返回与以前相同的解决方案。所以它是一个缓存映射参数到答案。如果参数包含非必要数据(例如存储中有多少组件 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)