Diese Seite ist unverschlüsselt! Um sicherzustellen, das Ihr Passwort nicht ausgelesen werden kann, sollten Sie auf die verschlüsselte Seite wechseln!

    Herzlich Willkommen, lieber Gast!
  Sie befinden sich hier:

  Forum » C / C++ (ANSI-Standard) » n-Damenproblem (Aufgabe)
Forum | Hilfe | Team | Links | Impressum | > Suche < | Mitglieder | Registrieren | Einloggen
  Quicklinks: MSDN-Online || STL || clib Reference Grundlagen || Literatur || E-Books || Zubehör || > F.A.Q. < || Downloads   

Autor Thread - Seiten: [ 1 ] [ 2 ] > 3 <
020
09.01.2009, 10:31 Uhr
virtual
Sexiest Bit alive
(Operator)


Ich denke, es ist ein klassisches Problem, bei dem man wissen muß, ob man speicher- oder zeitoptimal implementieren möchte.

Sicherlich ist es so, daß eine Lösung, die in einer Collection die Positionen der Figuren hält, weniger Speicher verwendet, als eine die in einem Array alle Felder hält.

Schwieriger zu beantworten ist aber die Frage, wie sich das laufzeittechnisch auswirkt: So ist in der Lösung die ich damals geschrieben habe es sehr schnell feststellbar, ob eine Dame auf ein bestimmtes Feld gesetzt werden darf oder nicht.

Ist jetzt nicht bis ins Detail analysiert, aber ich behaupte einfach mal, daß die Array-Lösung zwar O(N*N) mehr Platz als die Lösung mit den Positionslisten benötigt, allerdings die Laufzeit um den Faktor O(N) schneller ist. (Unter der Annahme, daß wirklich alle Lösungen gefunden werden sollen)
--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
021
09.01.2009, 11:30 Uhr
0xdeadbeef
Gott
(Operator)


Das sehe ich nicht - das Streichen der Felder skaliert ja linear mit der Brettgröße, das Überprüfen der Damen mit den bereits gesetzten Damen. Es ist nicht ganz einfach abzuschätzen, wie sich letzteres zur Brettgröße genau verhält, weil sich der Aufenthaltsbereich des Algorithmus über die Rekursionstiefe tendenziell als Glockenkurve darstellt, mehr als linear ist es aber mit Sicherheit auch nicht - mehr als *Brettgröße* Damen sind nie gesetzt. Und das Durchlaufen der freien Felder skaliert in beiden Fällen gleich - einen konzeptionellen Geschwindigkeitsvorteil einer Array-Lösung kann ich nicht erkennen.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
022
09.01.2009, 16:13 Uhr
~kronosistnichtangemeldet
Gast



Zitat von 0xdeadbeef:
Das sehe ich nicht - das Streichen der Felder skaliert ja linear mit der Brettgröße, das Überprüfen der Damen mit den bereits gesetzten Damen. Es ist nicht ganz einfach abzuschätzen, wie sich letzteres zur Brettgröße genau verhält, weil sich der Aufenthaltsbereich des Algorithmus über die Rekursionstiefe tendenziell als Glockenkurve darstellt, mehr als linear ist es aber mit Sicherheit auch nicht - mehr als *Brettgröße* Damen sind nie gesetzt. Und das Durchlaufen der freien Felder skaliert in beiden Fällen gleich - einen konzeptionellen Geschwindigkeitsvorteil einer Array-Lösung kann ich nicht erkennen.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
023
09.01.2009, 16:15 Uhr
~kronosistnichtangemeldet
Gast


Waah, ich poste nie wieder bei der Arbeit
Was ich schreiben wollte: das hängt doch davon ab wie oft probiert wird zu setzen im Verhältnis dazu wie oft tatsächlich gesetzt wird. Würde sagen der Array hat schon 'nen Vorteil wenn mann alle Lösungen sucht.
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
024
09.01.2009, 19:09 Uhr
0xdeadbeef
Gott
(Operator)


Das Skalierungsverhalten ist wohl, alles in allem, das gleiche, das heißt, welcher Ansatz das schnellere Ergebnis liefert, hängt nicht unwesentlich von Implementationsdetails ab - prinzipiell sind sie ebenbürtig, zumindest im Laufzeitverhalten. Und was den Speicherverbrauch angeht, da ist das Speichern der Lösungen weitaus problematischer als das Aufspannen des Brettes.
--
Einfachheit ist Voraussetzung für Zuverlässigkeit.
-- Edsger Wybe Dijkstra
 
Profil || Private Message || Suche Download || Zitatantwort || Editieren || Löschen || IP
Seiten: [ 1 ] [ 2 ] > 3 <     [ C / C++ (ANSI-Standard) ]  


ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: