1. Introduction
La recherche peut être complexe ou simple. Lorsqu'il n'est pas connu (ou seulement partiellement connu) à la fois l'objectif lui-même et la manière de l'atteindre, le hasard est important
Le but de l'article de recherche est de comparer les méthodes de recherche de la cible en mouvement (objet jaune) et immobile.
Ces méthodes:
- Recherche aléatoire (objet rouge)
- Recherche aléatoire avec mémoire (objet bleu)
- Recherche aléatoire avec mémoire et hiérarchie (objet vert)
- Recherche du premier itinéraire (objet violet)
- Recherche d'un itinéraire court (objet marron)
Sur la figure 1, ces objets sont représentés. Code de programme complet publié sur
github
2. La partie principale
2.1. Classe P - Recherche aléatoire
Le constructeur initialise les attributs et variables de classe: fenêtre principale, couleur, coordonnées y et x, compteur, dictionnaire visité, cible, dictionnaire de hiérarchie, dictionnaire de voisins. La méthode init_3_dict remplit trois dictionnaires. La méthode d'exposition peint la cellule dans la couleur souhaitée. La méthode de mise à jour met à jour l'objet. La méthode top_show crée une fenêtre de niveau supérieur et indique le nombre d'étapes effectuées vers la cible.
class P(): def __init__(self, root, color, node, target, maps, ban): self.root = root self.color = color self.y = node[0] self.x = node[1] P.target = target self.count = 0 self.visit = {} P.hierarchy = {} P.neighbor = {} self.init_3_dict(maps, ban)
La fonction is_en est déclarée dans la méthode init_3_dict, qui vérifie que la coordonnée n'est pas interdite et ne dépasse pas la carte.
def init_3_dict(self, maps, ban): def is_en(yx): if yx[0] < 0 or yx[0] > len(maps)-1: return if yx[1] < 0 or yx[1] > len(maps[0])-1: return if yx in ban: return return True
Dans un cycle, dans le dictionnaire visité avec la clé de coordonnées, écrivez la valeur initiale zéro. Dans le dictionnaire de hiérarchie avec la même clé, écrivez le nom hiérarchique de cette coordonnée. Ensuite, nous remplissons le dictionnaire des voisins en appelant la fonction is_en.
for y in range(len(maps)): for x in range(len(maps[0])): self.visit[(y,x)] = 0 P.hierarchy[(y,x)] = maps[y][x] n = [] if is_en((y-1,x)): n.append((y-1,x)) if is_en((y+1,x)): n.append((y+1,x)) if is_en((y,x-1)): n.append((y,x-1)) if is_en((y,x+1)): n.append((y,x+1)) P.neighbor[(y,x)] = n
La méthode show peint une cellule avec les coordonnées y, x dans la couleur souhaitée.
def show(self, y, x, color): lb = Label(text=" ", background = color) lb.configure(text=P.hierarchy[(y,x)] ) lb.grid(row=self.y, column=self.x, ipadx=10, ipady=5, padx=1, pady=1)
La méthode de déplacement déplace l'objet. Dans les variables y, x, nous écrivons les coordonnées du voisin, qui sont sélectionnées au hasard dans la liste des voisins. Ensuite, nous redessinons avec les nouvelles coordonnées.
Nous augmentons le compteur. Vérifiez si l'objectif est atteint. Si l'objectif est atteint, alors dans la variable de la classe J.disable nous écrivons correctement. Nous appelons la méthode top_show ().
def move(self): v = [] for i in P.neighbor[(self.y, self.x)]: v.append(i) y,x = random.choice(v) self.show(self.y, self.x, 'white') self.y = y self.x = x self.show(y, x, self.color) self.count +=1 if P.target == P.hierarchy[(self.y, self.x)]: J.disable = True self.top_show()
La méthode de mise à jour appelle move et met à jour toutes les demi-secondes.
def update(self): self.move() self.root.after(500, self.update)
La méthode top_show affiche les résultats.
def top_show(self): top = Toplevel() lbt = Label(top, text=self.color + " = " + str(self.count)) lbt.pack() top.mainloop()
2.2. Classe M - Recherche aléatoire dans la mémoire
Le constructeur appelle le constructeur de la classe parente et augmente la valeur de la cellule du champ où nous allons. La méthode de déplacement déplace l'objet. La méthode de choix renvoie les coordonnées sélectionnées par l'algorithme de recherche aléatoire avec mémoire.
Dans la méthode de déplacement, appelez la méthode de choix. Sinon, son travail est similaire à la méthode du parent.
def move(self): yx = self.choice((self.y, self.x))
La méthode de choix parcourt les coordonnées des voisins et ajoute des tuples à la liste v. Le premier élément du tuple sera la coordonnée du voisin, le second - combien de fois il a été visité. Ensuite, nous trions de petit à grand. Nous trions tous les tuples et dans la liste v nous ne laissons que ceux qui se sont produits autant de fois que ceux enregistrés dans le premier tuple. Sélectionnez au hasard l'un d'entre eux.
def choice(self, yx): v = [] for i in P.neighbor[yx]: v.append((i, self.visit[i])) v.sort(key = lambda x: x[1], reverse = False) v = [i for i in v if v[0][1] == i[1]] v = random.choice(v) self.visit[v[0]] += 1 return v[0]
2.3. Classe N - recherche aléatoire avec mémoire et hiérarchie.
La méthode de choix sélectionne les tuples qui correspondent le mieux au nom hiérarchique de la cible. Si cette correspondance est la même, les coordonnées les moins visitées sont sélectionnées.
Le constructeur appelle le constructeur du parent et initialise l'attribut de coïncidence le nombre de correspondances de caractères du nom hiérarchique avec la cible.
def __init__(self, root, color, node, target, maps, ban): super().__init__(root, color, node, target, maps, ban) self.coincidence = 0
La méthode de choix dans la boucle écrit le nom hiérarchique de la coordonnée actuelle du voisin. La variable r stocke le nombre de correspondances de cette variable avec la cible. Si le nombre de correspondances r est supérieur, la coïncidence est remplacée. Dans ce cas, le tuple (coordonnées, nombre de visites) de la liste v est écrit dans la liste d. Si r est égal à la coïncidence, alors dans d nous ajoutons un tuple de v.
def choice(self, yx): v = [] for i in P.neighbor[yx]: v.append((i, self.visit[i])) d = [] for l in v: c = P.hierarchy[l[0]] r = 0 for i in range(len(P.target)): if c[i] == P.target[i]: r +=1 else: break if r > self.coincidence: self.coincidence = r d = [l] if r == self.coincidence: d.append(l) if d: v = d v.sort(key = lambda x: x[1], reverse = False) v = [i for i in v if v[0][1] == i[1]] v = random.choice(v) self.visit[v[0]] += 1 return v[0]
2.4. Classe K - recherchez un itinéraire et recherchez l'itinéraire le plus court.
Le constructeur écrit les coordonnées de fin dans la variable de fin. Si le paramètre court est False, nous appelons la recherche d'itinéraire. Sinon, nous trouvons l'itinéraire le plus court.
La méthode find_path ajoute les coordonnées actuelles à l'itinéraire. Si l'objectif est atteint, retourne l'itinéraire. Nous trions tous les voisins. S'il n'y a pas de voisin dans le chemin, appelez-nous récursivement. Et le fait que la méthode retourne est écrit dans newpath. Le premier itinéraire trouvé sera newpath. La différence entre la méthode find_short_path est que si la longueur de newpath est supérieure ou égale à la longueur de shortest, alors shortest est écrasé.
def find_path(self, node, end, path=[]): path = path + [node] if node == end: return path for v in P.neighbor[node]: if v not in path: newpath = self.find_path(v, end, path) if newpath: return newpath
2.5. La classe J est une cible mobile.
Un objet de classe J se déplace comme la classe P. Si la variable de classe J.disable est vraie, alors l'objet s'arrête.
2.6. Fonction principale.
Créez la fenêtre principale. Dans la variable cible, écrivez le nom hiérarchique de la cible. La liste des interdictions contient les coordonnées des cellules interdites. Dans la liste des cartes, la carte elle-même. Dans la boucle, nous dessinons une carte. Créez des objets de classe. Ensuite, nous appelons la fonction de mise à jour, qui met à jour les objets.
3. Conclusions
Cinq expériences ont été réalisées à la fois pour une cible en mouvement et pour une cible immobile.
Le tableau 1 montre que le meilleur algorithme est l'itinéraire le plus court. Le deuxième plus efficace est une recherche aléatoire avec mémoire et hiérarchie. Le pire est la recherche aléatoire.
Tableau 1. Cible fixe
Dans le cas d'une cible mobile, les résultats sont différents. Les pires algorithmes sont ceux qui ont initialement calculé l'itinéraire vers l'objectif. Dans le tableau 2, un tiret indique que l'objectif n'a pas été atteint. Brown s'est avéré pire que Violet. Pire, car Violet a une trajectoire plus longue (la chance de rencontrer une cible en mouvement est plus grande). Le meilleur algorithme lors de la recherche d'une cible mobile est une recherche aléatoire avec mémoire et hiérarchie. En deuxième place, une recherche aléatoire avec mémoire.
Tableau 2. Cible mobile
Si l'on ne sait pas si la cible se déplace ou non, il est préférable d'utiliser l'algorithme de recherche aléatoire avec mémoire et hiérarchie ou simplement la recherche aléatoire avec mémoire.
4. Conclusion
L'aléatoire est important si la recherche d'une cible se produit face à l'incertitude. La recherche est réduite si les données sont présentées de manière hiérarchique. La mémoire, bien sûr, est également précieuse.