Cependant, entre les techniques de recherche informée et non informée, la recherche informée est plus efficace et plus rentable.
Tableau de comparaison
| Base de comparaison | Recherche éclairée | Recherche non informée |
|---|---|---|
| De base | Utilise ses connaissances pour trouver les étapes de la solution. | Aucune utilisation de la connaissance |
| Efficacité | Hautement efficace car consomme moins de temps et d’argent. | L'efficacité est médiatrice |
| Coût | Faible | Comparativement élevé |
| Performance | Trouve la solution plus rapidement | La vitesse est plus lente que la recherche éclairée |
| Algorithmes | Recherche en profondeur d'abord, recherche en largeur d'abord et première recherche au coût le plus bas | Recherche heuristique de profondeur d'abord et de largeur d'abord, et recherche A * |
Définition de la recherche informée
La technique de recherche informée utilise les connaissances spécifiques au problème afin de donner une idée de la solution du problème. Ce type de stratégie de recherche empêche en réalité les algorithmes de trébucher sur l'objectif et l'orientation de la solution. La recherche informée peut être avantageuse en termes de coût lorsque l'optimalité est obtenue à des coûts de recherche inférieurs.
Pour rechercher un coût de trajet optimal dans un graphique en mettant en œuvre une stratégie de recherche informée, les nœuds n les plus prometteurs sont insérés dans la fonction heuristique h (n). Ensuite, la fonction renvoie un nombre réel non négatif qui correspond au coût approximatif du chemin calculé du noeud n au noeud cible.
Ici, la partie la plus importante de la technique informée est la fonction heuristique qui facilite la transmission de la connaissance supplémentaire du problème à l’algorithme. En conséquence, cela aide à trouver le chemin vers l'objectif à travers les différents nœuds voisins. Il existe divers algorithmes basés sur la recherche informée, tels que la recherche heuristique en profondeur d'abord, la recherche heuristique en largeur d'abord, la recherche A *, etc. Comprenons maintenant la recherche heuristique en profondeur d'abord.
Profondeur heuristique première recherche
Semblable à la méthode de recherche en profondeur d'abord donnée ci-dessous, une recherche heuristique de profondeur en premier choisit un chemin mais parcourt tous les chemins du chemin sélectionné avant de choisir un autre chemin. Cependant, il choisit le meilleur chemin localement. Dans les cas où la plus petite valeur heuristique est la priorité de la frontière, on parle alors de meilleure recherche.
Un autre algorithme de recherche éclairé est la recherche A *, qui fusionne le concept de recherche au moindre coût et de recherche en premier. Cette méthode prend en compte le coût du chemin et les informations heuristiques dans le processus de recherche et de sélection du chemin à développer. Coût total estimé du chemin utilisé pour chaque chemin résidant à la frontière, du début au noeud cible. Par conséquent, il utilise deux fonctions simultanément: coût (p) est le coût du chemin d'accès découvert et h (p) est la valeur estimée du coût du chemin d'accès du nœud de départ au nœud de l'objectif.
Définition de la recherche non informée
La recherche non informée diffère de la recherche informée dans la mesure où elle fournit uniquement la définition du problème, mais ne constitue pas une étape supplémentaire pour trouver la solution au problème. L'objectif principal de la recherche non informée est de différencier les États cible et non cible, et ignore totalement la destination vers laquelle il se dirige dans la trajectoire jusqu'à ce qu'elle découvre l'objectif et signale son successeur. Cette stratégie est également appelée recherche à l'aveugle.
Il existe différents algorithmes de recherche dans cette catégorie, tels que la recherche en profondeur d'abord, la recherche de coût uniforme, la recherche en largeur d'abord, etc. Voyons maintenant le concept de la recherche non informée à l’aide de la recherche en profondeur.
Profondeur Première Recherche
Lors de la première recherche en profondeur, une pile Dernier entré premier sorti est utilisée pour ajouter et supprimer les nœuds. Un seul nœud est ajouté ou supprimé à la fois et le premier élément retiré de la frontière de la pile serait le dernier élément ajouté à la pile. En employant une pile dans les résultats de la frontière, la recherche de chemins s'est déroulée en profondeur de la première manière. Lorsqu'un chemin le plus court et optimal est recherché à l'aide de la recherche en profondeur d'abord, le chemin créé par les nœuds adjacents est terminé en premier, même s'il ne s'agit pas du chemin souhaité. Ensuite, le chemin alternatif est recherché via un retour en arrière.
En d’autres termes, l’algorithme choisit la première alternative à chaque nœud, puis revient à une autre alternative jusqu’à ce qu’il ait parcouru tous les chemins depuis la première sélection. Cela pose également un problème lorsque la recherche peut cesser de s’arrêter à cause des boucles infinies (cycles) présentes dans le graphique.
Principales différences entre la recherche informée et la recherche non informée
- L'ancienne technique de recherche informée utilise la connaissance pour trouver la solution. Par ailleurs, cette dernière technique de recherche non informée n’utilise pas les connaissances. Plus simplement, aucune information supplémentaire n’est fournie sur la solution.
- L'efficacité de la recherche informée est meilleure que la recherche non informée.
- Une recherche non informée prend plus de temps et d’argent car elle n’a aucune idée de la solution par rapport à une recherche informée.
- La recherche en profondeur d'abord, la recherche en largeur d'abord et la recherche en coût le plus bas sont les algorithmes qui entrent dans la catégorie de la recherche non informée. Par contre, la recherche informée couvre des algorithmes tels que la recherche heuristique en profondeur d'abord, la recherche heuristique en largeur d'abord et la recherche A *.
Conclusion
La recherche informée fournit la direction concernant la solution tandis que dans la recherche non informée, aucune suggestion n'est donnée concernant la solution. Cela rend la recherche non informée plus longue lorsque l'algorithme est implémenté.
