Algorithmus gesucht
-
numbo schrieb:
Wie schnell die Berechnung geht ist relativ egal.
Dann mach Backtracking. Gibt ja nur ca. N! Möglichkeiten zum testen. Bei N=100*100 und wenn du 10^12 Pfade pro Sekunde testest dauert es auch nur 2,8*10^35629 mal das aktuelle Alter des Universums und du bist auch schon fertig. Ich denke mit "relativ egal" meinst du irgendwas in der Größenordnung von maximal ein paar Tagen. Da ich noch keinen der Algorithmen getestet habe kann ich dir noch nicht sagen ob damit ein 100x100 Feld in absehbarer Zeit machbar ist. Da du ja keinen Algorithmus zu finden scheinst: Ich hatte hier doch schon einen verlinkt. Haste dir den mal angeschaut?
-
Haste dir den mal angeschaut?
Ja habe ich, werde daraus aber nicht schlau...
Gibts für das auch ein Codebeispiel?
Oder einen anderen Ansatz?Ich kann ja nicht der einzige sein , der sowas versucht...
-
Ja gibt es. Steht dort doch auch:
The algorithm is implemented in C++ and the program is demonstrated with several examples [Download].
-
Ich habe gerade mal selbst mit dem Algorithmus rumgespielt. So ganz überzeugt bin ich davon noch nicht. In meinen zufälligen generierten Maps findet er irgendwie nur Pfade wenn recht wenig gesperrte Felder vorhanden sind. Kann so natürlich stimmen aber ich würde es gerne mal mit realistischeren Maps testen. Kannst du mal einige der Maps hochladen wenn die nicht geheim sind?
-
das klingt aber alles sehr nach der ersten Aufgabe vom bundeswettbewerb-informatik
ist das überhaupt erlaubt? Immerhin soll man das Ganze nach Möglichkeit selbst lösen.
-
win8789 schrieb:
das klingt aber alles sehr nach der ersten Aufgabe vom bundeswettbewerb-informatik
ist das überhaupt erlaubt? Immerhin soll man das Ganze nach Möglichkeit selbst lösen.
Danke für den Hinweis. Ich werde also schonmal nicht meinen Code hier posten. Allerdings spricht der TO von 100x100 Feldern und die bwinf Beispiele sind alle sehr klein. Die müsste man auch schnell mit Backtracking lösen können.
-
Für den BWInf bin ich leider schon zu alt
Kannst du mir den Code Privat schicken, wenn du weiter kommst?
-
Ich würde den Code vorher ja gerne mal testen mit sinnvollen Maps. Ich habe gerade ein 10x10 Feld und wenn da zufällig ~3 Blocks drin verteilt werden findet der Algo schon keine Lösung mehr.
-
win8789 schrieb:
das klingt aber alles sehr nach der ersten Aufgabe vom bundeswettbewerb-informatik
ist das überhaupt erlaubt? Immerhin soll man das Ganze nach Möglichkeit selbst lösen.
Danke für die Tips, muß das aber erst verdauen.
Das hat mit Bundes-Informatik überhaupt nichts zu tun. Ich will einfach nur bestimmte Bereiche nach PZ absuchen, was gelingt, die dann in eine Map speichern, und nun diverse Zählungen für definierte Bereiche in der Map vornehmen.
Also Staatsgeheimnisse soll mir hier niemand verraten ....