1. Einleitung
Die Suche kann entweder komplex oder einfach sein. Wenn das Ziel selbst und der Weg zu dessen Erreichung nicht oder nur teilweise bekannt sind, ist der Zufall wichtig
Das Ziel des Forschungsartikels ist es, die Methoden zu vergleichen, um das Ziel als beweglich (gelbes Objekt) und bewegungslos zu finden.
Diese Methoden:
- Zufallssuche (rotes Objekt)
- Zufallssuche mit Speicher (blaues Objekt)
- Zufallssuche mit Speicher und Hierarchie (grünes Objekt)
- Suche nach der ersten Route (lila Objekt)
- Suche nach einer kurzen Route (braunes Objekt)
In Fig. 1 sind diese Objekte dargestellt. Vollständiger Programmcode auf
Github
2. Der Hauptteil
2.1. Klasse P - Zufallssuche
Der Konstruktor initialisiert Klassenattribute und -variablen: Hauptfenster, Farbe, y- und x-Koordinate, Zähler, besuchtes Wörterbuch, Ziel, Hierarchiewörterbuch, Nachbarwörterbuch. Die Methode init_3_dict füllt drei Wörterbücher. Die Show-Methode malt die Zelle in der gewünschten Farbe. Die Aktualisierungsmethode aktualisiert das Objekt. Die top_show-Methode erstellt ein Fenster auf oberster Ebene und zeigt an, wie viele Schritte zum Ziel ausgeführt wurden.
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)
Die Funktion is_en wird in der Methode init_3_dict deklariert, die überprüft, ob die Koordinate nicht gesperrt ist oder über die Karte hinausgeht.
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
Schreiben Sie in einem Zyklus in das mit dem Koordinatenschlüssel besuchte Wörterbuch den Anfangswert Null. Schreiben Sie im Hierarchiewörterbuch mit demselben Schlüssel den hierarchischen Namen dieser Koordinate. Dann füllen wir das Wörterbuch der Nachbarn mit der Funktion 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
Die show-Methode malt eine Zelle mit y, x-Koordinaten in der gewünschten Farbe.
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)
Die move-Methode verschiebt das Objekt. In die Variablen y, x schreiben wir die Koordinate des Nachbarn, die zufällig aus der Liste der Nachbarn ausgewählt wird. Dann zeichnen wir mit den neuen Koordinaten neu.
Wir erhöhen den Zähler. Überprüfen Sie, ob das Ziel erreicht ist. Wenn das Ziel erreicht ist, schreiben wir in die Variable der Klasse J.disable richtig. Wir nennen die top_show () -Methode.
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()
Die Aktualisierungsmethode ruft move auf und aktualisiert alle halbe Sekunde.
def update(self): self.move() self.root.after(500, self.update)
Die top_show-Methode zeigt die Ergebnisse an.
def top_show(self): top = Toplevel() lbt = Label(top, text=self.color + " = " + str(self.count)) lbt.pack() top.mainloop()
2.2. Klasse M - Zufällige Speichersuche
Der Konstruktor ruft den Konstruktor der übergeordneten Klasse auf und erhöht den Wert der Zelle des Feldes, in das wir gehen. Die move-Methode verschiebt das Objekt. Die Auswahlmethode gibt die Koordinate zurück, die der Zufallssuchalgorithmus mit Speicher ausgewählt hat.
Rufen Sie in der Methode move die Methode choice auf. Ansonsten ähnelt seine Arbeit der Methode der Eltern.
def move(self): yx = self.choice((self.y, self.x))
Die Auswahlmethode durchläuft die Koordinaten der Nachbarn und fügt Tupel zur Liste hinzu. V. Das erste Element des Tupels ist die Koordinate des Nachbarn, das zweite - wie oft wurde es besucht. Dann sortieren wir von klein nach groß. Wir sortieren alle Tupel und lassen in der Liste v nur diejenigen übrig, die so oft vorkamen, wie im ersten Tupel aufgezeichnet. Wählen Sie eine davon zufällig aus.
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. Klasse N - Zufallssuche mit Speicher und Hierarchie.
Die Auswahlmethode wählt die Tupel aus, die dem hierarchischen Namen des Ziels am ehesten entsprechen. Wenn diese Übereinstimmung identisch ist, werden die Koordinaten ausgewählt, die am wenigsten besucht wurden.
Der Konstruktor ruft den Konstruktor des übergeordneten Elements auf und initialisiert das Übereinstimmungsattribut mit der Anzahl der Zeichenübereinstimmungen des hierarchischen Namens mit dem Ziel.
def __init__(self, root, color, node, target, maps, ban): super().__init__(root, color, node, target, maps, ban) self.coincidence = 0
Die Auswahlmethode in der Schleife schreibt den hierarchischen Namen der aktuellen Koordinate des Nachbarn. Die Variable r speichert die Anzahl der Übereinstimmungen dieser Variablen mit dem Ziel. Wenn die Anzahl der Übereinstimmungen r größer ist, wird die Übereinstimmung überschrieben. In diesem Fall wird das Tupel (Koordinaten, Anzahl der Besuche) aus der Liste v in die Liste d geschrieben. Wenn r gleich Zufall ist, dann fügen wir in d ein Tupel aus v hinzu.
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. Klasse K - Suche nach einer Route und suche nach der kürzesten Route.
Der Konstruktor schreibt Endkoordinaten in die Endvariable. Wenn der Kurzparameter False ist, nennen wir die Routensuche. Ansonsten finden wir den kürzesten Weg.
Die find_path-Methode fügt der Route die aktuelle Koordinate hinzu. Wenn das Ziel erreicht ist, wird die Route zurückgegeben. Wir sortieren alle Nachbarn. Wenn sich kein Nachbar im Pfad befindet, rufen Sie uns rekursiv an. Und die Tatsache, dass die Methode zurückgibt, wird in newpath geschrieben. Die erste gefundene Route ist newpath. Der Unterschied zwischen der find_short_path-Methode besteht darin, dass der kürzeste Pfad überschrieben wird, wenn die Länge des neuen Pfads größer oder gleich der Länge des kürzesten ist.
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. Klasse J ist ein sich bewegendes Ziel.
Ein Objekt der Klasse J bewegt sich wie Klasse P. Wenn die Variable der Klasse J.disable wahr ist, stoppt das Objekt.
2.6. Funktion Haupt.
Erstellen Sie das Hauptfenster. Schreiben Sie in die Zielvariable den hierarchischen Namen des Ziels. Die Sperrliste enthält die Koordinaten der verbotenen Zellen. In der Liste der Karten die Karte selbst. In der Schleife zeichnen wir eine Karte. Erstellen Sie Klassenobjekte. Dann rufen wir die Update-Funktion auf, die die Objekte aktualisiert.
3. Schlussfolgerungen
Es wurden fünf Experimente sowohl für ein sich bewegendes als auch für ein sich bewegendes Ziel durchgeführt.
Tabelle 1 zeigt, dass der beste Algorithmus der kürzeste Weg ist. Die zweiteffektivste ist eine Zufallssuche mit Speicher und Hierarchie. Das Schlimmste ist die Zufallssuche.
Tabelle 1. Festes Ziel
Bei einem sich bewegenden Ziel sind die Ergebnisse unterschiedlich. Die schlechtesten Algorithmen waren diejenigen, die anfänglich die Route zum Ziel berechneten. In Tabelle 2 zeigt ein Bindestrich an, dass das Ziel nicht erreicht wurde. Brown erwies sich als schlimmer als Violet. Schlimmer noch, weil Violet eine längere Flugbahn hat (die Chance, ein sich bewegendes Ziel zu treffen, ist größer). Der beste Algorithmus bei der Suche nach einem sich bewegenden Ziel ist eine zufällige Suche mit Speicher und Hierarchie. An zweiter Stelle steht eine zufällige Suche mit Speicher.
Tabelle 2. Bewegliches Ziel
Wenn nicht bekannt ist, ob sich das Ziel bewegt oder nicht, ist es besser, den Zufallssuchalgorithmus mit Speicher und Hierarchie oder nur die Zufallssuche mit Speicher zu verwenden.
4. Fazit
Zufälligkeit ist wichtig, wenn die Suche nach einem Ziel trotz Unsicherheit erfolgt. Die Suche wird reduziert, wenn die Daten hierarchisch dargestellt werden. Das Gedächtnis ist natürlich auch wertvoll.