アイテムを含むストアがあります。各アイテムは、コンポーネント (アトマル) またはさまざまなコンポーネントで構成される製品 (ただし、2 つ以上の同じコンポーネントで構成されることはありません) のいずれかです。
今、商品を店から持ち出したい場合、さまざまなシナリオがあります。
- ストアには必要な数の製品が含まれています。
- ストアには、私が製品を組み立てることができるコンポーネントが含まれています。
- ストアには、必要な製品とコンポーネントを共有する製品が含まれています。それらを分解して、必要なアイテムを組み立てることができます。
- 上記の任意の組み合わせ。
以下に、これまでのコードを示します ( getAssemblyPath)。可能であれば、必要なアイテムを組み立てる方法を見つけますが、組み立てパスを最適化しません。
次の 2 つの方法でパスを最適化します。
- まず、アセンブリ/分解アクションの回数が最も少ないパスを選択します。
- 第二に、そのような経路が複数ある場合は、分解されたコンポーネントが店舗に残るのが最も少ない経路を選択します。
さて、ここで私はこの最適化を行う方法を完全に失っています（これが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.
これは機能しますが、製品 B には必要なコンポーネント alpha と charlie の両方が含まれているため、不必要に製品 A を逆アセンブルします。
--
編集：
Blckknght の非常に賢明な質問に答える:
「組立・分解回数を少なくしたい」とは、品数を少なくしたいということですか、それとも品種数を少なくしたいということですか
「組み立て/分解アクション」とは、含まれるコンポーネントの数に関係なく、1 つの製品を組み立てる、または分解するアクションです。異なるかどうかに関係なく、タッチされたアイテムの数が最も少ないものを探しています。
つまり、製品 A を 10 個分解し、さらに製品 B を 5 個分解するよりも、製品 A を 20 個分解する方がよいでしょうか?
後者は最適に近いです。
さらに、多くのコンポーネントを残すのは避けたいと言っていますが、現在のコードでは、要求された製品で使用されていない逆アセンブルされたコンポーネントはすべて失われています。それは意図的なものですか (つまり、他のコンポーネントを破棄したいのですか)、それともバグですか?
このメソッドgetAssemblyPathは、アイテムを取得する方法のパスのみを決定します。実店舗には触れません。に割り当てられることはありませんself.__items。これは、店から必要なアイテムを必要な量だけ取り出すために、店長が将来 (当面) に何をしなければならないかを注文する機能と考えてください。
--
編集2：
この問題に取り組むための最初の明白な (または少なくとも私には明白な) 方法は、分解するたびに必要なコンポーネントをより多く取得するにつれて、必要な製品と最大量のコンポーネントを共有する製品を最初に検索することです。しかし残念ながら、これは必ずしも最適なパスをもたらすとは限りません。たとえば、次のようにします。
コンポーネントα、β、γ、δ、ε、およびζからなる製品A。
コンポーネントα、β、η、δ、ε、およびθからなる製品B。
コンポーネントα、β、γ、ι、κ、およびλからなる製品C。
コンポーネントμ、ν、ξ、δ、ε、およびζからなる製品D。
A を 0 個、B を 100 個、C を 100 個、D を 100 個保管しています。A を 10 個必要とします。まず、A とほとんどのコンポーネントを共有する製品を探すと、B が見つかります。10 個を分解します。 B は、α、β、δ、および ε のそれぞれ 10 を取得します。しかし、次に、C の 10 個 (γ を取得するため) と D の 10 個 (ζ を取得するため) を逆アセンブルする必要があります。これらは 40 回のアクション (30 回の分解と 10 回の組み立て) になります。しかし、最適な方法は、C の 10 個と D の 10 個を分解することです (アクション 30 回、分解 20 回、組み立て 10 回)。
--
編集3：
報奨金を獲得するために Python コードを投稿する必要はありません。アルゴリズムを私に説明して、それが実際に最適なパス、または最適なパスが複数ある場合はその 1 つを生成することを示してください。