0

Je voudrais mieux comprendre comment les différents algorithmes de recherche communs sont liés les uns aux autres. Est-ce que quelqu'un sait d'une ressource, telle qu'un diagramme de hiérarchie ou une description textuelle concise de ceci?Hiérarchie hiérarchique des algorithmes de recherche?

Un petit exemple de ce que je veux dire est:

A* Search 
    -> Uniform-cost is a variant of A* where the heuristic is a constant function 
     -> Dijkstra's is a variant of uniform-cost search with no goal 
    -> Breadth-first search is a variant of A* where all step costs are +ve and identical 

etc.

Merci!

Répondre

1

Il n'y a pas de hiérarchie en tant que tel, juste un tas de différents algorithmes avec des traits différents.

par ex. A * peut être considéré comme basé sur Dijkstra, avec une heuristique ajoutée. Ou on peut considérer qu'il est basé sur une meilleure recherche basée sur l'heuristique, avec un facteur additionnel du coût du chemin jusqu'à présent.

De même, A * est implémenté à peu près de la même manière qu'une recherche en largeur d'abord (c'est-à-dire avec une file de nœuds). L'approfondissement itératif A * (IDA *) est basé sur A * dans la mesure où il utilise les mêmes mesures de coût et d'heuristique, mais est en réalité implémenté comme une méthode de recherche en profondeur en profondeur.

Il existe également un grand croisement avec des algorithmes d'optimisation. Certaines personnes considèrent les algorithmes génétiques comme un ensemble de tentatives d'escalade complexes, mais d'autres considèrent cela comme une forme de recherche par faisceau. Il est commun pour les algorithmes de recherche et d'optimisation de dessiner des propriétés à partir de plusieurs sources, de mélanger et d'assortir les approches pour les rendre plus pertinentes au domaine de recherche ou aux exigences de calcul, donc plutôt qu'une hiérarchie de méthodes. trouver une sélection de thèmes qui surgissent à travers différentes approches.