Une approche réactive du problème d'arbre couvrant maximal basé sur l'algorithme de Kruskal

Résumé : Dans un contexte de préférences non classiques (pouvant présenter des intransitivités et incomplétu­des, voire des circuits), les problèmes combinatoires de recherche d'une solution préférée sont semi-structurés. Leur résolution s'effectue généralement grâce à des interactions entre le Système Interactif d'Aide à la Décision (SIAD) et les décideurs selon un processus de décision. En proposant des algorithmes de résolution de problèmes connexes pertinents entièrement automatisables, le SIAD aide à obtenir des éléments de réponses aux questions que se pose un intervenant dans un processus de décision. Nous introduisons un tout nouveau type de SIAD, proposant des problèmes automatisables pertinents basés sur la déduction et le choix : les problèmes de consistance qualitative. Ainsi, nous présentons un algorithme glouton de consistance qualitative dans le cadre du problème d'arbre couvrant maximal basé sur une version ordinale de l'algorithme de Kruskal. Utilisés dans un processus itératif interactif, ce type de problèmes ne permet pas toujours d'aboutir à une solution maximale pour l'instance initiale. Le processus décisionnel est dit non pleinement rationnel. Pour y remédier, nous identifions algorithmiquement les arêtes critiques (présentes dans toute solution du sous-ensemble maximal courant). Enfin, nous fournissons des conditions nécessaires sur les préférences, en nous aidant des travaux en théorie du choix rationnel, pour que le processus conserve cette rationalité procédurale.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07
Liste complète des métadonnées

Littérature citée [34 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00151158
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 16:50:48
Dernière modification le : mercredi 18 juillet 2018 - 20:11:28

Fichier

31.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00151158, version 1

Collections

Citation

Rémy-Robert Joseph, Laurent Linguet. Une approche réactive du problème d'arbre couvrant maximal basé sur l'algorithme de Kruskal. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07. 〈inria-00151158〉

Partager

Métriques

Consultations de la notice

189

Téléchargements de fichiers

112