Meilleur premier algorithme de recherche dans le schéma

Question

D'accord c'est une question de devoirs, et je n'ai pas la moindre idée de comment je suppose pour commencer. De l'aide et des conseils seront grandement appréciés.

J'ai besoin d'utiliser une fonction heuristique pour résoudre un problème de type labyrinthe. Supposons que j'ai une grille de 5x5 et un robot en position (1,5) et mon but est de déplacer le robot vers (5,1). Sur le chemin il y a peu d'obstacles, disent (X,1,3), (X,2,3), (X,5,3), (X,4,2)

Imprimer l'itinéraire du robot est passé à travers.

Je pense à l'aide du greedy best first search algorithm pour trouver un chemin pour robot le but

Mon problème est, je suis nouveau système ont aucune idée de comment je devrais commencer à résoudre ce problème un peu.

Dois-je?

(define grid l w) --define the length and width of the grid ? 

(define robot) --define the initial position 

(define goal) --define the goal position 

(define blocks) --define the obstacle blocks 

and create a main function (define bestfirstslove) 

pour résoudre le problème?

Comment créer une grille? Comment dois-je aborder ce problème? Comment puis-je imprimer les étapes que le robot parcourt?

aide est très appréciée :)

Answer 1

Ok, donc la première chose que vous faites est discrétiser votre espace de recherche. En utilisant votre exemple d'une grille 5x5, cela signifie que vous avez un total de 25 points que votre robot peut occuper.

Ensuite, vous sélectionnez votre algorithme de recherche. Vous avez choisi Greedy Best First Search (GBFS), alors allons-y, mais dans une situation réelle, vous devriez le choisir en fonction des exigences de votre problème.

GBFS est un algorithme simple et nécessite les éléments suivants (et vous aurez besoin la plupart de ces modules pour tout algorithme pathfinding):

1. Une fonction à la liste de tous les voisins d'un nœud. E.g. Dans la grille que nous avons spécifiée ci-dessus, les voisins sont trivialement déterminés (+ 1, -1 permutations dans les deux directions avec une vérification des limites et, bien sûr, vérifiez s'il s'agit d'un obstacle).

2. Structure de données pour garder une trace des noeuds Open: Open noeuds sont des noeuds qui sont encore à examiner. Ainsi, dans l'exemple de code de Wikipedia, vous commencez avec la position initiale, trouvez ses successeurs (en utilisant la fonction ci-dessus) et en vous basant sur heuristique (vous pouvez utiliser la distance Euclidienne ou Manhattan entre le but et le successeur comme une heuristique) vous l'ajoutez à la "liste" Open - qui est mieux implémentée comme file d'attente prioritaire .

3. Votre fonction principale: Ce sera essentiellement commencer par la position initiale (1,5) et trouver ses voisins et les ajouter à la file d'attente de priorité en fonction de la distance euclidienne au but. Puis recurse (c'est-à-dire faire la même chose que ce que vous avez fait avec la position initiale) sur cette liste jusqu'à ce que vous trouviez votre objectif.

Alors, que vous devez noter à propos de Greedy meilleur premier est que vous ne pouvez pas avoir le chemin optimal, mais vous garantie la résiliation et un chemin (le cas échéant). Vous devriez penser à d'autres algorithmes comme A * ou Breadth First ou Depth First et voir ce qui fonctionne pour vos besoins.

Answer 2

probablement liée: C#: A-Star is born à CodeProject