1. Wie kann man einen Algorithmus zur Bestimmung der domination number für das Damenproblem implementieren?

    Der Algorithmus aus dem Artikel Entwicklung eines brute force Algorithmus für das Damenproblem prüft für alle Möglichkeiten k Damen auf ein n x n-Schachbrett zu stellen, ob alle Felder beherrscht werden. Ist man nur daran interessiert, wie viele Damen mindestens benötigt werden, ist dieser Algorithmus ungeeignet. Gibt es einen Algorithmus, der nur diese sogenannte domination number (oder zumindest eine gute Approximation) berechnet?
  2. Kann man den brute force Algorithmus zur Lösung des Damenproblems beschleunigen?

    Der Algorithmus aus dem Artikel Entwicklung eines brute force Algorithmus für das Damenproblem erfüllt zwar die an ihn gestellten Aufgaben, ist aber sehr langsam und für Schachbretter mit einer Seitenlänge von n > 10 unzumutbar. Kann man ihn deutlich schneller implementieren?
Durch die Nutzung dieser Website erklären Sie sich mit der Verwendung von Cookies einverstanden. Außerdem werden teilweise auch Cookies von Diensten Dritter gesetzt. Genauere Informationen finden Sie in unserer Datenschutzerklärung sowie im Impressum.