|
recherche arborescente basée sur le chemin est une méthode de recherche d'informations au sein d'une structure de fichiers ou en ligne. Méthodes de recherche d' arbre de vérifier chaque nœud et le chemin d'une structure de répertoire pour le fichier ou le terme de recherche. La méthode de recherche de l'arbre base du chemin se fait en utilisant une méthode logique comme chemin alphabétique ou le plus court en premier. Méthodes de Recherche en arbre basées sur le chemin peuvent être combinées avec d'autres données méthodes de recherche . Largeur d'abord
largeur d'abord les recherches commencent la recherche dans le répertoire racine ou le répertoire de démarrage requis. L'algorithme identifie les prochains nœuds sur l'arbre et identifie les chemins les plus courts entre les nœuds. Si la solution n'est pas trouvée, la recherche en largeur scrute les branches de chacun de ces nœuds. Largeur - premières recherches ne sauvent pas le chemin arbre basée sur la recherche de résultats que la recherche est effectuée . Selon " Algorithmes Unplugged " de Berthold Vöcking , " largeur d'abord n'est pas applicable pour rechercher un labyrinthe. On ne peut simplement noter une jonction sur une liste et sauter sur la demande. "
Profondeur d'abord
profondeur d'abord recherches le chemin d'un arbre comme profond que ça se passe. Une fois l'extrémité d'une branche est atteinte, l'algorithme se déplace vers le nœud de l'enfant le plus proche et cherche ses enfants . " Algorithmes en bref », dit «le cœur de la profondeur d'abord est un ( u) opération dfs_visit récursif, ce qui rend visite à un sommet u qui, auparavant, n'a pas été visité . " Après tous les chemins d' une branche d'arbre sont recherchées , l' recherche algorithme revient à la partie supérieure de la structure de l'arbre et identifie un autre noeud pour effectuer la recherche.
GRASP heuristique
Greedy Randomized Adaptive Search Procedure (GRASP) heuristique méthode de recherche commence par une recherche au hasard pour la meilleure correspondance. L'heuristique construit une liste de candidats susceptibles de recherche . L'heuristique du GRASP sauve recherches partielles et de leur parcours dans l'arborescence . L'algorithme de recherche dans la liste des candidats de manière itérative . La méthode de recherche retrace le parcours de chaque branche des dossiers des candidats retenus pour trouver la meilleure réponse à la requête de recherche .
Integer Linear Programming
Integer Linear Programming ( ILP) fusionne arbres et basées sur un chemin méthodes de recherche . Selon " Le Compiler Design Handbook », « il permet (limité ) l'intégration des informations de chemin infaisable tout ( souvent ) être beaucoup moins cher que les approches basées sur le chemin . " Recherches booléennes peuvent être effectués dans les recherches ILP . Recherche de chemin d'arbre basée sur des candidats probables de la recherche booléenne peut être utilisé pour identifier les meilleurs candidats de recherche. Direction et recherches liées à ILP coupés résultats non optimales trop loin du résultat optimal. Direction et recherches coupées en ILP identifier les correspondances possibles et ajouter des critères de recherche supplémentaires pour couper les faibles résultats de la recherche .
|
