Du bist nicht angemeldet.

Stilllegung des Forums
Das Forum wurde am 05.06.2023 nach über 20 Jahren stillgelegt (weitere Informationen und ein kleiner Rückblick).
Registrierungen, Anmeldungen und Postings sind nicht mehr möglich. Öffentliche Inhalte sind weiterhin zugänglich.
Das Team von spieleprogrammierer.de bedankt sich bei der Community für die vielen schönen Jahre.
Wenn du eine deutschsprachige Spieleentwickler-Community suchst, schau doch mal im Discord und auf ZFX vorbei!

Anzahl der möglichen maximalen Wege bestimmen

  • 1
  • 2

Werbeanzeige

Evrey

Treue Seele

Beiträge: 245

Beruf: Weltherrscher

  • Private Nachricht senden

11

08.07.2013, 20:04

Zitat

Spontan würde ich einfach alle Möglichkeiten durchprobieren.
(Ist das Gleiche wie: )

Zitat

Du könntest einen Baum aufbauen in dem alle möglichen Felder von einem Feld aus jeweils neue Zweige bilden.
Nimm A* und modifiziere die Heuristik, dann erhältste ein Zwischending aus Baum und A*. Dein modifizierter Baum/A* bricht automatisch die Pfad-Suche/Blatt-Erzeugung ab, so bald die Tiefe die Zahl der begehbaren Felder übersteigt. Jetzt bleibt am Ende ganz schön was übrig. Vorzeitiges Erkennen bereits abgelaufener Knoten ist kostspielig, da du es nicht über Tags lösen kannst. Statt dessen könnte jeder Knoten eine Referenz auf seine Wurzel haben und rekursiv prüfen, ob das Feld bereits in diesem Pfad des Baumes zum Start hin liegt. Willst du Geschwindigkeit haben, prüfst du sowas am Ende der groben Suche, willst du Speicher schonen, prüfst du dies, bevor ein neues Blatt erzeugt wird. Du prüfst so alle Enden des Baumes, bis du die Wurzel erreichst. Doppelte Blätter sterben quasi ab. Übrig bleibt ein Baum, der alle Pfade enthält, die über jedes freie Feld zum Ziel führen. Du musst dich bloß noch entscheiden, ob du den Baum über die Tiefen- oder Breitensuche erzeugen willst. Ich würde hier wahrscheinlich einfach stumpf die Tiefensuche nehmen. Ist simpler zu implementieren. Wahrscheinlich aber weniger effizient.

C-/C++-Quelltext

 
1
2
3
4

int main(int _argc, char** _argv) noexcept {
  asm volatile("lock cmpxchg8b %eax");
  return 0;
} // ::main
(Dieses kleine Biest vermochte einst x86-Prozessoren lahm zu legen.)

=> Und er blogt unter Hackish.Codes D:

Mirac

Treue Seele

  • »Mirac« ist der Autor dieses Themas

Beiträge: 220

  • Private Nachricht senden

12

08.07.2013, 20:11

Die Effiziens ist mir so gesehen erstmal egal, es muss am Ende auch nichtmal wirklich funktionieren, da es nur als Abgabe gezählt werden muss :D
Aber irgentwo greift dann auch das eigene Ehrgefühl ;)
"Wer Angst hat, dass ihm seine Ideen geklaut werden, der scheint nicht viele zu haben. "

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

13

08.07.2013, 23:40

Du suchst einen Eulerweg. Noch viel Spass beim Googlen.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

Tobiking

1x Rätselkönig

Beiträge: 1 231

  • Private Nachricht senden

14

09.07.2013, 08:57

Zitat von »TGGC«

Du suchst einen Eulerweg. Noch viel Spass beim Googlen.

Euler? Alle Felder besuchen klingt für mich eher nach Hamilton.

TGGC

1x Rätselkönig

Beiträge: 1 799

Beruf: Software Entwickler

  • Private Nachricht senden

15

09.07.2013, 09:09

Kommt wohl darauf an, wie man die Aufgabe interpretiert. Hamiltonwege sind ja nicht maximal, z.b. TSP entspricht dem kuerzesten Hamiltonkreis.
Tetris Meeting Mainz | WMK Gamesroom | Schau dem neuen Tetris Großmeister zu

dennis-.-

Frischling

Beiträge: 87

  • Private Nachricht senden

16

09.07.2013, 12:37

Um den längsten Pfad in einem Graph zu finden kann man auch einfach alle Kantengewichte negieren.

Dein Algorithmus sollte dann aber bei negativen Kantengewichten keine Schleifen produzieren: http://de.wikipedia.org/wiki/Bellman-Ford-Algorithmus

David Scherfgen

Administrator

Beiträge: 10 382

Wohnort: Hildesheim

Beruf: Wissenschaftlicher Mitarbeiter

  • Private Nachricht senden

17

10.07.2013, 18:40

Zitat von »TGGC«

Kommt wohl darauf an, wie man die Aufgabe interpretiert.

Euler würde bedeuten, dass man jede Kante zwischen zwei benachbarten Feldern einmal ablaufen muss.
Dabei würde man zwangsläufig Knoten mehrfach besuchen, und das ist beim vorliegenden Problem nicht erlaubt.

Zitat von »TGGC«

Hamiltonwege sind ja nicht maximal, z.b. TSP entspricht dem kuerzesten Hamiltonkreis.

Die Minimalität bezieht sich dort auf die Kantengewichte entlang des gesuchten Pfades, nicht auf die Anzahl der besuchten Knoten (die ist fest).

Ich plädiere auch für "alles durchprobieren".

In einem Zustand merkt man sich, wo man gerade ist und welche Felder bereits besucht wurden (2D-Bitmap); evtl. zum Beschleunigen noch die verbleibende Anzahl noch zu besuchender Felder.
Der Startzustand ist klar: man befindet sich auf der Startposition und hat noch kein Feld besucht außer eben das Startfeld.
Den Startzustand legt man in eine Warteschlange.
Ein globaler Zähler zählt die Anzahl bisher gefundener maximaler Wege.
Aus der Warteschlange nimmt man sich nun immer den ersten Zustand heraus. Befindet man sich in diesem Zustand auf dem Zielfeld, so wird geprüft, ob auch alle anderen Felder besucht wurden. Wenn ja, ist das ein gültiger maximaler Weg, und man kann den globalen Zähler erhöhen.
Der Zustand wird aus der Warteschlange gelöscht, und es werden alle möglichen Nachfolgezustände erzeugt und wieder in die Warteschlange eingefügt (nur wenn die aktuelle Position nicht das Zielfeld ist, denn sonst kann hieraus kein gültiger maximaler Weg mehr entstehen, denn das Zielfeld muss als letztes erreicht werden).
Wenn die Warteschlange leer ist, hört man auf, und der Zähler sollte nun die korrekte Antwort enthalten.

Vielleicht kann man durch bidirektionale Suche (Vor- und Rückwärtssuche) noch einiges an Performance rausholen.
David Scherfgens Website | Konzentrationstest Polizei

Werbeanzeige

  • 1
  • 2

Ähnliche Themen