Ich habe ein Geschäft mit Artikeln. Jedes Element ist entweder eine Komponente (die atomal ist) oder ein Produkt, das aus verschiedenen Komponenten besteht (aber niemals aus zwei oder mehr derselben Komponenten).
Wenn ich jetzt ein Produkt aus dem Geschäft herausholen möchte, gibt es verschiedene Szenarien:
Unten können Sie meinen Code bis jetzt sehen ( getAssemblyPath ). Es wird eine Möglichkeit gefunden, das erforderliche Element zu erstellen, wenn es möglich ist, aber es optimiert den Montagepfad nicht.
Ich möchte den Pfad auf zwei Arten optimieren:
Nun, hier bin ich völlig im Verlust, wie ich diese Optimierung machen kann (ich bin mir nicht einmal sicher, ob das eine Frage für SO oder für Mathematik ist).
Wie kann ich getAssemblyPath ändern, damit es meinen Optimierungsanforderungen entspricht?
Mein Code bisher:
%Vor%Dies gibt aus:
%Vor%Was funktioniert, zerlegt Produkt A jedoch unnötig, da Produkt B die beiden erforderlichen Komponenten alpha und charlie enthält.
-
BEARBEITEN:
Beantworten der sehr vernünftigen Fragen von Blckknght:
Wenn Sie sagen, Sie möchten "die geringste Anzahl von Montage- / Demontageaktionen", meinen Sie damit die kleinste Anzahl von Artikeln oder die kleinste Anzahl von verschiedenen Produkten?
Eine "asm / disasm Aktion" ist die Aktion des Zusammenfügens oder Zerlegens eines Produkts, egal wie viele Komponenten beteiligt sind. Ich suche nach der geringsten Anzahl berührter Objekte, egal ob sie eindeutig sind oder nicht.
Das heißt, ist es besser, 20 von Produkt A zu zerlegen, als 10 von Produkt A und 5 weitere von Produkt B zu zerlegen?
Letzteres ist näher am Optimum.
Außerdem möchten Sie vermeiden, dass viele Komponenten zurückbleiben, aber in Ihrem aktuellen Code gehen alle zerlegten Komponenten verloren, die nicht vom angeforderten Produkt verwendet werden. Ist das absichtlich (das heißt, willst du die anderen Komponenten wegwerfen), oder ist es ein Fehler?
Die Methode getAssemblyPath legt nur den Pfad zum Abrufen der Elemente fest. Es berührt nicht den eigentlichen Laden. Zu keinem Zeitpunkt weist es self.__items zu. Stellen Sie sich dies als eine Funktion vor, die dem Geschäft eine Anweisung erteilt, was er in der (unmittelbaren) Zukunft tun muss, um die benötigte Menge des benötigten Artikels aus seinem Geschäft zu bekommen.
-
EDIT 2:
Die erste offensichtliche (oder zumindest für mich naheliegende) Methode, dieses Problem anzugehen, besteht darin, zuerst die Produkte zu suchen, die die maximale Anzahl an Komponenten mit dem benötigten Produkt teilen, da Sie bei jeder Demontage mehr benötigte Komponenten erhalten. Aber das führt leider nicht zum optimalen Weg. Zum Beispiel:
Produkt A bestehend aus den Komponenten α, β, γ, δ, ε und ζ.
Produkt B bestehend aus den Komponenten α, β, η, δ, ε und θ.
Produkt C bestehend aus den Komponenten α, β, γ, ι, κ und λ.
Produkt D bestehend aus den Komponenten μ, ν, ξ, δ, ε und ζ.
Wir haben im Geschäft 0 von A, 100 von B, 100 von C und 100 von D. Wir verlangen 10 von A. Wenn wir jetzt zuerst nach den Produkten suchen, die die meisten Komponenten mit A teilen, finden wir B. Wir Demontieren Sie 10 von B und erhalten Sie jeweils 10 von α, β, δ und ε. Aber dann müssen wir 10 von C zerlegen (um γ zu bekommen) und 10 von D (um ζ zu bekommen). Dies wären 40 Aktionen (30 Zerlegen und 10 Montieren). Aber der optimale Weg wäre, 10 von C und 10 von D zu zerlegen (30 Handlungen, 20 Zerlegen und 10 Zusammenbauen).
-
EDIT 3:
Sie müssen keinen Python-Code posten, um das Kopfgeld zu gewinnen. Erklären Sie mir einfach den Algorithmus und zeigen Sie, dass er tatsächlich den optimalen Pfad oder eines der Optima liefert, wenn mehrere existieren.
Hier würde ich dieses Problem lösen. Ich wollte Code dafür schreiben, aber ich glaube nicht, dass ich Zeit habe.
Sie können eine optimale Lösung rekursiv finden. Erstellen Sie eine Datenstruktur, die den Status des Ersatzteilspeichers und der aktuellen Anforderung darstellt. Erstellen Sie nun für jeden benötigten Teil eine Reihe rekursiver Aufrufe, die die verschiedenen Möglichkeiten zum Füllen der Reihenfolge ausprobieren. Der Schlüssel ist, dass Sie einen Teil der Arbeit erledigen, indem Sie versuchen, die Reihenfolge zu füllen, so dass der rekursive Aufruf nun eine etwas einfachere Version desselben Problems ist.
Hier ist ein spezifisches Beispiel, basierend auf Ihrem Beispiel. Wir müssen Bestellungen für Produkt 3 (p3), das aus den Komponenten c1, c3 und c4 besteht, ausfüllen. Unsere Bestellung ist für 20 von p3, und wir haben 10 p3 auf Lager, so füllen wir trivialerweise die Bestellung für die ersten 10 von p3. Jetzt ist unsere Bestellung für 10 von p3, aber wir können es als eine Bestellung für 10 von c1, 10 von c3 und 10 von c4 betrachten. Für den ersten rekursiven Aufruf zerlegen wir ein p1 und füllen eine Reihenfolge für ein einzelnes c1 und legen ein zusätzliches c2 in den Speicher; Also ist dieser rekursive Aufruf für 9 von c1, 10 von c3 und 10 von c4, mit einer aktualisierten Verfügbarkeit im Speicher. Für den zweiten rekursiven Aufruf zerlegen wir ein p2 und füllen eine Reihenfolge für ein c1 und ein c4 und fügen ein zusätzliches c2 in den Speicher ein; Also ist dieser rekursive Aufruf für 9 von c1, 10 von c3 und 9 von c4, mit einer aktualisierten Verfügbarkeit im Speicher.
Da jeder Aufruf das Problem reduziert, wird die rekursive Reihe von Aufrufen beendet. Die rekursiven Aufrufe sollten eine Kostenmetrik zurückgeben, die entweder signalisiert, dass der Aufruf keine Lösung gefunden hat, oder aber angibt, wie viel die gefundene Lösung kostet. Die Funktion wählt die beste Lösung, indem sie die Lösung mit den niedrigsten Kosten wählt.
Ich bin mir nicht sicher, aber vielleicht können Sie das beschleunigen, indem Sie die Anrufe protokollieren. Python hat in der 3.x-Reihe ein wirklich raffiniertes Built-in, functools.lru_cache() ; Da Sie Ihre Frage als "Python 3.2" markiert haben, steht Ihnen diese zur Verfügung.
Was ist Memoisierung und wie kann ich? Verwenden Sie es in Python?
Die Memoisierung funktioniert, indem erkannt wird, dass die Funktion bereits mit den gleichen Argumenten aufgerufen wurde, und dieselbe Lösung wie zuvor zurückgegeben wird. Es ist also ein Cache, der Argumente auf Antworten abbildet. Wenn die Argumente nicht wesentliche Daten enthalten (z. B. wie viele der Komponente c2 im Speicher vorhanden sind), ist es weniger wahrscheinlich, dass die Memoisierung funktioniert. Aber wenn wir uns vorstellen, dass wir die Produkte p1 und p9 haben und p9 die Komponenten c1 und c9 enthält, dann sollte für unsere Zwecke die Zerlegung von p1 oder p9 gleichwertig sein: Sie haben die gleichen Demontagekosten und beide produzieren eine Komponente, die wir brauchen (c1) und eins brauchen wir nicht (c2 oder c9). Wenn wir also die rekursiven Aufrufargumente richtig stellen, könnte die Memo-Anweisung eine sofortige Antwort zurückgeben, wenn wir p9 ausprobieren, und es könnte viel Zeit sparen.
Hmm, jetzt, wo ich darüber nachdenke, können wir% ce_de% wahrscheinlich nicht verwenden, aber wir können einfach selbst memotieren. Wir können einen Cache von Lösungen erstellen: ein Wörterbuch, das Tupel auf Werte abbildet und Tupel erstellt, die nur die Argumente haben, die wir zwischenspeichern wollen. In unserer Funktion überprüfen wir als Erstes den Cache der Lösungen. Wenn dieser Aufruf einer gecachten Lösung entspricht, geben Sie ihn einfach zurück.
EDIT: Hier ist der Code, den ich bisher geschrieben habe. Ich habe das Debuggen noch nicht abgeschlossen, daher liefert es wahrscheinlich noch nicht die richtige Antwort (ich bin mir nicht sicher, weil es lange dauert und ich habe es nicht fertig laufen lassen). Diese Version gibt Wörterbücher weiter, die mit meinen Ideen zum Memoisieren nicht gut funktionieren, aber ich wollte eine einfache Version zum Laufen bringen und mich dann darum kümmern, sie zu beschleunigen.
Auch dieser Code nimmt Produkte auseinander und fügt sie dem Laden als Komponenten hinzu, so dass die endgültige Lösung zuerst etwas wie "Nimm 10 Produkt A" sagen wird und dann wird es sagen "Take 20 component alpha" oder was auch immer. Mit anderen Worten, die Anzahl der Komponenten kann als hoch angesehen werden, da nicht zwischen Komponenten, die sich bereits im Geschäft befanden, und Komponenten, die durch das Zerlegen von Produkten dort platziert wurden, unterschieden wird.
Ich habe jetzt keine Zeit mehr und werde eine Weile nicht daran arbeiten, Entschuldigung.
%Vor%In der Tat, wenn wir N von Produkt X optimal zusammenbauen müssen, nachdem wir (ein aktuelles Lager) optimal ein Produkt zusammengestellt haben, wird die Frage gestellt, (N-1) von Produkt X unter Verwendung von restlichem Lager optimal zusammenzusetzen.
= & gt; Daher ist es ausreichend, einen Algorithmus bereitzustellen, um EINES Produkts X auf einmal optimal zusammenzusetzen.
Suchen Sie für jede Komponente xk alle Produkte, die diese Komponente enthalten. Wir erhalten eine Liste von Produkten für jede Komponente - Produkte A1 (1), .., A1 (i1) haben Komponente x1, Produkte A (1), .., A (i2) haben die Komponente x2 usw. (einige Produkte können in mehreren Listen A1, A2, .., An-Listen enthalten sein).
Wenn eine der Listen leer ist, gibt es keine Lösung.
Wir brauchen eine minimale Menge von Produkten, so dass ein Produkt aus dieser Menge in jeder der Listen enthalten ist. Die einfachste, aber nicht recheneffiziente Lösung ist mit roher Gewalt - versuchen Sie alle Sätze und wählen Sie minimal:
a. Nimm ein einzelnes Produkt von A, wenn es in allen A1, .., An enthalten ist - wir brauchen nur eine Demontage (dieses Produkt). b. Probieren Sie alle Kombinationen von zwei Produkten aus A aus, wenn eine Kombination (a1, a2) die Bedingung erfüllt, dass entweder a1 oder a2 in jeder der Listen A1, .., An enthalten ist - es ist eine Lösung.
...
sicher, es gibt eine Lösung in der Tiefe n - eine Komponente aus jeder der Listen A1, .., An. Wenn wir vorher keine Lösung gefunden haben, ist dies die beste Lösung.
Jetzt müssen wir nur über bessere Strategie nachdenken, dann Brute-Force-Check, was ich für möglich halte - ich muss darüber nachdenken, aber dieser Brute-Force-Ansatz findet sicher eine optimale Lösung.
BEARBEITEN:
Eine genauere Lösung besteht darin, Listen nach Länge zu sortieren. Wenn dann eine Menge von K-Produkten als Lösung geprüft wird, müssen nur alle möglichen Kombinationen von 1 Element aus jeder Liste von ersten K-Listen überprüft werden, wenn keine Lösung da ist - es gibt keine minimale Menge von Tiefe K, die das Problem löst. Diese Art der Überprüfung wird auch rechnerisch nicht so schlimm sein - vielleicht kann es funktionieren ????
Ich denke, hier kommt es darauf an, die potenziellen Kosten für jeden Kauffall zu ermitteln, damit die richtige Kombination von Kauffällen eine Kostenfunktion optimal minimiert. (Dann ist es einfach auf ein Rucksackproblem reduziert)
Was folgt ist wahrscheinlich nicht optimal, aber hier ist ein Beispiel, was ich meine:
1. Jedes Produkt, das das Endprodukt ist, kostet seine tatsächlichen Kosten (in der Währung).
2.Eine Komponente oder ein Produkt, die / das in das Endprodukt (andere separate Produkte / Komponenten) eingebaut werden kann, aber nicht zerlegt werden muss, kostet ihren tatsächlichen Preis (in der Währung) zuzüglich einer kleinen Steuer (tbd).
>3.Ein Bauteil oder Produkt, das die Montage des Endprodukts erleichtern kann, aber zerlegt werden muss, kostet seinen Preis in Währung plus eine kleine Steuer für die Montage in das Endprodukt und eine weitere kleine Steuer für jede Demontage. (vielleicht der gleiche Wert wie die Montagesteuer?).
Hinweis: Diese "Steuern" gelten für alle Unterprodukte, die denselben Fall belegen.
... und so weiter für andere mögliche Fälle
Finden Sie dann alle möglichen Kombinationen von Komponenten und Produkten, die im Laden erhältlich sind und in das Endprodukt eingebaut werden können. Platzieren Sie diese "Assembly-Listen" in eine kostensortierte Liste, die von Ihrer gewählten Kostenfunktion bestimmt wird. Beginnen Sie danach mit dem Erstellen von so vielen der ersten (niedrigsten Kosten) "Assembly-Liste" wie möglich (indem Sie prüfen, ob alle Elemente in der Assembly-Liste noch im Store verfügbar sind - d. H. Sie haben sie bereits für eine vorherige Assembly verwendet). Sobald Sie keinen weiteren Fall erstellen können, müssen Sie ihn aus der Liste entfernen. Wiederholen Sie dies, bis alle benötigten Endprodukte "gebaut" sind.
Hinweis: Jedes Mal, wenn Sie ein Endprodukt "zusammenbauen", müssen Sie einen globalen Zähler für jedes Produkt in der aktuellen "Assembly-Liste" dekrimentären.
Hoffentlich geht die Diskussion in die richtige Richtung. Viel Glück!
Tags und Links python optimization python-3.2