2002 | OriginalPaper | Buchkapitel
Determining the Number of Solutions to Binary CSP Instances
verfasst von : Ola Angelsmark, Peter Jonsson, Svante Linusson, Johan Thapper
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
Counting the number of solutions to CSP instances has applications in several areas, ranging from statistical physics to artificial intelligence. We give an algorithm for counting the number of solutions to binary CSPs, which works by transforming the problem into a number of 2-sat instances, where the total number of solutions to these instances is the same as those of the original problem. The algorithm consists of two main cases, depending on whether the domain size d is even, in which case the algorithm runs in time, or odd, in which case it runs in if d = 4 · k + 1, and if d = 4 · k + 3. We also give an algorithm for counting the number of possible 3-colourings of a given graph, which runs in , an improvement over our general algorithm gained by using problem specific knowledge.