Géographie généralisée
En théorie de la complexité, géographie généralisé est un problème PSPACE-complet classique. Il est plus connu sous son nom anglais Generalized Geography et est abrégé GG.
Introduction
modifierÀ l'origine, Géographie est un jeu particulièrement adapté aux longs trajets en voiture dans lequel deux joueurs énoncent à tour de rôle différents noms de villes. Chaque nom de ville donné doit commencer par la dernière lettre du précédant (à l'exception du premier qui est librement choisi) et il est interdit de donner un nom de ville qui a déjà été employé. Le premier joueur qui ne peut pas donner de nom de ville respectant les contraintes perd la partie et le jeu prend alors fin.
Modélisation par graphe
modifierLe jeu peut être représenté par un graphe orienté dont les nœuds représentent les noms de ville du monde. Une flèche lie le nœud N1 au nœud N2 si et seulement si le nom de ville représenté par le nœud N2 commence par la dernière lettre de celui représenté par le nœud N1. Autrement dit, une flèche représente le fait qu'il est possible de passer d'une ville à une autre en accord avec les règles du jeu. Une partie correspond alors à une marche sur le graphe où les joueurs choisissent chacun leur tour un nœud voisin du nœud actuel qui n'a pas été visité. Le premier joueur qui en est incapable perd la partie. Un exemple illustré avec des noms de villes de l'État du Michigan (États-Unis) est présenté ci-dessous.
- Dans le problème Géographie généralisée on considère simplement un graphe orienté dont l'un des sommets est spécifié être le sommet de départ (on ne choisit plus la première ville librement). Le graphe suivant illustre un exemple d'instance du problème GG.
Jouer une partie
modifierOn définit P1 le joueur qui joue en premier et P2 le deuxième. On définit de plus N1, … , Nn les nœuds du graphe avec N1 le point d'entrée. Une partie jouée correspond à un chemin maximal ne passant jamais deux fois par le même sommet en commençant au nœud N1.
Complexité calculatoire
modifierLe problème GG qui consiste étant donné un graphe G et un sommet N1 à trouver quel joueur (P1 ou P2) a une stratégie gagnante est PSPACE-complet.
Géographie Généralisé est PSPACE-complet
modifierGG est PSPACE-complet. Cela signifie qu'il est à la fois PSPACE et PSPACE dur. On prouve ces deux affirmations séparément.
Géographie Généralisé est dans PSPACE.
Géographie généralisé est PSPACE-dur.
Planar GG
modifierLe problème GG restreint aux graphes planaires (Planar GG) est toujours PSPACE-complet. La preuve suivant est issue du théorème 3 de [2].
Graphes planaires bipartis d'arité maximale 3
modifierLe problème restreint aux graphes planaires bipartis d'arité maximale 3 est toujours PSPACE-dur. On le prouve en remplaçant les sommets d'arité strictement supérieure à trois par des chaines de sommets[1].
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a3/Generalized_geography_3-planar_transformation.svg/666px-Generalized_geography_3-planar_transformation.svg.png)
Edge Geography
modifierIl existe une variante de GG nommée Edge Geography (traduisible par « Géographie arête ») où, après chaque coup, on efface l’arête qui vient d'être employée mais où on peut passer plusieurs fois par le même nœud. Cela contraste avec GG, qui peut être vu comme effaçant les sommets empruntés à chaque étape. On peut donc considérer que GG est « Géographie sommet » (Vertex Geography).
Edge Geography est également PSPACE-complet. Cela se prouve en réduisant des formules booléennes quantifiées à des instances de Edge Geography [2].
Graphe non orienté
modifierOn peut envisager une variante de GG basée sur des graphes non orientés. Fraenkel, Scheinerman, et Ullman[3] ont montré qu'Edge Geography non orienté est dans P tandis que GG non orienté est PSPACE-complet, même en se restreignant aux graphes plan d'arité maximale 3. Si on se restreint aux graphes bipartis, le problème peut être résolu en temps polynomial.
Notes et références
modifier- David Lichtenstein et Michael Sipser, « Go Is Polynomial-Space Hard », Journal of the ACM, vol. 27, no 2, , p. 393–401 (DOI 10.1145/322186.322201, lire en ligne)
- Thomas J. Schaefer, « On the complexity of some two-person perfect-information games », Journal of Computer and System Sciences, vol. 16, no 2, , p. 185–225 (DOI 10.1016/0022-0000(78)90045-4)
- Aviezri Fraenkel, Edward Scheinerman et Daniel Ullman, « Undirected edge geography », Theoretical Computer Science, vol. 112, no 2, , p. 371–381 (DOI 10.1016/0304-3975(93)90026-p)
Bibliographie
modifier- Michael Sipser, Introduction to the Theory of Computation, PWS, 1997.
- David Liechtenstein and Michael Sipser, GO is polynomial Space Hard, Journal of the Association for Computing Machinery, avril 1980. [1] [2]