Dieser Algorithmus verwendet die Summe von g als Entfernung zur aktuellen Zeit und den geschätzten Wert h zum Ziel als Parameter während der Suche und berechnet die kürzeste Entfernung der Route bei relativ geringen Suchkosten. Es wird oft in Spielen verwendet.
Es gibt Fälle, in denen die kürzeste Entfernung nicht berechnet wird, während die Suchkosten niedrig sind. Tiefensuche (DFS) oder Breitensuche (BFS), die die kürzeste Entfernung berechnen kann, jedoch tendenziell hohe Berechnungskosten verursacht. ) Neigt dazu, bessere Ergebnisse zu erzielen.
Es basierte ursprünglich auf einem 1968 veröffentlichten Artikel. Die Gruppe von Algorithmen, die die kürzeste Entfernung finden, wird in diesem Artikel als "akzeptabel - zulässig" beschrieben. Das führende A ist also die Menge der Algorithmen, und diejenige, die die Anzahl der Auswertungen für die Berechnung der kürzesten Route optimiert, ist A \ *. Die Notation ist der Ursprung des Namens des Algorithmus.
Artikel-Link: Eine formale Grundlage für die heuristische Bestimmung von Mindestkostenpfaden
Die Gesamtkosten für das Verschieben einer Position (Knoten / Knoten) nach n betragen $ f (n) $, die Kosten von der Startposition zum Knoten an Position n betragen $ g (n) $ und ein als heuristisch bezeichneter Wert. Unter der Annahme, dass die berechnete Funktion (geschätzter Wert der Entfernung zum Ziel) $ h (n) $ ist, wird $ f (n) $ durch die folgende Summe berechnet.
f(n) = g(n) + h(n)
Obwohl nicht streng, berechnet dieser Artikel einfach $ g (n) $ als die Anzahl der Knoten, die von Anfang an verschoben wurden (einfach 1 für jede Bewegung), um die Berechnung zu vereinfachen. Entsprechend in Form von Addition).
Außerdem wird die Berechnung von $ h (n) $ dieses Mal gelöst. Da das Labyrinth ein Gittertyp ist, der nach oben, unten, links und rechts verschoben werden kann, wird die Manhattan-Distanz verwendet, wobei eine Bewegung nach oben, unten, links und rechts die Distanz 1 ist.
Ich werde den Code zum Verständnis in Python schreiben.
Verwenden Sie zum Erstellen eines Labyrinthgitters das aus "Suche nach Tiefenpriorität in Python schreiben". Die Details der Erklärung sind im Link geschrieben, daher werde ich sie weglassen, aber die grobe Zusammenfassung lautet wie folgt.
from __future__ import annotations
from typing import Optional
from typing import List
import random
#Konstanter Wert für den Eingang.
CELL_TYPE_START: str = 'S'
#Konstanter Wert für Passagen.
CELL_TYPE_PASSAGE: str = ' '
#Der konstante Wert der Wand.
CELL_TYPE_WALL: str = 'W'
#Konstanten Wert verlassen.
CELL_TYPE_GOAL: str = 'G'
#Ein konstanter Wert für den berechneten Routenpfad.
CELL_TYPE_PATH: str = '*'
class Location:
def __init__(self, row: int, column: int) -> None:
"""
Eine Klasse, die eine einzelne Positionsinformation des Labyrinthgitters verarbeitet.
Parameters
----------
row : int
Die Zeilennummer der Position. Beginnen Sie bei 0, 1 von oben nach unten
Wird hinzugefügt werden.
column : int
Die Spaltennummer der Position. Beginnen Sie bei 0, 1 von links nach rechts
Wird hinzugefügt werden.
"""
self.row: int = row
self.column: int = column
class Maze:
#Die vertikale Anzahl der zu erzeugenden Labyrinthgitter.
_ROW_NUM: int = 7
#Die Nummer neben dem Labyrinthgitter, die generiert werden soll.
_COLUMN_NUM: int = 15
#Prozentsatz der zu erzeugenden Wände. 1.Je näher es an 0 liegt, desto mehr Wände gibt es.
_WALL_SPARSENESS: float = 0.3
def __init__(self) -> None:
"""
Eine Klasse, die die Erzeugung und Steuerung eines zufälligen Labyrinthgitters übernimmt.
Notes
-----
Da jeder Zelltyp zufällig festgelegt wird, ist dies nicht immer von Anfang an der Fall
Beachten Sie, dass Sie nichts tun können, um Ihr Ziel zu erreichen.
"""
self._set_start_and_goal_location()
self._grid: List[List[str]] = []
self._fill_grid_by_passage_cell()
self._set_wall_type_to_cells_randomly()
self._set_start_and_goal_type_to_cell()
def _set_start_and_goal_location(self) -> None:
"""
Stellen Sie die Attribute der Koordinaten des Startpunkts (Eingang) und des Ziels (Ausgang) ein.
"""
self.start_loc: Location = Location(row=0, column=0)
self.goal_loc: Location = Location(
row=self._ROW_NUM - 1,
column=self._COLUMN_NUM - 1)
def _fill_grid_by_passage_cell(self) -> None:
"""
Fügen Sie allen Zellen Zellen hinzu und legen Sie den Zelltyp der Passage fest.
"""
for row in range(self._ROW_NUM):
row_cells: List[str] = []
for column in range(self._COLUMN_NUM):
row_cells.append(CELL_TYPE_PASSAGE)
self._grid.append(row_cells)
def _set_wall_type_to_cells_randomly(self) -> None:
"""
Legen Sie den Wandzelltyp für jede Zelle im Raster zufällig fest.
"""
for row in range(self._ROW_NUM):
for column in range(self._COLUMN_NUM):
probability = random.uniform(0.0, 1.0)
if probability >= self._WALL_SPARSENESS:
continue
self._grid[row][column] = CELL_TYPE_WALL
def _set_start_and_goal_type_to_cell(self) -> None:
"""
An der Startposition (Eingang) bzw. an der Zielposition (Ausgang)
Stellen Sie den Zelltyp ein.
"""
self._grid[self.start_loc.row][self.start_loc.column] = \
CELL_TYPE_START
self._grid[self.goal_loc.row][self.goal_loc.column] = \
CELL_TYPE_GOAL
def is_goal_loc(self, location: Location) -> bool:
"""
Ruft den booleschen Wert ab, ob die angegebene Position die Zielposition ist.
Parameters
----------
location : Location
Position für das Urteil.
Returns
-------
result : bool
True wird gesetzt, wenn es sich um die Zielposition handelt.
"""
if (location.row == self.goal_loc.row
and location.column == self.goal_loc.column):
return True
return False
def get_movable_locations(self, location: Location) -> List[Location]:
"""
Holen Sie sich eine Liste der beweglichen Positionen von der angegebenen Position.
Parameters
----------
location : Location
Eine Instanz der Referenzposition.
Returns
-------
movable_locations : list of Location
Eine Liste mit Instanzen von beweglichen Orten.
"""
movable_locations: List[Location] = []
#Beurteilung der Verarbeitung, ob es nach oben verschoben werden kann oder nicht.
if location.row + 1 < self._ROW_NUM:
is_wall: bool = self._grid[location.row + 1][location.column] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row + 1, column=location.column))
#Beurteilungsverarbeitung, ob es nach unten verschoben werden kann.
if location.row - 1 >= 0:
is_wall = self._grid[location.row - 1][location.column] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row - 1, column=location.column))
#Urteilsverarbeitung, ob es nach rechts verschoben werden kann.
if location.column + 1 < self._COLUMN_NUM:
is_wall = self._grid[location.row][location.column + 1] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row, column=location.column + 1))
#Beurteilungsverarbeitung, ob es nach links verschoben werden kann.
if location.column - 1 >= 0:
is_wall = self._grid[location.row][location.column - 1] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row, column=location.column - 1))
return movable_locations
def set_path_type_to_cells(self, path: List[Location]) -> None:
"""
Für Zellen, die im angegebenen Pfad zum Ein- und Ausgang enthalten sind
Legen Sie den Zelltyp des Pfads fest.
Parameters
----------
path : list of Location
Die Positionsinformationen jeder Zelle vom Eingang bis zum Ausgang, die durch die Suche erhalten wurden
Gespeicherte Liste.
"""
for location in path:
self._grid[location.row][location.column] = CELL_TYPE_PATH
#Die im Pfad enthaltenen Eingangs- und Ausgangsteile sind das Original
#Reflektieren Sie den Zelltyp.
self._grid[self.start_loc.row][self.start_loc.column] = \
CELL_TYPE_START
self._grid[self.goal_loc.row][self.goal_loc.column] = \
CELL_TYPE_GOAL
def __str__(self) -> str:
"""
Ruft die Typzeichenfolge für jede Zelle im Raster ab.
Returns
-------
grid_str : str
Eine Zeichenfolge für jede Zelle im Raster.
"""
grid_str: str = ''
for row_cells in self._grid:
grid_str += '-' * self._COLUMN_NUM * 2
grid_str += '\n'
for cell_type in row_cells:
grid_str += cell_type
grid_str += '|'
grid_str += '\n'
return grid_str
class Node:
def __init__(self, location: Location, parent: Optional[Node]):
"""
Daten für einen einzelnen Knoten, um Informationen wie die Position und den Übergang des Labyrinths aufzunehmen
Klasse zu handhaben.
Parameters
----------
location : Location
Eine Instanz, die die Standortinformationen des Ziels verarbeitet.
parent : Node or None
Eine Instanz eines Knotens, der Standortinformationen vor dem Verschieben verarbeitet. Zu Beginn der Suche
Usw. wird None sein.
"""
self.location: Location = location
self.parent: Optional[Node] = parent
def get_path_from_goal_node(goal_node: Node) -> List[Location]:
"""
Vom Ausgangsknoten der Pfad vom Eingang, der durch Suchen zum Ausgang erhalten wird
erhalten.
Parameters
----------
goal_node : Node
Eine Instanz des Ziel-Exit- (Ziel-) Knotens.
Returns
-------
path : list of Location
Eine Liste mit Instanzen jedes Standorts vom Eingang bis zum Ausgang.
"""
path: List[Location] = [goal_node.location]
node: Node = goal_node
while node.parent is not None:
node = node.parent
path.append(node.location)
path.reverse()
return path
Wenn Sie versuchen, das als Versuch erzeugte Labyrinth auszugeben, wird es wie unten gezeigt in einem Raster angezeigt.
if __name__ == '__main__':
maze = Maze()
print(maze)
------------------------------
S| |W| |W| | | |W| |W| |W| |W|
------------------------------
W| | | | | |W| | | |W|W| |W|W|
------------------------------
W| | | | |W| | | |W|W| | | | |
------------------------------
| |W| |W|W| | | | | | | |W|W|
------------------------------
W|W|W| | | |W| | | | | | | |W|
------------------------------
W|W| | | | | | | |W| |W| | | |
------------------------------
W|W| | | | |W| | | | | | | |G|
Der A \ * -Algorithmus verwendet eine Prioritätswarteschlange als Datenstruktur. Dies ist eine spezielle Warteschlange, in der Werte mit Priorität zur Warteschlange hinzugefügt werden. Der Wert mit der höchsten Priorität wird auch beim Abrufen des Werts berücksichtigt.
Sie müssen der Knotenklasse die Methode __lt__ hinzufügen, da der Prioritätswert vom Operator kleiner als der Vergleich (<) für die Instanz des Knotens berechnet wird, den Sie der Warteschlange hinzufügen möchten.
Bei der Methode lt wird $ g (n) + h (n) $ in der Kostenformel berechnet und mit einem anderen Knoten verglichen.
Passen Sie außerdem den Wert von $ g (n) $ und den Wert von $ h (n) $ so an, dass sie in den Klassenattributen enthalten sind, da sie für die Berechnung erforderlich sind.
class Node:
def __init__(
self, location: Location, parent: Optional[Node],
cost: float, heuristic:float) -> None:
"""
Daten für einen einzelnen Knoten, um Informationen wie die Position und den Übergang des Labyrinths aufzunehmen
Klasse zu handhaben.
Parameters
----------
location : Location
Eine Instanz, die die Standortinformationen des Ziels verarbeitet.
parent : Node or None
Eine Instanz eines Knotens, der Standortinformationen vor dem Verschieben verarbeitet. Zu Beginn der Suche
Usw. wird None sein.
cost : float
Kostenwert von der Startposition bis zur Position des entsprechenden Knotens (g(n)damit
Erhaltener Wert).
heuristic : float
Geschätzte Entfernung von diesem Knoten zum Ausgang (h(n)Wert erhalten durch).
"""
self.location: Location = location
self.parent: Optional[Node] = parent
self.cost = cost
self.heuristic = heuristic
def __lt__(self, other_node: Node) -> bool:
"""
Vergleichsoperator( < )Methode zur Verarbeitung durch.
Wird zur Steuerung priorisierter Warteschlangen verwendet.
Parameters
----------
other_node : Node
Instanzen anderer zu vergleichender Knoten.
Returns
-------
result_bool : bool
Vergleichsergebnis. Berechnungsverarbeitung sind die Kosten vom Eingang (g(n))Wann
Hulistischer Wert (h(n)) Durch Vergleichen des Gesamtwertes
Getan werden.
"""
left_value: float = self.cost + self.heuristic
right_value: float = other_node.cost + other_node.heuristic
result_bool: bool = left_value < right_value
return result_bool
Ich habe die Methode "lt" noch nie alleine verwendet, daher werde ich versuchen, mehrere Instanzen zu erstellen und sie zu vergleichen, um die Ergebnisse anzuzeigen. Der Vergleich basiert auf der Summe aus Kosten und Heuristik, sodass der erste Vergleich falsch und der zweite wahr ist.
if __name__ == '__main__':
node_1 = Node(
location=Location(row=0, column=0),
parent=None,
cost=2, heuristic=2)
node_2 = Node(
location=Location(row=0, column=0),
parent=None,
cost=1, heuristic=2)
node_3 = Node(
location=Location(row=0, column=0),
parent=None,
cost=3, heuristic=2)
print(node_1 < node_2)
print(node_1 < node_3)
False
True
Als nächstes bereiten wir die Prioritätswarteschlange vor. Die Verarbeitung der Prioritätswarteschlange kann mithilfe des heapq-Pakets des Python-Standardmoduls erfolgen.
import heapq
...
class PriorityQueue:
def __init__(self) -> None:
"""
Eine Klasse zum Steuern von Prioritätswarteschlangen.
"""
self._container: List[Node] = []
@property
def empty(self) -> bool:
"""
Attributwert, ob die Warteschlange leer ist.
Returns
-------
result : bool
Auf Leer setzen, wenn leer.
"""
return not self._container
def push(self, node: Node) -> None:
"""
Fügen Sie der Warteschlange eine Instanz des Knotens hinzu.
Parameters
----------
node : Node
Instanz des hinzuzufügenden Knotens.
"""
heapq.heappush(self._container, node)
def pop(self) -> Node:
"""
Extrahieren Sie die Instanz des Knotens mit der höchsten Priorität aus der Warteschlange.
Returns
-------
node : Node
Eine Instanz der abgerufenen Node-Klasse.
"""
return heapq.heappop(self._container)
Lassen Sie uns tatsächlich ein wenig bewegen und versuchen, ob die Verarbeitung auf eine Weise erfolgt, die Priorität berücksichtigt. Es ist zu beachten, dass das Formular "Niedrige Kosten sind vorzuziehen (= hohe Priorität)". Es wird nicht von Pop aus dem mit dem höchsten Gesamtkostenwert herausgenommen.
if __name__ == '__main__':
priority_queue = PriorityQueue()
priority_queue.push(
node=Node(
location=Location(row=0, column=0),
parent=None,
cost=1,
heuristic=1))
priority_queue.push(
node=Node(
location=Location(row=0, column=0),
parent=None,
cost=3,
heuristic=3))
priority_queue.push(
node=Node(
location=Location(row=0, column=0),
parent=None,
cost=2,
heuristic=3))
node: Node = priority_queue.pop()
print(node.cost, node.heuristic)
node = priority_queue.pop()
print(node.cost, node.heuristic)
node = priority_queue.pop()
print(node.cost, node.heuristic)
Sie können sehen, dass die Ausgabeergebnisse in aufsteigender Reihenfolge der Gesamtkosten abgerufen werden.
1 1
2 3
3 3
Da diesmal die Berechnung der Heuristik ($ h (n) $) ein Labyrinth im Rasterformat ist, wird die Manhattan-Entfernung verwendet. Fügen Sie diese Funktion daher der Labyrinth-Klasse hinzu.
def get_manhattan_distance(self, location: Location) -> int:
"""
Der Manhattan-Abstand zwischen der Zielposition und der Ausgangsposition (Zielposition)
erhalten.
Parameters
----------
location : Location
Eine Instanz des Zielorts.
Returns
-------
distance : int
Manhattan Abstand zwischen der Zielposition und der Ausgangsposition. Spaltenrichtung
Die Summe aus dem Absolutwert der Differenz und dem Absolutwert der Differenz in Zeilenrichtung wird eingestellt.
"""
x_distance: int = abs(location.column - self.goal_loc.column)
y_distance: int = abs(location.row - self.goal_loc.column)
distance: int = x_distance + y_distance
return distance
Nachdem wir alle notwendigen Vorbereitungen getroffen haben, erstellen wir eine Funktion für den A \ * -Algorithmus. Der Funktionsname ist astar.
from typing import Callable, Dict
...
def astar(
init_loc: Location,
is_goal_loc_method: Callable[[Location], bool],
get_movable_locations_method: Callable[[Location], List[Location]],
hueristic_method: Callable[[Location], int],
) -> Optional[Node]:
"""
A*Führen Sie die Suchverarbeitung nach Algorithmus durch.
Parameters
----------
init_loc : Location
Suche Startposition (Position des Eingangs des Labyrinths).
is_goal_loc_method : callable
Eine Methode, die bestimmt, ob die Zielposition der Ausgang (Ziel) ist.
get_movable_locations_method : callable
Eine Methode zum Abrufen einer Liste von Zellenpositionen, die von der Zielposition verschoben werden sollen.
hueristic_method : callable
Ermitteln Sie den Abstand zwischen der Zielposition und der Ausgangsposition (Zielposition)
Eine Methode zur Heuristik für.
Returns
-------
goal_node : Node or None
Eine Instanz des Knotens am berechneten Austrittsort. Zum Ausgang
Keine wird in Fällen festgelegt, in denen die Route nicht berechnet werden kann.
"""
frontier_queue: PriorityQueue = PriorityQueue()
frontier_queue.push(
node=Node(
location=init_loc,
parent=None,
cost=0,
heuristic=hueristic_method(init_loc)))
explored_loc_cost_dict: Dict[Location, float] = {init_loc: 0.0}
while not frontier_queue.empty:
current_node: Node = frontier_queue.pop()
current_loc: Location = current_node.location
if is_goal_loc_method(current_loc):
return current_node
movable_locations = get_movable_locations_method(current_loc)
for movable_location in movable_locations:
new_cost: float = current_node.cost + 1
#Ein neues Ziel wurde bereits gesucht und ist nicht kostengünstig
#Wenn ja, überspringen Sie es.
if (movable_location in explored_loc_cost_dict and
explored_loc_cost_dict[movable_location] <= new_cost):
continue
explored_loc_cost_dict[movable_location] = new_cost
frontier_queue.push(
node=Node(
location=movable_location,
parent=current_node,
cost=new_cost,
heuristic=hueristic_method(movable_location)))
return None
Ich habe früher geschrieben: "Schreibe Suche mit Tiefenpriorität in Python. “ähnelt der Ablauf der dfs-Funktion im Artikel. Da die Verarbeitung teilweise unterschiedlich ist, werde ich hauptsächlich den Unterschied erklären.
Zunächst wird für das Argument das Callable (hueristic_method) für die Heuristik hinzugefügt. Dies gibt die Methode zur Berechnung der Manhattan-Entfernung an, die vor einiger Zeit in diesem Beispiel hinzugefügt wurde.
frontier_queue: PriorityQueue = PriorityQueue()
frontier_queue.push(
node=Node(
location=init_loc,
parent=None,
cost=0,
heuristic=hueristic_method(init_loc)))
Außerdem wurde die Warteschlange durch die der Prioritätswarteschlange (frontier_queue) ersetzt. Wir fügen dieser Warteschlange Knoten hinzu, die untersucht werden sollen.
explored_loc_cost_dict: Dict[Location, float] = {init_loc: 0.0}
Das Wörterbuch, das die gesuchten Knoten enthält, besteht aus der Position der Position im Schlüssel und dem Wert der Kosten ($ g (n) $) im Wert. Da es sich um eine einfache Methode handelt, die bei jeder Bewegung um 1 erhöht wird, setzen Sie zuerst 0.0.
while not frontier_queue.empty:
current_node: Node = frontier_queue.pop()
current_loc: Location = current_node.location
Der Vorgang wird in einer while-Schleife wiederholt, bis der zu durchsuchende Knoten aus der Warteschlange verschwindet.
if is_goal_loc_method(current_loc):
return current_node
Wenn der Zielknoten ein Exit (Ziel) ist, wird der Vorgang durch Zurückgeben des Exit-Knotens abgeschlossen.
movable_locations = get_movable_locations_method(current_loc)
for movable_location in movable_locations:
new_cost: float = current_node.cost + 1
Jede Position, die vom aktuellen Suchzielknoten verschoben werden soll, wird von einer for-Schleife verarbeitet. Dieses Mal wird es in einer einfachen Form implementiert, die die Kosten ($ g (n) $) bei jeder Bewegung um 1 erhöht.
#Ein neues Ziel wurde bereits gesucht und ist nicht kostengünstig
#Wenn ja, überspringen Sie es.
if (movable_location in explored_loc_cost_dict and
explored_loc_cost_dict[movable_location] <= new_cost):
continue
Auch wenn es sich um eine gesuchte Position handelt, lohnt es sich zu suchen, ob sie kostengünstig ist. Wenn es bereits durchsucht wurde und sich die Position in Bezug auf die Kosten nicht ändert oder verschlechtert, ist die Suche nicht sinnvoll. Überspringen Sie sie daher.
explored_loc_cost_dict[movable_location] = new_cost
frontier_queue.push(
node=Node(
location=movable_location,
parent=current_node,
cost=new_cost,
heuristic=hueristic_method(movable_location)))
Wenn die Bedingungen eine Suche wert sind, legen wir Werte wie Kosten im durchsuchten Wörterbuch fest und fügen Knoten zu der zu durchsuchenden priorisierten Warteschlange hinzu.
Da die Elemente mit der höchsten Priorität zuerst verarbeitet werden, können Sie eine Suche mit hervorragenden Suchkosten durchführen.
return None
Abhängig vom erzeugten Labyrinth gibt es möglicherweise keine Route zum Ausgang. In diesem Fall wird keine zurückgegeben.
Ich werde es versuchen.
if __name__ == '__main__':
maze: Maze = Maze()
print(maze)
goal_node: Optional[Node] = astar(
init_loc=maze.start_loc,
is_goal_loc_method=maze.is_goal_loc,
get_movable_locations_method=maze.get_movable_locations,
hueristic_method=maze.get_manhattan_distance,
)
if goal_node is None:
print('Es ist ein Labyrinth, in dem der Ausgang nicht berechnet werden kann.')
else:
print('-' * 20)
path: List[Location] = get_path_from_goal_node(
goal_node=goal_node)
maze.set_path_type_to_cells(path=path)
print('Berechneter Pfad:')
print(maze)
Berechneter Pfad:
------------------------------
S|*|*|*|*| | | |W| | | |W|W|W|
------------------------------
W| | |W|*|*|W|W|W| | | | |W| |
------------------------------
W|W| |W|W|*|W| | | | |W|W|W|W|
------------------------------
W|W|W| | |*|*|W| |W| | | | | |
------------------------------
|W|W|W| | |*|W| | | | | |W| |
------------------------------
| | | | |W|*|*|*|*|*| | |W| |
------------------------------
|W| | |W|W|W| |W| |*|*|*|*|G|
S im Raster ist der Eingang (Start), G ist der Ausgang (Ziel) und der Stern ist der durch die Suche berechnete Pfad. Der Weg vom Eingang zum Ausgang wurde sicher berechnet.
Es ist ein Merkmal von A \ *, dass ein diagonaler Pfad im Vergleich zur Suche mit Breitenpriorität erhalten wird, bei der das Suchergebnis leicht rechtwinklig ist. Sogar das Beispiel, das ich dieses Mal tatsächlich ausprobiert habe, hat einen leicht diagonalen Pfad.
from __future__ import annotations
from typing import Optional
from typing import List
import random
import heapq
from typing import Callable, Dict
#Konstanter Wert für den Eingang.
CELL_TYPE_START: str = 'S'
#Konstanter Wert für Passagen.
CELL_TYPE_PASSAGE: str = ' '
#Der konstante Wert der Wand.
CELL_TYPE_WALL: str = 'W'
#Konstanten Wert verlassen.
CELL_TYPE_GOAL: str = 'G'
#Ein konstanter Wert für den berechneten Routenpfad.
CELL_TYPE_PATH: str = '*'
class Location:
def __init__(self, row: int, column: int) -> None:
"""
Eine Klasse, die eine einzelne Positionsinformation des Labyrinthgitters verarbeitet.
Parameters
----------
row : int
Die Zeilennummer der Position. Beginnen Sie bei 0, 1 von oben nach unten
Wird hinzugefügt werden.
column : int
Die Spaltennummer der Position. Beginnen Sie bei 0, 1 von links nach rechts
Wird hinzugefügt werden.
"""
self.row: int = row
self.column: int = column
class Maze:
#Die vertikale Anzahl der zu erzeugenden Labyrinthgitter.
_ROW_NUM: int = 7
#Die Nummer neben dem Labyrinthgitter, die generiert werden soll.
_COLUMN_NUM: int = 15
#Prozentsatz der zu erzeugenden Wände. 1.Je näher es an 0 liegt, desto mehr Wände gibt es.
_WALL_SPARSENESS: float = 0.3
def __init__(self) -> None:
"""
Eine Klasse, die die Erzeugung und Steuerung eines zufälligen Labyrinthgitters übernimmt.
Notes
-----
Da jeder Zelltyp zufällig festgelegt wird, ist dies nicht immer von Anfang an der Fall
Beachten Sie, dass Sie nichts tun können, um Ihr Ziel zu erreichen.
"""
self._set_start_and_goal_location()
self._grid: List[List[str]] = []
self._fill_grid_by_passage_cell()
self._set_wall_type_to_cells_randomly()
self._set_start_and_goal_type_to_cell()
def _set_start_and_goal_location(self) -> None:
"""
Stellen Sie die Attribute der Koordinaten des Startpunkts (Eingang) und des Ziels (Ausgang) ein.
"""
self.start_loc: Location = Location(row=0, column=0)
self.goal_loc: Location = Location(
row=self._ROW_NUM - 1,
column=self._COLUMN_NUM - 1)
def _fill_grid_by_passage_cell(self) -> None:
"""
Fügen Sie allen Zellen Zellen hinzu und legen Sie den Zelltyp der Passage fest.
"""
for row in range(self._ROW_NUM):
row_cells: List[str] = []
for column in range(self._COLUMN_NUM):
row_cells.append(CELL_TYPE_PASSAGE)
self._grid.append(row_cells)
def _set_wall_type_to_cells_randomly(self) -> None:
"""
Legen Sie den Wandzelltyp für jede Zelle im Raster zufällig fest.
"""
for row in range(self._ROW_NUM):
for column in range(self._COLUMN_NUM):
probability = random.uniform(0.0, 1.0)
if probability >= self._WALL_SPARSENESS:
continue
self._grid[row][column] = CELL_TYPE_WALL
def _set_start_and_goal_type_to_cell(self) -> None:
"""
An der Startposition (Eingang) bzw. an der Zielposition (Ausgang)
Stellen Sie den Zelltyp ein.
"""
self._grid[self.start_loc.row][self.start_loc.column] = \
CELL_TYPE_START
self._grid[self.goal_loc.row][self.goal_loc.column] = \
CELL_TYPE_GOAL
def is_goal_loc(self, location: Location) -> bool:
"""
Ruft den booleschen Wert ab, ob die angegebene Position die Zielposition ist.
Parameters
----------
location : Location
Position für das Urteil.
Returns
-------
result : bool
True wird gesetzt, wenn es sich um die Zielposition handelt.
"""
if (location.row == self.goal_loc.row
and location.column == self.goal_loc.column):
return True
return False
def get_movable_locations(self, location: Location) -> List[Location]:
"""
Holen Sie sich eine Liste der beweglichen Positionen von der angegebenen Position.
Parameters
----------
location : Location
Eine Instanz der Referenzposition.
Returns
-------
movable_locations : list of Location
Eine Liste mit Instanzen von beweglichen Orten.
"""
movable_locations: List[Location] = []
#Beurteilung der Verarbeitung, ob es nach oben verschoben werden kann oder nicht.
if location.row + 1 < self._ROW_NUM:
is_wall: bool = self._grid[location.row + 1][location.column] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row + 1, column=location.column))
#Beurteilungsverarbeitung, ob es nach unten verschoben werden kann.
if location.row - 1 >= 0:
is_wall = self._grid[location.row - 1][location.column] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row - 1, column=location.column))
#Urteilsverarbeitung, ob es nach rechts verschoben werden kann.
if location.column + 1 < self._COLUMN_NUM:
is_wall = self._grid[location.row][location.column + 1] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row, column=location.column + 1))
#Beurteilungsverarbeitung, ob es nach links verschoben werden kann.
if location.column - 1 >= 0:
is_wall = self._grid[location.row][location.column - 1] \
== CELL_TYPE_WALL
if not is_wall:
movable_locations.append(
Location(row=location.row, column=location.column - 1))
return movable_locations
def set_path_type_to_cells(self, path: List[Location]) -> None:
"""
Für Zellen, die im angegebenen Pfad zum Ein- und Ausgang enthalten sind
Legen Sie den Zelltyp des Pfads fest.
Parameters
----------
path : list of Location
Die Positionsinformationen jeder Zelle vom Eingang bis zum Ausgang, die durch die Suche erhalten wurden
Gespeicherte Liste.
"""
for location in path:
self._grid[location.row][location.column] = CELL_TYPE_PATH
#Die im Pfad enthaltenen Eingangs- und Ausgangsteile sind das Original
#Reflektieren Sie den Zelltyp.
self._grid[self.start_loc.row][self.start_loc.column] = \
CELL_TYPE_START
self._grid[self.goal_loc.row][self.goal_loc.column] = \
CELL_TYPE_GOAL
def get_manhattan_distance(self, location: Location) -> int:
"""
Der Manhattan-Abstand zwischen der Zielposition und der Ausgangsposition (Zielposition)
erhalten.
Parameters
----------
location : Location
Eine Instanz des Zielorts.
Returns
-------
distance : int
Manhattan Abstand zwischen der Zielposition und der Ausgangsposition. Spaltenrichtung
Die Summe aus dem Absolutwert der Differenz und dem Absolutwert der Differenz in Zeilenrichtung wird eingestellt.
"""
x_distance: int = abs(location.column - self.goal_loc.column)
y_distance: int = abs(location.row - self.goal_loc.column)
distance: int = x_distance + y_distance
return distance
def __str__(self) -> str:
"""
Ruft die Typzeichenfolge für jede Zelle im Raster ab.
Returns
-------
grid_str : str
Eine Zeichenfolge für jede Zelle im Raster.
"""
grid_str: str = ''
for row_cells in self._grid:
grid_str += '-' * self._COLUMN_NUM * 2
grid_str += '\n'
for cell_type in row_cells:
grid_str += cell_type
grid_str += '|'
grid_str += '\n'
return grid_str
class Node:
def __init__(
self, location: Location, parent: Optional[Node],
cost: float, heuristic:float) -> None:
"""
Daten für einen einzelnen Knoten, um Informationen wie die Position und den Übergang des Labyrinths aufzunehmen
Klasse zu handhaben.
Parameters
----------
location : Location
Eine Instanz, die die Standortinformationen des Ziels verarbeitet.
parent : Node or None
Eine Instanz eines Knotens, der Standortinformationen vor dem Verschieben verarbeitet. Zu Beginn der Suche
Usw. wird None sein.
cost : float
Kostenwert von der Startposition bis zur Position des entsprechenden Knotens (g(n)damit
Erhaltener Wert).
heuristic : float
Geschätzte Entfernung von diesem Knoten zum Ausgang (h(n)Wert erhalten durch).
"""
self.location: Location = location
self.parent: Optional[Node] = parent
self.cost = cost
self.heuristic = heuristic
def __lt__(self, other_node: Node) -> bool:
"""
Vergleichsoperator( < )Methode zur Verarbeitung durch.
Wird zur Steuerung priorisierter Warteschlangen verwendet.
Parameters
----------
other_node : Node
Instanzen anderer zu vergleichender Knoten.
Returns
-------
result_bool : bool
Vergleichsergebnis. Berechnungsverarbeitung sind die Kosten vom Eingang (g(n))Wann
Hulistischer Wert (h(n)) Durch Vergleichen des Gesamtwertes
Getan werden.
"""
left_value: float = self.cost + self.heuristic
right_value: float = other_node.cost + other_node.heuristic
result_bool: bool = left_value < right_value
return result_bool
def get_path_from_goal_node(goal_node: Node) -> List[Location]:
"""
Vom Ausgangsknoten der Pfad vom Eingang, der durch Suchen zum Ausgang erhalten wird
erhalten.
Parameters
----------
goal_node : Node
Eine Instanz des Ziel-Exit- (Ziel-) Knotens.
Returns
-------
path : list of Location
Eine Liste mit Instanzen jedes Standorts vom Eingang bis zum Ausgang.
"""
path: List[Location] = [goal_node.location]
node: Node = goal_node
while node.parent is not None:
node = node.parent
path.append(node.location)
path.reverse()
return path
class PriorityQueue:
def __init__(self) -> None:
"""
Eine Klasse zum Steuern von Prioritätswarteschlangen.
"""
self._container: List[Node] = []
@property
def empty(self) -> bool:
"""
Attributwert, ob die Warteschlange leer ist.
Returns
-------
result : bool
Auf Leer setzen, wenn leer.
"""
return not self._container
def push(self, node: Node) -> None:
"""
Fügen Sie der Warteschlange eine Instanz des Knotens hinzu.
Parameters
----------
node : Node
Instanz des hinzuzufügenden Knotens.
"""
heapq.heappush(self._container, node)
def pop(self) -> Node:
"""
Extrahieren Sie die Instanz des Knotens mit der höchsten Priorität aus der Warteschlange.
Returns
-------
node : Node
Eine Instanz der abgerufenen Node-Klasse.
"""
return heapq.heappop(self._container)
def astar(
init_loc: Location,
is_goal_loc_method: Callable[[Location], bool],
get_movable_locations_method: Callable[[Location], List[Location]],
hueristic_method: Callable[[Location], int],
) -> Optional[Node]:
"""
A*Führen Sie die Suchverarbeitung nach Algorithmus durch.
Parameters
----------
init_loc : Location
Suche Startposition (Position des Eingangs des Labyrinths).
is_goal_loc_method : callable
Eine Methode, die bestimmt, ob die Zielposition der Ausgang (Ziel) ist.
get_movable_locations_method : callable
Eine Methode zum Abrufen einer Liste von Zellenpositionen, die von der Zielposition verschoben werden sollen.
hueristic_method : callable
Ermitteln Sie den Abstand zwischen der Zielposition und der Ausgangsposition (Zielposition)
Eine Methode zur Heuristik für.
Returns
-------
goal_node : Node or None
Eine Instanz des Knotens am berechneten Austrittsort. Zum Ausgang
Keine wird in Fällen festgelegt, in denen die Route nicht berechnet werden kann.
"""
frontier_queue: PriorityQueue = PriorityQueue()
frontier_queue.push(
node=Node(
location=init_loc,
parent=None,
cost=0,
heuristic=hueristic_method(init_loc)))
explored_loc_cost_dict: Dict[Location, float] = {init_loc: 0.0}
while not frontier_queue.empty:
current_node: Node = frontier_queue.pop()
current_loc: Location = current_node.location
if is_goal_loc_method(current_loc):
return current_node
movable_locations = get_movable_locations_method(current_loc)
for movable_location in movable_locations:
new_cost: float = current_node.cost + 1
#Ein neues Ziel wurde bereits gesucht und ist nicht kostengünstig
#Wenn ja, überspringen Sie es.
if (movable_location in explored_loc_cost_dict and
explored_loc_cost_dict[movable_location] <= new_cost):
continue
explored_loc_cost_dict[movable_location] = new_cost
frontier_queue.push(
node=Node(
location=movable_location,
parent=current_node,
cost=new_cost,
heuristic=hueristic_method(movable_location)))
return None
if __name__ == '__main__':
maze: Maze = Maze()
print(maze)
goal_node: Optional[Node] = astar(
init_loc=maze.start_loc,
is_goal_loc_method=maze.is_goal_loc,
get_movable_locations_method=maze.get_movable_locations,
hueristic_method=maze.get_manhattan_distance,
)
if goal_node is None:
print('Es ist ein Labyrinth, in dem der Ausgang nicht berechnet werden kann.')
else:
print('-' * 20)
path: List[Location] = get_path_from_goal_node(
goal_node=goal_node)
maze.set_path_type_to_cells(path=path)
print('Berechneter Pfad:')
print(maze)
――Wenn ich ursprünglich Absolvent einer Schule im Bereich Design war, verzeihen Sie bitte Masakari, der über fundierte Kenntnisse im Bereich Informatik verfügt.
Recommended Posts