Die eigentliche Frage lautet so:
McDonald's plant eine Anzahl von Gelenken (n) entlang einer geraden Autobahn zu öffnen. Diese Verbindungen erfordern Lagerhäuser, um ihre Lebensmittel zu lagern. Ein Lagerhaus kann Lebensmittel für eine beliebige Anzahl von Verbindungen lagern, muss jedoch nur an einer der Verbindungen angeordnet sein. McD hat eine begrenzte Anzahl von Lagern (zB k) zur Verfügung und möchte sie so platzieren, dass die durchschnittliche Entfernung der Verbindungen von ihrem nächsten Lagerhaus minimiert wird.
Geben Sie ein Array (n Elemente) der Koordinaten der Gelenke und eine ganze Zahl 'k' zurück und geben Sie ein Array von 'k' Elementen zurück, die die Koordinaten für die optimale Positionierung von Lagern angeben.
Tut mir leid, ich habe keine Beispiele verfügbar, da ich dies aus dem Speicher schreibe. Wie auch immer, ein Beispiel könnte sein:
array = {1,3,4,5,7,7,8,10,11} (n = 9)
k = 1
Antwort: {7}
Das ist, was ich mir gedacht habe: Für k = 1 können wir einfach den Median der Menge herausfinden, der den optimalen Standort des Lagers geben würde. Für k & gt; 1 sollte der gegebene Satz jedoch in "k" Teilmengen (disjunkt und von zusammenhängenden Elementen der Obermenge) unterteilt sein, und der Median für jede Teilmenge würde die Lagerstandorte ergeben. Ich verstehe jedoch nicht, auf welcher Grundlage die 'k' Teilmengen gebildet werden sollten. Vielen Dank im Voraus.
BEARBEITEN: Es gibt auch eine Variante für dieses Problem: Minimieren Sie die maximale Entfernung zwischen einer Verbindung und ihrem nächstgelegenen Warenlager, statt Summe / Durchschnitt. Ich verstehe das auch nicht.
Die Straight Highway macht dies zu einer Übung in der dynamischen Programmierung, die von links nach rechts entlang der Autobahn arbeitet. Eine Teillösung kann durch den Standort des am weitesten rechts gelegenen Lagers und die Anzahl der platzierten Lager beschrieben werden. Die Kosten für die Teillösung sind die Gesamtstrecke zum nächsten Lager (für fixed k minimiert dies die Minimierung der Abweichung) oder die maximale Entfernung bis zum nächsten Lager.
In jeder Phase haben Sie die Antworten für die am weitesten links gelegenen N-Verbindungen ausgearbeitet und lassen sich anhand der Anzahl der verwendeten Lager und der Position des am weitesten rechts liegenden Lagers indexieren. Sie müssen nur die besten Kosten sparen. Betrachten Sie nun das nächste Gelenk und erarbeiten Sie die beste Lösung für N + 1 Gelenke und alle möglichen Werte von k und rechtmässigem Lagerhaus. Verwenden Sie die Antworten, die Sie für N Gelenke gespeichert haben, um dies zu beschleunigen. Sobald Sie die beste Kostenlösung für alle Verbindungen ausgearbeitet haben, wissen Sie, wo sich das rechte Lager befindet. So haben Sie die Position eines einzigen Lagers. Gehen Sie zurück zu der Lösung, die dieses Lager als das rechte Gelenk hat, und finden Sie heraus, auf welcher Lösung es basiert. Das gibt Ihnen ein weiteres rechtes Lager - und Sie können sich auf dem Weg zum Standort aller Lagerhäuser nach der besten Lösung arbeiten.
Ich neige dazu, die Kosten dafür zu bekommen, dies falsch zu machen, aber mit N Gelenken und K Lagern, um Sie haben N Schritte zu nehmen, jeder auf der Grundlage von nicht mehr als Nk vorherige Lösungen, so denke ich, Kosten ist kN ^ 2.
Dies ist KEIN Clustering-Problem, sondern ein Spezialfall eines Standortproblems. Sie können es mit einem allgemeinen Integer / Linear-Programming-Paket lösen, aber da das Problem auf einer Linie liegt, könnte es effizientere (und weniger teure softwareseitige) Algorithmen geben, die funktionieren würden. Sie könnten dynamische Programmierung in Betracht ziehen, da es wahrscheinlich eine Kombination von Einrichtungen gibt, die ziemlich schnell beseitigt werden könnten. Sehen Sie sich das P-Median-Problem für weitere Informationen an.
Tags und Links algorithm optimization c++ dynamic