Forum: Knobelecke

Allgemein bekannt ist das Springerproblem: welchen Weg muss ein Springer auf einem ansonsten leeren Schachbrett wählen, wenn er jedes Feld einmal erreichen will und keines doppelt?

Für dieses Problem gibt es zahlreiche Lösungen; die offensichtliche ist einfach Brute Force und funktioniert immer, dauert aber unter Umständen etwas lange.

Im guten alten Jahr 1823 hat daher ein gewisser Herr Warnsdorff folgende Regel entworfen: der Springer zieht immer auf das Feld mit den wenigsten Zugmöglichkeiten.

Diese einfache Regel ist im Vergleich zu Brute Force um Größenordnungen schneller, aber wie uns der Wikipedia-Artikel zum Springerproblem erklärt, gerät der Warnsdorff-Algorithmus unter Umständen in eine Sackgasse.

Das Rätsel: warum kann die Warnsdorff-Regel keine Lösung garantieren?

Ich habe dafür einen Beweis konstruiert, der nicht allzu schwer zu finden ist, habe aber noch kein konkretes Gegenbeispiel gefunden. Wer den Beweis findet, erhält wie gewöhnlich Ruhm und Ehre; wer mir ein Gegenbeispiel angeben kann dass auf der Warnsdorff-Regel beruht, erhält Ruhm, Ehre und eine Flasche saarländisches Bier per Eilpost.

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Huhu Philip,

Zitat:

Das Rätsel: warum kann die Warnsdorff-Regel keine Lösung garantieren?

Sie lässt proportional zu Grösse des Feldes mehr Möglichkeiten zu, gleichzeitig sinken mit der Vergrösserung des Feldes die Möglichkeiten zum Erfolg.
Im übrigen versagt sie schon bei 3/4, wenn man in der Ecke anfängt.

Das ist kein Algo und keine Regel, sondern einfach nur ne Strategie

Bis denne

Martin

--
0xC0FFEE

 

Wußte ich's doch, dass Du Dich gleich meldest, wenn's um Bier geht :>

Hast Du eine konkrete Zugfolge, die zum Misserfolg führt?




Hier mal mein Beweis; ich bin mir neuerdings nicht mehr so sicher, ob das tatsächlich so stimmt, vielleicht hat jemand eine brauchbare Kritik?


Also: die Felder eines Schachbrettes können als Knoten in einem Graph G aufgefasst werden. Die Kanten des Graphs werden durch die möglichen Züge des Springers festgelegt. Das Springerproblem auf dem Schachbrett ist dann äquivalent zur Suche nach einem Hamilton-Pfad in G.

Um das Springerproblem zu lösen, besucht man laut Definition jedes Feld genau einmal, also insgesamt NxN Besuche. Nach der Warnsdorff-Regel muss pro Zug das Feld mit der geringsten Anzahl an Folgezügen ermittelt werden. Der Springer erreicht pro Zug maximal 8 Felder; für jedes dieser Felder muss der Springer 7 Felder untersuchen (von einem dieser Felder kommt er ja gerade, deshalb nicht 8). Warnsdorff braucht also N*N*8*7 Schritte, um das Springerproblem zu lösen. Das Springerproblem läge also in O(N^2).

Dagegen liegt das Problem, einen Hamilton-Pfad zu finden, in NP.

Würde Warnsdorff immer funktionieren, hätten wir also einen Algorithmus mit polynomieller Laufzeit zur Lösung eines Problems aus NP.

Drei Möglichkeiten:

- P = NP (her mit der Fields-Medaille!)
- Warnsdorff kann nicht immer eine Lösung garantieren
- ich habe einen Fehler in der Beweisführung gemacht


Findet jemand gegen diese Argumentation einen Einwand?

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Hi Philip,

Zitat:
Das Springerproblem läge also in O(N^2).

Ich hab mich nicht detailiert mit dem Problem beschäftigt, sondern nur den Wikipedia-Artikel überflogen, aber da steht

Zitat:
Das Hamiltonpfadproblem ist NP-vollständig, ein effizienter Lösungsalgorithmus ist also nicht bekannt und existiert, wie allgemein vermutet wird, auch nicht. Dagegen existieren für das Springerproblem effiziente Algorithmen, die unten vorgestellt werden.

Zitat:
... verschiedene Algorithmen, mit denen für beliebig große Felder eine Lösung in linearer Zeit gefunden werden kann.

.

Bleibt wohl bei P != NP ... Hätt dir die Fields-Medaille vergönnt, wird aber wohl noch ein bisschen dauern :-P

mfg, Wolfgang

--
Hex, Bugs and Rock 'n Roll

 

Hi,
die Komplexität des Allgemeinen Problems (Hamilton-Pfad auf beliebigen Graphen) ist nur eine obere Schranke für die Komplexität eines Spezialfalles des Problems. Deshalb ergibt sich aus O(Springerproblem) < O(Hamilton-Pfad-Problem) keinerlei Widerspruch.