Approches structurelles et coopératives pour la résolution des problèmes de satisfaction de contraintes / Cyril Terrioux ; sous la direction de Philippe Jégou

Bibliogr. p. 127-133

Thèse de doctorat informatique 2002 université Aix-Marseille I

Cette thèse porte sur des méthodes de résolution du problème de satisfaction de contraintes (CSP) qui exploitent des informations explicitées durant la recherche. D'abord, nous définissons la méthode énumérative BTD qui produit et exploite des goods et nogoods structurels. Un good (resp. Nogood) structurel est une affectation consistante qui peut (resp. Ne peut pas) être étendue de façon consistante sur une partie bien définie du problème. BTD bénéficie de l'efficacité pratique de l'énumération tout en garantissant des bornes de complexité identiques à celles des meilleures méthodes structurelles. BTD est ensuite étendu au cadre des CSP valués. Ensuite, nous étudions l'apport de la coopération à une méthode concurrente, la coopération reposant sur l'échange de nogoods classiques (i. E. Des affections consistantes qui ne peuvent être étendues en une solution). Cette approche obtenant de bons résultats en pratique, nous l'étendons aux goods et nogoods structurels, puis aux CSP valués.