A Probabilistic-Based Model for Binary CSP

Autor:	Balafrej, Amine, Lorca, Xavier, Truchet, Charlotte
Rok vydání:	2016
Předmět:	Computer Science - Artificial Intelligence Computer Science - Discrete Mathematics Computer Science - Data Structures and Algorithms G.2.1 G.2.2
Druh dokumentu:	Working Paper
Popis:	This work introduces a probabilistic-based model for binary CSP that provides a fine grained analysis of its internal structure. Assuming that a domain modification could occur in the CSP, it shows how to express, in a predictive way, the probability that a domain value becomes inconsistent, then it express the expectation of the number of arc-inconsistent values in each domain of the constraint network. Thus, it express the expectation of the number of arc-inconsistent values for the whole constraint network. Next, it provides bounds for each of these three probabilistic indicators. Finally, a polytime algorithm, which propagates the probabilistic information, is presented. Comment: 10 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1606.03894 Zobrazit plný text záznamu View this record from Arxiv