Théorie de Computation, Problème de Grammaire, Shortest-Path

Bonjour,

La question est veille, mais sait-on jamais, peut-être que les quelques lignes qui suivent aideront à vulgariser ce texte que personnellement je trouve difficile à lire pour les non-spécialistes.

Rappels sur les grammaires

Une grammaire est composé d'un ensemble de règles (appelées production) qui permet, intuitivement, de définir récursivement un langage (au sens de la théorie des langages). Dans la définition de cette grammaire, on peut distinguer deux types de symboles : les terminaux et les non terminaux.

• Les terminaux sont des caractères de l'alphabet sur lequel est construit la grammaire (par exemple {0 ... 9, -, *, +, /, (, )} pour les opérations arithmétiques).
• Les non-terminaux sont des noms permettant de faire référence à une autre production (par exemple <Digit> ou <Expr> dans l'exemple qui suit).

Exemple : la section 4.1 de cet article montre comment peut se décliner cette grammaire en utilisant les opérateurs usuels des expression rationnelles :

1. <Digit> -> 0 | 1 | 2 | ... | 9
2. <Number> -> <Digit> | <Number> <Digit>
3. <Expression> -> <Number>
4. <Expression> -> (<Expression>)
5. <Expression> -> <Expression> + <Expression>
6. <Expression> -> <Expression> - <Expression>
7. <Expression> -> <Expression> * <Expression>
8. <Expression> -> <Expression> / <Expression>

Rôles de ces règles:

1. Définit un chiffre comme étant soit un 0, soit un 1, ... soit un 9.
2. Définit un nombre comme étant un chiffre, ou un nombre suivi d'un chiffre. Donc récursivement, un nombre est une suite de 1 ou plusieurs chiffres.
3. Définit comme un expression étant possiblement juste un nombre
4. Indique qu'une expression peut être entourée de parenthèses
5. Définit l'addition comme étant une expression, suivie d'un +, suivie d'une (autre) expression
6. Définit la soustraction
7. Définit la multiplication
8. Définit la division

Explication intuitive du papier

L'extrait d'article partagé dans le message #initial provient de ce papier. C'est malheureusement le genre d'article où les notations de départ servent à formaliser le le problème sous sa forme la plus générale, et souvent ces notations sont très abstraites et donc dur à lire. Dans ce genre de situation, il faut presque lire le papier à l'envers.

Je vais essayer de faire sentir l'idée du paragraphe que tu as partagé en partant d'un exemple très simple et en le ramenant progressivement au formalisme du papier.

Considérons un graphe orienté G(V, E) très simple dont les sommets sont {1, 2, 3} et les arcs sont (1 -> 2) (2 -> 3) (3 -> 1) et (3 -> 3). Alors si on part du sommet 1, on peut générer une infinité de chemins, parmi lesquels [1], [1, 2], [1, 2, 3], [1, 2, 3, 3, 3], [1, 2, 3, 1, 2, 3]. On voit donc que la structure du graphe contraint les suites de nombres obtenus en enregistrant les identifiants de sommets traversés. On peut avoir bien entendu le même raisonnement sur les arcs.

Que l'on raisonne sur les arcs ou les sommets, on peut donc imaginer construire une grammaire qui produit les chemins induit par G. Le papier pour sa part raisonne sur les sommets comme on le verra plus tard, donc afin d'être cohérent avec le papier, je considère dans ce qui suit qu'un papier est une suite de sommets.

Les productions de la grammaire qui généralise G découle arcs de G. Intuitivement, chaque arc (u -> v) induit une production : un chemin vide ou qui se termine par u, suivi d'un chemin vide ou qui commence par v.

Note qu'on peut facilement compléter ces productions pour contraindre les sommets d'où partent et où arrivent les chemins et ainsi voir G comme un automate (non déterministe) dont toutes les transitions sont étiquetées par le mot vide, même manière de voir les choses n'est pas couverte par le papier.

Si je reviens au papier, les productions de la grammaire induite par G sont notées Y. Le langage induit par cette grammaire noté L_G(Y) est l'ensemble des chemins que l'on peut construire dans G. En effet, l'équation L_G(Y) = {alpha | alpha in T* and Y -> alpha*} signifie que :

• chaque chemin alpha est une suite arbitraire de sommets, ce qui se note T*
• de plus, chaque chemin est contraint par Y (donc par les productions de la grammaire, et donc par les arcs de G)

Ensuite, toute la question est de traduire les chemins dans une représentation qui permet de les comparer entre eux. Cette représentation est spécifiée par la fonction val. Le plus souvent, le poids d'un chemin est obtenu en sommet le poids de ses arcs. Comme l'addition est associative, une manière équivalente de le dire est que le poids d'un chemin de longueur n est le poids de chemin x constitué de ses n-1 premiers arcs auquel on ajoute le poids du dernier arc (u -> v), ce qui correspond dans le papier à l'opération g_(u->v)(x) = x + length(u->v).

Résumé des notations

Si on bascule sur les notations génériques :

• X désigne un chemin
• x désigne le poids de ce chemin
• un chemin X se décompose en sous-chemins X_1 ... X_k
• chaque sous-chemin X_i est de poids x_i
• les poids de ces sous chemins sont combinés avec la fonction g (dans le cas qui nous intéresse, g est l'addition)
• le poids d'un chemin alpha est noté par la suite val(alpha)
• le but du problème est de trouver alpha tel que val(alpha) est minimal

Tu l'auras compris, si tu choisis une autre opération de concaténation g, ou une autre fonction de pondération val, tu couvres une classe très générale de problème.

Épilogue : les semi anneaux

Une manière plus générale de formaliser le problème (dans le cas où les poids sont "positifs" avec bonne définition de positifs) est la structure de semi anneaux. En effet, les semi-anneaux rassemblent alors suffisamment de propriétés algébriques pour qu'on puisse montrer que l'algorithme de Dijkstra généralisé (voir Gondran et Minoux, graphe et algorithme) pour chercher l'arbre de plus courts chemin dans un graphe.

• Le semi anneau utilisé pour un Dijkstra classique est (R+, min, +), ce qui signifie les sommets sont des réels positifs, qu'on cherche les chemins de poids minimaux, et qu'un chemin est obtenu en sommant les poids de ses sous chemins.
• (R+, min, max) est le semi anneau qui permet de chercher le chemin de bande passante maximale
• ([0, 1], max, *) est le semi anneau qui permet de chercher le chemin le plus sur
• Sous sa forme générale, un semi anneau est généralement noté  (E, \oplus, \otimes), où E est l'espace des poids, \oplus l'opération de comparaison, et \otimes l'opération de concaténation

Si on revient à ton article, g correspond à \otimes, et (E, \oplus) correpond à (R+, min).

Bonne chance

Salut , LgY =  ici est la configuration général de son contenu , et après il fait définir sa mesure qui obtient des contenance de qualité de mesure .  Je pense que c'est une mesure simple est toute première dans les contexte mathématique !!!