2002 | OriginalPaper | Buchkapitel
Solving the Kirkman’s Schoolgirl Problem in a Few Seconds
verfasst von : Nicolas Barnier, Pascal Brisset
Erschienen in: Principles and Practice of Constraint Programming - CP 2002
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
The Social Golfer Problem has been extensively used in recent years by the constraint community as an example of highly symmetric problem. It is an excellent problem for benchmarking symmetry breaking mechanisms such as SBDS or SBDD and for demonstrating the importance of the choice of the right model for one problem. We address in this paper a specific instance of the Golfer Problem well known as the Kirkman’s Schoolgirl Problem and list a collection of techniques and tricks to find efficiently all its unique solutions. In particular, we propose SBDD+, an generic improvement over SBDD which allows a deep pruning when a symmetry is detected during the search. Our implementation of the presented techniques allows us to improve previous published results by an order of magnitude for CPU time as well as number of backtracks, and to compute the seven unique solutions of the Kirkman’s problem in a few seconds.