2009 | OriginalPaper | Chapter
Komplexität der Geographie
Authors : Volker Diekert, Ulrich Hertrampf
Published in: Informatik als Dialog zwischen Theorie und Anwendung
Publisher: Vieweg+Teubner
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Das allgemein als Prototyp eines PSPACE-vollständigen Spiels gesehene Geographiespiel wird bezüglich seiner Komplexität genauer untersucht. Das Interesse der theoretischen Informatik an diesem Spiel wurde sehr durch die Darstellung in dem Lehrbuch von Papadimitriou [Pap94] gefördert. Allerdings bestimmt dieses Lehrbuch nicht die Komplexität des Standardspiels sondern verwendet eine Verallgemeinerung. Die Aussage in dem Lehrbuch bleibt damit etwas unbefriedigend und hinter den Möglichkeiten. Wir zeigen hier, dass die komplexitätstheoretische Charakterisierung schon für die Standardvariante des Spiels gilt.
In der konkreten Version, die man tatsächlich als Gesellschaftsspiel verwenden kann, gibt es unserem Alphabet entsprechend nur 26 Buchstaben. Es ergibt sich, dass man bei konstanter Buchstabenzahl optimale Spielstrategien in polynomieller Zeit berechnen kann.
In der Praxis muss man allerdings wiederum anders vorgehen, um verwertbare Ergebnisse zu erhalten. Wir beschreiben das anhand eines Spiels mit den 305 Millionenstädten dieser Welt.