Ich habe für einen bevorstehenden Programmierwettbewerb geübt und bin auf eine Frage gestoßen, die mich nur völlig verwirrt. Ich habe jedoch das Gefühl, dass es ein Konzept ist, das ich jetzt lernen sollte, anstatt die Daumen zu drücken, dass es nie auftaucht.
Grundsätzlich handelt es sich um eine Ritterfigur auf einem Schachbrett. Sie erhalten zwei Eingaben: Startort und Endort. Das Ziel ist es, den kürzesten Weg zu berechnen und auszudrucken, den der Ritter nehmen kann, um zum Zielort zu gelangen.
Ich habe mich nie mit Dingen befasst, die dem kürzesten Weg ähneln, und ich weiß nicht einmal, wo ich anfangen soll. Welche Logik verwende ich, um dies anzugehen?
PS Wenn es von Bedeutung ist, möchten sie, dass Sie die normalen Bewegungen des Ritters ergänzen, indem Sie ihm erlauben, sich zu den vier Ecken des Quadrats zu bewegen, die durch die (möglicherweise) acht Bewegungen gebildet werden, die ein Ritter ausführen kann, vorausgesetzt, die Mitte des Quadrats ist der Standort des Ritters.
quelle
Antworten:
Sie haben hier ein Diagramm, in dem alle verfügbaren Züge verbunden sind (Wert = 1) und nicht verfügbare Züge getrennt sind (Wert = 0). Die Matrix mit geringer Dichte lautet wie folgt:
Der kürzeste Weg von zwei Punkten in einem Diagramm kann mithilfe von http://en.wikipedia.org/wiki/Dijkstra's_algorithm gefunden werden
Pseudocode von der Wikipedia-Seite:
BEARBEITEN:
Introduction to Algorithms
ISBN 0-262-03384-4. Oder versuchen Sie es mit Wikipedia, http://en.wikipedia.org/wiki/List_of_algorithmsquelle
EDIT: Siehe Simons Antwort , in der er die hier vorgestellte Formel korrigierte.
Tatsächlich gibt es eine O (1) -Formel
Dies ist ein Bild, das ich gemacht habe, um es zu visualisieren (Quadrate, die ein Ritter am N- ten erreichen kann Zug , sind mit derselben Farbe gemalt).
Kannst du das Muster hier bemerken?
Obwohl wir das Muster sehen können, ist es wirklich schwierig, die Funktion zu finden, die
f( x , y )
die Anzahl der Bewegungen zurückgibt, die erforderlich sind, um vom Quadrat zu gehen( 0 , 0 )
zu Quadrat zu gelangen( x , y )
Aber hier ist die Formel, die funktioniert, wenn
0 <= y <= x
Hinweis: Diese Frage wurde am ersten Tag von SACO 2007 gestellt. Hier finden Sie
Lösungen
quelle
2 * floor((y - delta) / 3) + delta
und seindelta - 2 * floor((delta - y) / 4)
. Dies ist eine offizielle Lösung von dieser Wettbewerbsseite, aber sie ist falsch. Diese erste Gleichung (vonif
) gibt falsche Antworten zurück. Auf dem Schachbrett [-1000..1000] x [-1000..1000], das 2001x2001 groß (aber logisch unbegrenzt) ist, zählt die angegebene Antwort 2.669.329 von 4.004.001 korrekten Feldern (66,66%). Kennt jemand die funktionierende Lösung ohne Schleifen?Hier ist eine korrekte O (1) -Lösung, aber für den Fall, dass sich der Ritter nur wie ein Schachritter und auf einem unendlichen Schachbrett bewegt:
https://jsfiddle.net/graemian/5qgvr1ba/11/
Der Schlüssel, um dies zu finden, besteht darin, die Muster zu bemerken, die beim Zeichnen der Tafel auftreten. In der folgenden Abbildung ist die Anzahl auf dem Quadrat die Mindestanzahl von Zügen, die erforderlich sind, um dieses Quadrat zu erreichen (Sie können die Breitensuche verwenden, um dies zu finden):
Da die Lösung über die Achsen und Diagonalen symmetrisch ist, habe ich nur den Fall x> = 0 und y> = x gezeichnet.
Der untere linke Block ist die Startposition und die Zahlen in den Blöcken geben die minimale Anzahl von Zügen an, um diese Blöcke zu erreichen.
Es gibt 3 Muster zu beachten:
(Stellen Sie sicher, dass Sie beide Diagonalsätze von oben links nach unten rechts sehen. Sie haben eine konstante Bewegungsanzahl. Die Diagonalen unten links oben rechts sind viel komplexer.)
Sie können jeweils Formeln ableiten. Die gelben Blöcke sind Sonderfälle. So wird die Lösung:
Am schwierigsten sind die vertikalen Gruppen:
Siehe die Geige für die anderen Fälle.
Vielleicht gibt es einfachere oder elegantere Muster, die ich vermisst habe? Wenn ja, würde ich sie gerne sehen. Insbesondere bemerke ich einige diagonale Muster in den blauen vertikalen Fällen, aber ich habe sie nicht untersucht. Unabhängig davon erfüllt diese Lösung immer noch die O (1) -Beschränkung.
quelle
Sehr interessantes Problem, auf das ich kürzlich gestoßen bin. Nachdem ich einige Lösungen gesucht hatte, wurde versucht,
O(1) time and space complexity
die in SACO 2007 Day 1- Lösungen angegebene analytische Formel ( ) wiederherzustellen .Zunächst möchte ich Graeme Pyle für eine sehr schöne Visualisierung schätzen, die mir geholfen hat, die Formel zu korrigieren.
Aus irgendeinem Grund (vielleicht zur Vereinfachung oder Schönheit oder nur wegen eines Fehlers) haben sie das
minus
Zeichen in denfloor
Operator verschoben , was dazu führt, dass sie eine falsche Formel habenfloor(-a) != -floor(a) for any a
.Hier ist die richtige analytische Formel:
Die Formel funktioniert für alle (x, y) Paare (nach Anwendung von Achsen und diagonaler Symmetrie) mit Ausnahme von (1,0) und (2,2) Eckfällen, die dem Muster nicht entsprechen und im folgenden Snippet fest codiert sind:
Hinweis: Die nur zur Veranschaulichung verwendete jQuery, Code siehe
distance
Funktion.quelle
Ja, Dijkstra und BFS werden Ihnen die Antwort geben, aber ich denke, der Schachkontext dieses Problems liefert Wissen, das eine Lösung liefern kann, die viel schneller ist als ein generischer Algorithmus für kürzeste Wege, insbesondere auf einem unendlichen Schachbrett.
Beschreiben wir der Einfachheit halber das Schachbrett als (x, y) -Ebene. Das Ziel besteht darin, den kürzesten Weg von (x0, y0) nach (x1, y1) nur mit den Kandidatenschritten (+ -1, + -2), (+ -2, + -1) und (+ -2) zu finden , + -2), wie in der PS der Frage beschrieben
Hier ist die neue Beobachtung: Zeichnen Sie ein Quadrat mit den Ecken (x-4, y-4), (x-4, y + 4), (x + 4, y-4), (x + 4, y + 4). . Dieses Set (nennen wir es S4) enthält 32 Punkte. Der kürzeste Weg von einem dieser 32 Punkte zu (x, y) erfordert genau zwei Züge .
Der kürzeste Weg von einem der 24 Punkte in der Menge S3 (ähnlich definiert) zu (x, y) erfordert mindestens zwei Züge .
Wenn also | x1-x0 |> 4 oder | y1-y0 |> 4 ist, ist der kürzeste Weg von (x0, y0) nach (x1, y1) genau zwei Züge größer als der kürzeste Weg von (x0, y0) nach S4. Und das letztere Problem kann mit einfacher Iteration schnell gelöst werden.
Sei N = max (| x1-x0 |, | y1-y0 |). Wenn N> = 4 ist, hat der kürzeste Weg von (x0, y0) nach (x1, y1) Ceil (N / 2) -Schritte.
quelle
Die obige O (1) -Antwort [ https://stackoverflow.com/a/8778592/4288232 von Mustafa Serdar Şanlı] funktioniert nicht wirklich. (Überprüfen Sie (1,1) oder (3,2) oder (4,4), abgesehen von den offensichtlichen Randfällen von (1,0) oder (2,2)).
Unten ist eine viel hässlichere Lösung (Python), die funktioniert (mit zusätzlichen "Tests"):
quelle
above
oderbelow
funktioniert nicht wirklich auf SO.Was Sie tun müssen, ist, sich die möglichen Bewegungen des Ritters als Grafik vorzustellen, wobei jede Position auf dem Brett ein Knoten ist und die möglichen Bewegungen zu einer anderen Position als Kante. Der dijkstra-Algorithmus ist nicht erforderlich, da jede Kante das gleiche Gewicht oder den gleichen Abstand hat (sie sind alle genauso einfach oder kurz). Sie können einfach eine BFS-Suche von Ihrem Startpunkt aus durchführen, bis Sie die Endposition erreichen.
quelle
Lösung aus ersten Prinzipien in Python
Ich habe dieses Problem zum ersten Mal in einem Codility-Test festgestellt. Sie gaben mir 30 Minuten, um es zu lösen - ich brauchte erheblich länger, um zu diesem Ergebnis zu gelangen! Das Problem war: Wie viele Züge braucht ein Ritter, um von 0,0 nach x, y zu gelangen, wobei nur legale Ritterzüge verwendet werden. x und y waren mehr oder weniger unbegrenzt (wir sprechen hier also nicht von einem einfachen 8x8-Schachbrett).
Sie wollten eine O (1) -Lösung. Ich wollte eine Lösung, bei der das Programm das Problem eindeutig löste (dh ich wollte etwas offensichtlich Richtiges als Graemes Muster - Muster haben die Angewohnheit, dort zusammenzubrechen, wo man nicht hinschaut), und ich wollte mich wirklich nicht auf ein verlassen müssen unargierte Formel, wie in Mustafas Lösung
Also, hier ist meine Lösung für das, was es wert ist. Beginnen Sie wie andere, indem Sie feststellen, dass die Lösung symmetrisch zu den Achsen und Diagonalen ist, sodass wir nur nach 0> = y> = x lösen müssen. Zur Vereinfachung der Erklärung (und des Codes) werde ich das Problem umkehren: Der Ritter beginnt bei x, y und strebt 0,0 an.
Nehmen wir an, wir verkleinern das Problem auf die Nähe des Ursprungs. Wir werden zu gegebener Zeit herausfinden, was "Umgebung" eigentlich bedeutet, aber jetzt schreiben wir einfach einige Lösungen in ein Cheatsheet (Ursprung unten links):
Wenn also x, y im Raster angegeben sind, können wir einfach die Anzahl der Bewegungen zum Ursprung ablesen.
Wenn wir außerhalb des Gitters angefangen haben, müssen wir uns zurückarbeiten. Wir führen die 'Mittellinie' ein, die durch y = x / 2 dargestellt wird. Jeder Ritter bei x, y auf dieser Linie kann sich mit einer Reihe von 8-Uhr-Zügen (dh (-2, -1) Zügen) zum Cheatsheet zurückarbeiten. Wenn x, y über der Mittellinie liegt, benötigen wir eine Folge von 8 Uhr und 7 Uhr, und wenn es unter der Mittellinie liegt, benötigen wir eine Folge von 8 Uhr und 10 Uhr Die Uhr bewegt sich. Zwei Dinge, die hier zu beachten sind:
Schauen wir uns also die Bewegungen über der Mittellinie an. Was wir behaupten ist, dass:
(dx; dy) = (2,1; 1,2) (n8; n7) (Matrixnotation ohne mathematischen Satz - Spaltenvektor (dx; dy) entspricht der quadratischen Matrix multipliziert mit dem Spaltenvektor (n8; n7) - der Anzahl der 8-Uhr-Züge und Anzahl der 7-Uhr-Züge) und ähnlich;
(dx; dy) = (2,2; 1, -1) (n8; n10)
Ich behaupte, dass dx, dy ungefähr (x, y) sein wird, also (x-dx, y-dy) in der Nähe des Ursprungs (was auch immer sich als "Umgebung" herausstellt).
Die beiden Zeilen im Code, die diese Begriffe berechnen, sind die Lösung für diese, aber sie wurden ausgewählt, um einige nützliche Eigenschaften zu haben:
(Möchten Sie Beweise dafür?) Die Entfernung des Ritters ist also die Summe aus n7, n8, n10 und Cheatsheet [x-dx, y-dy], und unser Cheatsheet reduziert sich auf Folgendes:
Dies ist noch nicht das Ende der Geschichte. Schauen Sie sich die 3 in der unteren Reihe an. Die einzigen Möglichkeiten, wie wir dies erreichen können, sind entweder:
Es gibt eine ähnliche Optimierung mit der 4 oben rechts. Abgesehen davon, dass Sie dort beginnen, können Sie dies nur mit einer 8-Uhr-Bewegung von (4,3) erreichen. Das steht nicht auf dem Cheatsheet, aber wenn es dort wäre, wäre seine Entfernung 3, weil wir stattdessen 7 Uhr auf (3,1) hätten haben können, was eine Entfernung von nur 2 hat. Also sollten wir eine zurückverfolgen Bewegen Sie sich um 8 Uhr und gehen Sie dann um 7 Uhr vorwärts.
Also müssen wir dem Cheatsheet noch eine Nummer hinzufügen:
(Hinweis: Es gibt eine ganze Reihe von Back-Tracking-Optimierungen von (0,1) und (0,2), aber da der Löser uns niemals dorthin bringt, müssen wir uns keine Sorgen machen.)
Hier ist also ein Python-Code, um dies zu bewerten:
Wenn Sie übrigens eine tatsächliche Route kennen möchten, bietet dieser Algorithmus auch Folgendes: Es handelt sich lediglich um eine Folge von n7 7-Uhr-Bewegungen, gefolgt von (oder durchsetzt mit) n8 8-Uhr-Bewegungen, n10 10- Die Uhr bewegt sich und welcher Tanz auch immer vom Cheatsheet diktiert wird (der sich selbst in einem Cheatsheet befinden kann).
Nun: Wie man das beweist, ist richtig. Es reicht nicht aus, diese Ergebnisse nur mit einer Tabelle mit richtigen Antworten zu vergleichen, da das Problem selbst unbegrenzt ist. Aber wir können sagen, wenn der Abstand des Ritters von einem Quadrat s d ist, dann muss der Abstand des Ritters von (s + m) entweder d-1 oder d + 1 sein, wenn {m} die Menge der legalen Bewegungen von s ist für alle m. (Benötigen Sie einen Beweis dafür?) Außerdem muss es mindestens ein solches Quadrat geben, dessen Abstand d-1 ist, es sei denn, s ist der Ursprung. Wir können also die Richtigkeit beweisen, indem wir zeigen, dass diese Eigenschaft für jedes Quadrat gilt. So:
Alternativ können wir die Richtigkeit eines beliebigen Quadrats beweisen, indem wir die Route von s bergab zum Ursprung verfolgen. Überprüfen Sie zuerst s auf Angemessenheit wie oben und wählen Sie dann s + m so aus, dass der Abstand (s + m) == d-1 ist. Wiederholen, bis wir den Ursprung erreichen.
Howzat?
quelle
Ich habe Graphen noch nicht studiert. Aufgrund des Problems, sie durch einfache Arrays zu implementieren, konnte ich keine andere Lösung als diese ableiten. Ich behandelte die Positionen nicht als Ränge und Dateien (die übliche Schachnotation), sondern als Array-Indizes. Zu Ihrer Information, dies ist nur für ein 8 * 8-Schachbrett. Verbesserungsvorschläge sind immer willkommen.
* Die Kommentare sollten für Ihr Verständnis der Logik ausreichen. Sie können jedoch immer fragen.
* Überprüft auf DEV-C ++ 4.9.9.2 Compiler (Bloodshed Software).
quelle
Ich denke, dass dies auch Ihnen helfen könnte ..
und Verwenden der dynamischen Programmierung, um die Lösung zu erhalten.
PS: Es verwendet das BFS, ohne sich die Mühe machen zu müssen, die Knoten und Kanten des Graphen zu deklarieren.
quelle
Hier ist eine Lösung für dieses spezielle Problem, das in Perl implementiert ist. Es wird einer der kürzesten Wege angezeigt - in einigen Fällen kann es mehr als einen geben.
Ich habe keinen der oben beschriebenen Algorithmen verwendet - aber es wäre schön, ihn mit anderen Lösungen zu vergleichen.
quelle
quelle
Nur Ruby-Code aus Graeme Pyles Antwort-Jsfiddle oben , der den gesamten zusätzlichen Code gestreift und in Ruby umgewandelt wurde, um eine Lösung durch seinen Algorithmus zu erhalten, scheint zu funktionieren. Trotzdem testen:
Die einzige Absicht ist es, jemandem Zeit beim Konvertieren von Code zu sparen, wenn jemand vollständigen Code benötigt.
quelle
Hier ist die PHP-Version von Jules Mays Funktion
quelle
Hier ist mein Programm. Dies ist keine perfekte Lösung. In der Rekursionsfunktion müssen viele Änderungen vorgenommen werden. Aber dieses Endergebnis ist perfekt. Ich habe versucht, ein bisschen zu optimieren.
quelle
Hier ist eine C-Version, die auf dem Code von Mustafa Serdar Şanlı basiert und für ein Finit Board funktioniert:
Testen Sie es hier mit einem Beweis gegen eine rekursive Lösung
quelle