Problème de recherche
En informatique théorique, et plus particulièrement en théorie de la complexité et en théorie de la calculabilité, un problème de recherche est un problème algorithmique associé à une relation binaire. Si R est une relation binaire telle que pour tout (R) ⊆ Γ et T une machine de Turing, alors T implante R si:
- Si x est tel qu'il existe un y vérifiant R(x, y) alors T accepte l'entrée x en produisant un résultat z tel que R(x, z) (s'il y a plusieurs y, T n'est astreint à n'en trouver qu'un seul)
- Si x est tel qu'il n'existe aucune y tel que R(x, y) alors T rejette l'entrée x
De manière intuitive, un problème de recherche consiste à trouver, s'il existe, un objet "y" associé à un objet "x". On considère qu'un algorithme résout le problème si pour tout x, pour lequel un résultat existe, une occurrence est produite en résultat.
De tels problèmes se rencontrent fréquemment en théorie des graphes, en cherchant par exemple certains couplage, cliques, ensemble indépendant, etc.
Le graphe d'une fonction est une relation binaire.
Toute relation R peut être vue comme un problème de recherche et on dit qu'une machine de Turing qui implante R résout le problème de recherche. Tout problème de décision est la restriction d'un problème de recherche qui consiste à assimiler "oui" à "un résultat existe" et "non" à "aucun résultat n'existe":
La définition d'un problème de recherche peut être généralisée à des relations n-aires en utilisant un encodage adéquat.
Définition
modifierUn problème de recherche est défini par [1],[2],[3]:
- un ensemble d'états,
- un état de départ,
- un état-cible ou état-test,
- une fonction booléenne qui permet de savoir un état donné est l'état-cible,
- une fonction successeur,
- une application d'un état vers l'ensemble des états possibles
Objectif
modifierTrouver une solution lorsqu’un algorithme n'est pas fourni, mais lorsqu'on a que la spécification de la solution[4].
Méthode de recherche
modifier- algorithme de recherche générique: soit un graphe, un ensemble de nœuds de départ, et de nœuds d'arrivée, on explore de manière incrémentale les chemins du graphe depuis les nœuds de départ.
- Maintenir une liste de chemin "frontière" depuis les nœuds de départ qui ont déjà été explorés.
- Au fur et à mesure, la frontière s’étend aux nœuds non explorés jusqu'à ce qu'un état cible soit trouvé.
- La façon dont la frontière s'étend dépend du choix de la stratégie de recherche[4].
Entrée: un graphe,
un ensemble d'états de départ,
Une fonction booléenne goal(n) qui renvoie si n est un état cible.
frontière := {s : s est un nœud de départ};
Tant que frontière n'est pas vide:
sélectionner et retirer le chemin <n0, ..., nk> de la frontière;
Si goal(nk)
renvoyer <n0, ..., nk>;
Pour tous les voisins n de nk
rajouter <n0, ..., nk, n> à la frontière;
Fin Tant que
Notes et références
modifier- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Search problem » (voir la liste des auteurs).
- Kevin Leyton-Brown, « Graph Search »
- State-Space Search: Algorithms, Complexity, Extensions, and Applications, Weixiong Zhang
- Theoretical Aspects of Local Search, Wil Michiels, Emile Aarts,Jan Korst
- Kevin Leyton-Brown, « Graph Search », ubc (consulté le )
