Ich habe also folgendes Problem:
Berechnen Sie die Anzahl der Routen unter Berücksichtigung eines Gitters aus x-mal-y-Dimensionen Dadurch beginnen sie in einer Ecke (sagen wir oben links) und enden in ein anderes (unten rechts) und durchlaufen jeden Scheitelpunkt.
Also zwingt meine derzeitige Methode es einfach nur, indem sie jeden möglichen Weg ausprobiert und diejenigen zählt, die das Ziel erreichen und jeden Knoten durchqueren. Während es funktioniert, ist es O (n ^ 2) und wird extrem schnell unglaublich langsam. Ich bin nicht sicher, wie man es kombinatorisch tut, weil der Pfad jeden Knoten durchqueren muss.
Ich habe komplexere Algorithmen nachgeschlagen, und der Algorithmus von Hierholzer zur Berechnung eulerscher Pfade scheint etwas verwandt, aber nicht perfekt, weil Knoten dafür nicht mehr als einmal durchlaufen werden können.
So wie es ist, funktioniert mein Programm, aber schlecht, und ich möchte es effizienter machen. Gibt es bessere Algorithmen, die ich verwenden könnte?
Bearbeiten Danke für die Antworten bisher. Nur um zu verdeutlichen, sind alle Knoten im 2D-Gitter mit n / e / s / w verbunden
Außerdem muss das Gitter kein Quadrat sein
Es gibt nicht viel, was Sie tun können, weil es ein Hamilton-Pfadproblem ist, das NP-vollständig ist.
>Sie dürfen jedoch tatsächlich nach etwas anderem suchen und dem Problem, das Sie lösen möchten, einige Einschränkungen hinzufügen ...
Wie @JanDvorak festgestellt hat, ist Ihre spezifische Einschränkung , dass Sie ein quadratisches Gitter verwenden. Meine bisherigen Ergebnisse:
Wenn x gerade ist, gibt es keine Möglichkeit, alle Ecken beginnend von der oberen linken Ecke bis unten rechts zu durchlaufen. Beweis:
Lässt gerichtete Bewegungen entlang von Achsen zählen, z. up ist -1 , down ist 1 , links ist -1 , richtig -1 . Mit x x x Raster wäre Ihre gesamte Bewegung 2*x . An jedem Scheitelpunkt (außer dem letzten) wählen Sie nur eine Richtung aus. Also, wenn es eine gerade Anzahl von Eckpunkten gibt, die du durchlaufen musst, wäre deine Gesamtbewegung gerade und umgekehrt für ungerade. Wenn x gerade ist, dann gibt es eine ungerade Anzahl von Scheitelpunkten, aber die totale Bewegung ist immer noch gleich = & gt; Sie können keinen Weg finden.
Zunächst einmal, wenn x gerade ist, gibt es ein einfaches Paritätsargument, das zeigt, dass die Antwort immer Null ist; Überprüfen Sie das Gitter und beachten Sie, dass die Quadrate oben links und unten rechts die gleiche Farbe haben, und diese Farbe kann nicht zuerst und n 2 beobachtet werden, da n 2 ist sogar während 1 ungerade ist.
Wenn x ungerade ist, weiß ich nicht, wie ich die Pfade zählen soll, aber bemerke, dass die Gesamtzahl zumindest exponentiell schnell anwächst: Jede Durchquerung eines n * n-Gitters kann auf zwei verschiedene Durchläufe von a (n +2) * (n + 2) Gitter. Sie erhalten einen, indem Sie die obere Reihe entlanggehen, links entlang der zweiten Reihe, entlang der ersten Spalte entlang der zweiten Spalte und dann auf den verbleibenden Quadraten die n * n-Gitter-Traversierung durchführen; Sie erhalten die andere, indem Sie die ersten zwei Zeilen und Spalten in umgekehrter Reihenfolge abdecken.
Dies sollte Ihnen sagen, dass eine Brute-Force-Lösung wahrscheinlich nicht sehr gut funktioniert.
Ich habe in diesem Semester mit solchen Problemen zu einem Thema gearbeitet. Ich denke, man könnte sich metaheuristische Algorithmen wie uns anschauen:
Sie möchten vielleicht mit roher Gewalt bleiben, außer Sie brauchen wirklich eine Verbesserung; weil sie ziemlich komplex sind.