In dieser Antwort nehme ich an, dass Perlen nur einmal bewegt werden können. Sonst wäre es offensichtlich, dass Perlen nur ein Quadrat nach dem anderen bewegen sollten, was dieses Problem viel weniger interessant macht: Die Summe der Quadrate würde auf eine einfache Summe von Zügen zurückgehen.

Das Problem kann in O (n) Zeit gelöst werden, und unter Punkt 4 gebe ich eine JavaScript-Implementierung. Wenn Sie die Argumentation, die zum Algorithmus führt, überspringen möchten, scrollen Sie einfach zu diesem Abschnitt.

Bearbeiten: Ich habe einen Abschnitt B hinzugefügt, in dem eine Variante des Problems analysiert wird.

Aber hier sind die Beobachtungen, die zu dem vorgeschlagenen Algorithmus für die vorliegende Frage führen:

1. Kein Überholen

Es sollte beachtet werden, dass die Perlen in einer optimalen Lösung niemals so bewegt werden, dass eine Perle eine andere "überholt". Die alternative Lösung, wo diese beiden Perlen wären tauschen Sie ihre Ziel-Slots würden immer eine niedrigere Summe von Quadraten geben.

Um dies ein wenig zu formalisieren, nehmen wir an, eine Perle bewegt sich von der Steckplatznummer a zu b und eine andere von c zu d . Es ist erforderlich, dass sie sich nicht gegen den Uhrzeigersinn bewegen können. Nehmen wir an, der erste überholt den anderen, dann haben wir alle diese Wahrheiten:

Dann vergleichen die Quadrate der Züge der überholenden Version und die Quadrate der Züge der alternativen Version (wo die Kugeln Ziele wechseln):

Beweis ist, dass die obige Ungleichung zu:

Dies hat zur Folge, dass die Perlen, die sich am Anfang den gleichen Slot teilen, immer in benachbarten Slots in der optimalen Lösung landen.

Allgemeiner:

2. Betrachte nur Lösungen, bei denen die Perlen in der gleichen Reihenfolge bleiben.

Also - wenn wir den Perlen, die im selben Slot beginnen, eine (willkürliche) Reihenfolge geben - können wir sagen, dass eine optimale Lösung gefunden werden kann, wenn die Reihenfolge der Perlen die gleiche ist wie in der ursprünglichen Eingabe (seit Überholen ist ausgeschlossen).

Dies bedeutet auch, dass wir ganz einfach eine Kandidatenlösung finden können, bei der wir die Perlen nach Auftragsnummer aufnehmen und sie mit derselben Bestellnummer in den Schacht legen. Dies könnte nicht die optimale Lösung sein, aber es könnte sein. Es könnte sogar ungültig sein, wenn es eine Bewegung gegen den Uhrzeigersinn enthält. Aber es ist immer noch nützlich, mit zu beginnen.

3. Zykluslösung auf optimale Eins

Jede andere mögliche Lösung, die die gleiche Reihenfolge beibehält, wird gefunden, indem einfach alle Perlen zum nächsten Schlitz bewegt werden, bis eine gültige und beste Lösung gefunden wird. Ich werde eine solche Bewegung einen Zyklus nennen.

Wenn die erste Kandidatenlösung wegen einer Bewegung gegen den Uhrzeigersinn ungültig ist, ist es einfach, die beste Lösung zu finden: Nimm die größte Bewegung gegen den Uhrzeigersinn und füge das Gegenteil dieser Bewegung zu allen Bewegungen hinzu, einschließlich dieser . Dadurch werden alle angreifenden Züge nicht gegen den Uhrzeigersinn (mindestens eine wird eine Null-Bewegung sein). Durch das weitere Radfahren wird die Summe der Quadrate offensichtlich größer. Das ist also die optimale Lösung.

Wenn andererseits die Kandidatenlösung gültig ist, aber keine der Perlen in Position bleibt, kann die Lösung verbessert werden, indem umgekehrt umgegangen wird, dh indem die Bewegungen kleiner gemacht werden, bis mindestens eine Perle in Position bleibt .

4. Algorithmus

Mit allen oben genannten Informationen präsentiere ich hier den in JavaScript implementierten Algorithmus, der in diesem Live-Ausschnitt getestet werden kann:

Dieses Snippet verwendet ein Array, bei dem jeder Index einen Slot darstellt und der Wert die Anzahl der Beads in diesem Slot darstellt. Es gibt das ursprüngliche Array, die Summe der Quadrate der optionalen Lösung und die Liste der Bewegungen für die Perlen aus.

Ausgabe für das Beispielproblem in der Frage ist:

Die Antwort auf die Beispielkonfiguration lautet also: 60 Dollar.

B. Nachtrag: Ohne Anforderung im Uhrzeigersinn

Was wäre, wenn die Notwendigkeit für Bewegungen im Uhrzeigersinn entfernt würde und Bewegungen in irgendeine Richtung gehen könnten? Das wurde nicht gefragt, aber ich dachte, es wäre eine interessante Variante.

Hier sind die zusätzlichen Beobachtungen, die für diesen Fall gelten:

B.1. Die Summe der Quadrate einer Lösung kann für das nächste

Ein Zyklus muss nicht wirklich ausgeführt werden, um die Summe der Quadrate dieser neuen Konfiguration zu finden:

Nehmen wir an, wir haben drei Perlen und drei Schlitze, und die Perlen wurden jeweils in ihre Ziel-Slots verschoben, indem man sie jeweils in x, y und z Slots bewegt. Zum Beispiel, wenn sie alle in Slot 0 wären, könnten wir x, y, z -Werte von 0, 1, 2 bekommen (aber auch -1, 0, 1 oder sogar 5, 6, 7, falls wir wollen übertreiben).

Die Summe der Quadrate ist:

Wenn wir nun diese Lösung durchgehen und somit der Bewegung jeder Perle einen zusätzlichen Platz hinzufügen, werden die Quadrate zu:

oder:

Wenn man eine Konfiguration mit n Kügelchen so zyklisiert, erhöht sich im Allgemeinen die Summe der Quadrate mit diesem Ausdruck:

Also kann der Algorithmus daraus Nutzen ziehen und schnell die Summe der Quadrate der Lösung berechnen, die aus einem Zyklus resultiert. Dies kann für nachfolgende Zyklen wiederholt werden.

B.2. Nur ein lokales Minimum für Quadratsumme

Schließlich ist die Summe der Quadrate für jeden aufeinanderfolgenden Zyklus (Lösung) eine Funktion mit einer parabolischen Form, d. h. sobald ein lokales Minimum gefunden wurde, besteht keine Notwendigkeit, nach einem anderen zu suchen; da ist es nicht. Das können wir anhand der obigen Formel für steigende Werte für sum(moves) sehen. Wir könnten höchstens die gleiche Quadratsumme für zwei benachbarte Zyklen haben.

B.3. Algorithmus

Hier folgt der in JavaScript implementierte Algorithmus:

Dieses Snippet verwendet ein Array, bei dem jeder Index einen Slot darstellt und der Wert die Anzahl der Beads in diesem Slot darstellt. Es gibt das ursprüngliche Array, die Summe der Quadrate der optionalen Lösung und die Liste der Bewegungen für die Perlen aus.

Ausgabe für das Beispielproblem in der Frage ist:

NB: Dies ist nicht die Antwort auf die Frage, weil es Bewegungen gegen den Uhrzeigersinn erlaubt. Für die Antwort, sehen Sie die erste Hälfte dieser Antwort.