La séquence globale minimale

Résumé : Le problème de la Séquence Globale Minimale, connue dans la littérature sous le nom de "Plus Courte Super-séquence Commune", est un problème NP-complet. On le rencontre dans plusieurs domaines tels que la linguistique computationnelle et la lexicographie. Nous le retrouvons ici dans un problème où il s'agit de construire une séquence minimale de machines telle qu'une série de pièces qui doivent passer sur certaines de ces machines dans un certain ordre n'ait à parcourir la séquence que dans un seul sens. Bien entendu, cette séquence peut contenir plusieurs fois la même machine, et une pièce qui parcourt la séquence peut éviter certaines machines. Nous présentons dans ce papier une heuristique rapide permettant de trouver cette séquence. Nous développons aussi une méthode exacte nous permettant d'évaluer notre heuristique.
Type de document :
Rapport
[Rapport de recherche] RR-1328, INRIA. 1990, pp.29
Liste complète des métadonnées

https://hal.inria.fr/inria-00075232
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 17:47:08
Dernière modification le : samedi 17 septembre 2016 - 01:06:51
Document(s) archivé(s) le : mardi 12 avril 2011 - 21:58:08

Fichiers

Identifiants

  • HAL Id : inria-00075232, version 1

Collections

Citation

Abdelghani Souilah. La séquence globale minimale. [Rapport de recherche] RR-1328, INRIA. 1990, pp.29. 〈inria-00075232〉

Partager

Métriques

Consultations de la notice

158

Téléchargements de fichiers

67