Skip to Main content Skip to Navigation
Conference papers

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.
Document type :
Conference papers
Complete list of metadata

Cited literature [34 references]  Display  Hide  Download

https://hal.inria.fr/inria-00151158
Contributor : Sylvain Soliman <>
Submitted on : Friday, June 1, 2007 - 4:50:48 PM
Last modification on : Friday, July 10, 2020 - 2:22:01 PM

File

31.pdf
Files produced by the author(s)

Identifiers

  • 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 Programmation par Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, France. ⟨inria-00151158⟩

Share

Metrics

Record views

273

Files downloads

158