Optimisation des réseaux de contraintes qualitatives temporelles
Loading...
Date
2017
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
UMMTO
Abstract
Dans ce travail, nous montrons que MinCons est NP-complet pour PA malgré le fait que le problème de cohérence est polynomial pour ce calcul. Moins surprenant, MinCons est également Np-complet pour IA dans le cas général, mais est également NP-complet pour certaines sous-classes pour lesquelles le problème de cohérence est connu pour être résoluble. Dans cet esprit, nous nous concentrons sur les sous-classes des relations convexes de PA et IA et montrons que pour ces cas particuliers, MinCons est polynomial. Nous définissons, pour les RCQT convexes, une méthode polynomiale pour extraire des scénarios compacts correspondant à des éléments minimaux d'ordres partiels particuliers.
Description
48 f.; ill. : 30 cm + (CD-Rom)
Keywords
RCQT : réseau de contraintes qualitatives temporelles, IA : algèbre des points, PA : algèbre des intervalles, MinCons : cohérence minimale