Cet algorithme utilise la somme de g comme distance au point actuel et la valeur estimée h à l'objectif comme paramètres pendant la recherche, et calcule la distance la plus courte de l'itinéraire avec un coût de recherche relativement faible. Il est souvent utilisé dans les jeux.
Il y a des cas où la distance la plus courte n'est pas calculée alors que le coût de recherche est faible (recherche en profondeur d'abord / DFS) et la recherche avec priorité à la largeur (recherche en largeur d'abord / BFS) où la distance la plus courte peut être calculée mais le coût de calcul a tendance à être élevé. ) A tendance à donner de meilleurs résultats.
Il était à l'origine basé sur un article publié en 1968. Le groupe d'algorithmes qui trouvent la distance la plus courte est décrit comme "acceptable - Admissible" dans l'article, donc le premier A est l'ensemble des algorithmes, et celui qui optimise le nombre d'évaluations pour le calcul d'itinéraire le plus court est A \ * La notation est à l'origine du nom de l'algorithme.
Lien de l'article: Une base formelle pour la détermination heuristique des chemins de coût minimum
Le coût total du déplacement d'une position (nœud / nœud) vers n est $ f (n) $, le coût de la position de départ au nœud à la position n est $ g (n) $, et une valeur appelée heuristique. En supposant que la fonction qui calcule (valeur estimée de la distance au but) est $ h (n) $, $ f (n) $ est calculé par la somme suivante.
f(n) = g(n) + h(n)
Bien que non rigoureux, cet article calcule simplement $ g (n) $ comme le nombre de nœuds déplacés depuis le début (simplement 1 pour chaque déplacement) pour simplifier le calcul. Correspondant sous forme d'ajout).
De plus, le calcul de $ h (n) $ sera résolu cette fois. Étant donné que le labyrinthe est un type de grille qui peut être déplacé vers le haut, le bas, la gauche et la droite, la distance Manhattan est utilisée, où un mouvement vers le haut, le bas, la gauche et la droite est la distance 1.
J'écrirai le code en Python pour comprendre.
Pour le processus de création d'une grille de labyrinthe, utilisez celle de "Recherche de priorité en profondeur d'écriture en Python". Les détails de l'explication sont écrits dans le lien, je vais donc l'omettre, mais il sera résumé comme suit.
-Représenté par une grille de lignes et de colonnes définies.
from __future__ import annotations
from typing import Optional
from typing import List
import random
#Valeur constante pour l'entrée.
CELL_TYPE_START: str = 'S'
#Valeur constante pour les passages.
CELL_TYPE_PASSAGE: str = ' '
#La valeur constante du mur.
CELL_TYPE_WALL: str = 'W'
#Quitter la valeur constante.
CELL_TYPE_GOAL: str = 'G'
#Une valeur constante pour le chemin d'itinéraire calculé.
CELL_TYPE_PATH: str = '*'
class Location:
def __init__(self, row: int, column: int) -> None:
"""
Une classe qui gère une seule information de position de la grille du labyrinthe.
Parameters
----------
row : int
Le numéro de ligne de la position. Commencez par 0, 1 de haut en bas
Sera ajouté.
column : int
Le numéro de colonne de la position. Partir de 0, 1 de gauche à droite
Sera ajouté.
"""
self.row: int = row
self.column: int = column
class Maze:
#Le nombre vertical de grilles de labyrinthe à générer.
_ROW_NUM: int = 7
#Le numéro à côté de la grille du labyrinthe à générer.
_COLUMN_NUM: int = 15
#Pourcentage de murs à générer. 1.Plus il est proche de 0, plus il y a de murs.
_WALL_SPARSENESS: float = 0.3
def __init__(self) -> None:
"""
Une classe qui gère la génération et le contrôle d'une grille de labyrinthe aléatoire.
Notes
-----
Étant donné que chaque type de cellule est défini au hasard, ce n'est pas toujours depuis le début
Notez que vous ne pouvez rien faire qui puisse atteindre votre objectif.
"""
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:
"""
Définissez les attributs des coordonnées du point de départ (entrée) et de l'objectif (sortie).
"""
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:
"""
Ajoutez des cellules à toutes les cellules et définissez le type de cellule du passage.
"""
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:
"""
Définissez de manière aléatoire le type de cellule de paroi pour chaque cellule de la grille.
"""
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:
"""
Aux positions de départ (entrée) et de but (sortie), respectivement
Définissez le type de cellule.
"""
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:
"""
Obtient la valeur booléenne indiquant si la position spécifiée est la position cible.
Parameters
----------
location : Location
Position pour le jugement.
Returns
-------
result : bool
True est défini s'il s'agit de la position cible.
"""
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]:
"""
Obtenez une liste des positions mobiles à partir de la position spécifiée.
Parameters
----------
location : Location
Une instance de la position de référence.
Returns
-------
movable_locations : list of Location
Une liste contenant des instances d'emplacements mobiles.
"""
movable_locations: List[Location] = []
#Traitement du jugement pour savoir s'il peut ou non être déplacé vers le haut.
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))
#Traitement du jugement pour savoir s'il peut être déplacé vers le bas.
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))
#Traitement du jugement pour savoir s'il peut être déplacé vers la droite.
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))
#Traitement du jugement pour savoir s'il peut être déplacé vers la gauche.
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:
"""
Pour les cellules contenues dans le chemin spécifié vers l'entrée et la sortie
Définissez le type de cellule du chemin.
Parameters
----------
path : list of Location
Les informations de position de chaque cellule de l'entrée à la sortie obtenues par la recherche
Liste stockée.
"""
for location in path:
self._grid[location.row][location.column] = CELL_TYPE_PATH
#Les pièces d'entrée et de sortie incluses dans le chemin sont d'origine
#Reflétez le type de cellule.
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:
"""
Obtient la chaîne de type pour chaque cellule de la grille.
Returns
-------
grid_str : str
Une chaîne de types pour chaque cellule de la grille.
"""
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]):
"""
Données pour un seul nœud pour contenir des informations telles que la position et la transition du labyrinthe
Classe à gérer.
Parameters
----------
location : Location
Une instance qui gère les informations de localisation de la cible.
parent : Node or None
Une instance d'un nœud qui gère les informations de position avant de se déplacer. Au début de la recherche
Etc. sera Aucun.
"""
self.location: Location = location
self.parent: Optional[Node] = parent
def get_path_from_goal_node(goal_node: Node) -> List[Location]:
"""
Depuis le nœud de sortie, le chemin depuis l'entrée obtenu en recherchant jusqu'à la sortie
avoir.
Parameters
----------
goal_node : Node
Une instance du nœud de sortie cible (objectif).
Returns
-------
path : list of Location
Une liste contenant des instances de chaque emplacement de l'entrée à la sortie.
"""
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
Si vous essayez de sortir le labyrinthe généré comme un essai, il sera affiché dans une grille comme indiqué ci-dessous.
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|
L'algorithme A \ * utilise une file d'attente prioritaire comme structure de données. Il s'agit d'une file d'attente spéciale dans laquelle les valeurs sont ajoutées à la file d'attente avec priorité et lors de la récupération de la valeur, la valeur avec la priorité la plus élevée est également ciblée.
Vous devez ajouter la méthode __lt__ à la classe Node car la valeur de priorité est calculée par l'opérateur de comparaison inférieur à (<) pour l'instance du nœud que vous souhaitez ajouter à la file d'attente.
Dans la méthode __lt__, $ g (n) + h (n) $ est calculé dans la formule de coût et comparé à un autre nœud.
Ajustez également la valeur de $ g (n) $ et la valeur de $ h (n) $ afin qu'elles soient incluses dans les attributs de classe car elles sont requises pour le calcul.
class Node:
def __init__(
self, location: Location, parent: Optional[Node],
cost: float, heuristic:float) -> None:
"""
Données pour un seul nœud pour contenir des informations telles que la position et la transition du labyrinthe
Classe à gérer.
Parameters
----------
location : Location
Une instance qui gère les informations de localisation de la cible.
parent : Node or None
Une instance d'un nœud qui gère les informations de position avant de se déplacer. Au début de la recherche
Etc. sera Aucun.
cost : float
Valeur de coût de la position de départ à la position du nœud correspondant (g(n)alors
Valeur obtenue).
heuristic : float
Distance estimée de ce nœud à la sortie (h(n)Valeur obtenue par).
"""
self.location: Location = location
self.parent: Optional[Node] = parent
self.cost = cost
self.heuristic = heuristic
def __lt__(self, other_node: Node) -> bool:
"""
Opérateur de comparaison( < )Méthode de traitement par.
Utilisé pour contrôler les files d'attente prioritaires.
Parameters
----------
other_node : Node
Instances d'autres nœuds à comparer.
Returns
-------
result_bool : bool
Résultat de la comparaison. Le traitement du calcul est le coût de l'entrée (g(n))Quand
Valeur hulistique (h(n)) En comparant la valeur totale
Sera fait.
"""
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
Je n'ai jamais utilisé la méthode __lt__ seule, je vais donc essayer de créer plusieurs instances et de les comparer pour voir les résultats. La comparaison est basée sur la somme du coût et de l'heuristique, donc la première comparaison est False et la seconde est True.
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
Ensuite, nous préparerons la file d'attente prioritaire. Le traitement de la file d'attente prioritaire peut être géré à l'aide du package heapq du module standard Python.
import heapq
...
class PriorityQueue:
def __init__(self) -> None:
"""
Une classe pour contrôler les files d'attente prioritaires.
"""
self._container: List[Node] = []
@property
def empty(self) -> bool:
"""
Valeur d'attribut indiquant si la file d'attente est vide.
Returns
-------
result : bool
Défini sur True si vide.
"""
return not self._container
def push(self, node: Node) -> None:
"""
Ajoutez une instance du nœud à la file d'attente.
Parameters
----------
node : Node
Instance du nœud à ajouter.
"""
heapq.heappush(self._container, node)
def pop(self) -> Node:
"""
Extrayez l'instance du nœud de priorité la plus élevée de la file d'attente.
Returns
-------
node : Node
Une instance de la classe Node récupérée.
"""
return heapq.heappop(self._container)
Déplaçons-le un peu et essayons-le pour voir s'il est traité d'une manière qui prend en compte la priorité. Il convient de noter que la forme «faible coût est préférable (= priorité élevée)». Il n'est pas retiré par pop de celui avec la valeur de coût totale la plus élevée.
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)
Vous pouvez voir que les résultats de sortie sont récupérés dans l'ordre croissant du coût total.
1 1
2 3
3 3
Puisque le calcul de l'heuristique ($ h (n) $) est cette fois un labyrinthe au format grille, la distance Manhattan est utilisée, alors ajoutez cette fonction à la classe Maze.
def get_manhattan_distance(self, location: Location) -> int:
"""
La distance de Manhattan entre la position cible et la position de sortie (objectif)
avoir.
Parameters
----------
location : Location
Une instance de l'emplacement cible.
Returns
-------
distance : int
Distance de Manhattan entre la position cible et la position de sortie. Direction de la colonne
La somme de la valeur absolue de la différence et de la valeur absolue de la différence dans le sens des lignes est définie.
"""
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
Maintenant que nous avons toutes les préparations nécessaires, créons une fonction pour l'algorithme A \ *. Le nom de la fonction est 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*Effectuer le traitement de la recherche par algorithme.
Parameters
----------
init_loc : Location
Recherche de la position de départ (position de l'entrée du labyrinthe).
is_goal_loc_method : callable
Une méthode qui détermine si la position cible est la sortie (objectif).
get_movable_locations_method : callable
Une méthode pour obtenir une liste de positions de cellule à déplacer de la position cible.
hueristic_method : callable
Obtenez la distance entre la position cible et la position de sortie (objectif)
Une méthode d'heuristique pour.
Returns
-------
goal_node : Node or None
Une instance du nœud à l'emplacement de sortie calculé. Vers la sortie
Aucun n'est défini dans les cas où l'itinéraire ne peut pas être calculé.
"""
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
#Une nouvelle destination a déjà été recherchée et ce n'est pas rentable
#Si tel est le cas, ignorez-le.
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
J'ai écrit plus tôt, "Ecrire une recherche de priorité en profondeur en Python. », le flux est similaire à la fonction dfs dans l'article. Le traitement étant partiellement différent, je vais principalement expliquer la différence.
Tout d'abord, comme pour l'argument, le Callable (hueristic_method) pour l'heuristique est ajouté. Cela spécifie la méthode de calcul de la distance de Manhattan qui a été ajoutée il y a quelque temps dans cet exemple.
frontier_queue: PriorityQueue = PriorityQueue()
frontier_queue.push(
node=Node(
location=init_loc,
parent=None,
cost=0,
heuristic=hueristic_method(init_loc)))
De plus, la file d'attente a été remplacée par celle de la file d'attente prioritaire (frontier_queue). Nous ajoutons des nœuds à explorer à cette file d'attente.
explored_loc_cost_dict: Dict[Location, float] = {init_loc: 0.0}
Le dictionnaire qui contient les nœuds recherchés se présente sous la forme de maintien de la position dans la clé et de la valeur du coût ($ g (n) $) dans la valeur. Comme il s'agit d'une méthode simple qui s'incrémente de 1 à chaque fois que vous vous déplacez, définissez d'abord 0,0.
while not frontier_queue.empty:
current_node: Node = frontier_queue.pop()
current_loc: Location = current_node.location
Le processus est répété dans une boucle while jusqu'à ce que le nœud à rechercher disparaisse de la file d'attente.
if is_goal_loc_method(current_loc):
return current_node
Si le nœud cible est une sortie (objectif), le processus est terminé en renvoyant le nœud de sortie.
movable_locations = get_movable_locations_method(current_loc)
for movable_location in movable_locations:
new_cost: float = current_node.cost + 1
Chaque position à déplacer du nœud cible de recherche actuel est traitée par une boucle for. Cette fois, il est implémenté sous une forme simple qui incrémente le coût ($ g (n) $) de 1 à chaque déplacement.
#Une nouvelle destination a déjà été recherchée et ce n'est pas rentable
#Si tel est le cas, ignorez-le.
if (movable_location in explored_loc_cost_dict and
explored_loc_cost_dict[movable_location] <= new_cost):
continue
Même si l'emplacement a déjà été recherché, il vaut la peine de chercher s'il est rentable. S'il a déjà été recherché et que la position ne change pas ou se détériore en termes de coût, il n'y a aucun intérêt à rechercher, alors sautez-la.
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)))
Si les conditions valent la peine d'être recherchées, nous définissons des valeurs telles que le coût dans le dictionnaire recherché et ajoutons des nœuds à la file d'attente prioritaire à rechercher.
Étant donné que les éléments avec la priorité la plus élevée sont traités en premier, vous pouvez effectuer une recherche avec un excellent coût de recherche.
return None
En fonction du labyrinthe généré, il se peut qu'il n'y ait pas de route vers la sortie, donc dans ce cas Aucun n'est retourné.
Je vais essayer.
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('C'est un labyrinthe où la sortie ne peut être calculée.')
else:
print('-' * 20)
path: List[Location] = get_path_from_goal_node(
goal_node=goal_node)
maze.set_path_type_to_cells(path=path)
print('Chemin calculé:')
print(maze)
Chemin calculé:
------------------------------
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 sur la grille est l'entrée (début), G est la sortie (but) et la partie astérisque est le chemin calculé par la recherche. Le chemin de l'entrée à la sortie a été calculé en toute sécurité.
C'est une caractéristique de A \ * qu'un chemin diagonal est obtenu par rapport à la recherche de priorité de largeur où le résultat de la recherche est légèrement à angle droit. Même l'échantillon que j'ai essayé cette fois-ci a un chemin légèrement diagonal.
from __future__ import annotations
from typing import Optional
from typing import List
import random
import heapq
from typing import Callable, Dict
#Valeur constante pour l'entrée.
CELL_TYPE_START: str = 'S'
#Valeur constante pour les passages.
CELL_TYPE_PASSAGE: str = ' '
#La valeur constante du mur.
CELL_TYPE_WALL: str = 'W'
#Quitter la valeur constante.
CELL_TYPE_GOAL: str = 'G'
#Une valeur constante pour le chemin d'itinéraire calculé.
CELL_TYPE_PATH: str = '*'
class Location:
def __init__(self, row: int, column: int) -> None:
"""
Une classe qui gère une seule information de position de la grille du labyrinthe.
Parameters
----------
row : int
Le numéro de ligne de la position. Commencez par 0, 1 de haut en bas
Sera ajouté.
column : int
Le numéro de colonne de la position. Partir de 0, 1 de gauche à droite
Sera ajouté.
"""
self.row: int = row
self.column: int = column
class Maze:
#Le nombre vertical de grilles de labyrinthe à générer.
_ROW_NUM: int = 7
#Le numéro à côté de la grille du labyrinthe à générer.
_COLUMN_NUM: int = 15
#Pourcentage de murs à générer. 1.Plus il est proche de 0, plus il y a de murs.
_WALL_SPARSENESS: float = 0.3
def __init__(self) -> None:
"""
Une classe qui gère la génération et le contrôle d'une grille de labyrinthe aléatoire.
Notes
-----
Étant donné que chaque type de cellule est défini au hasard, ce n'est pas toujours depuis le début
Notez que vous ne pouvez rien faire qui puisse atteindre votre objectif.
"""
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:
"""
Définissez les attributs des coordonnées du point de départ (entrée) et de l'objectif (sortie).
"""
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:
"""
Ajoutez des cellules à toutes les cellules et définissez le type de cellule du passage.
"""
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:
"""
Définissez de manière aléatoire le type de cellule de paroi pour chaque cellule de la grille.
"""
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:
"""
Aux positions de départ (entrée) et de but (sortie), respectivement
Définissez le type de cellule.
"""
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:
"""
Obtient la valeur booléenne indiquant si la position spécifiée est la position cible.
Parameters
----------
location : Location
Position pour le jugement.
Returns
-------
result : bool
True est défini s'il s'agit de la position cible.
"""
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]:
"""
Obtenez une liste des positions mobiles à partir de la position spécifiée.
Parameters
----------
location : Location
Une instance de la position de référence.
Returns
-------
movable_locations : list of Location
Une liste contenant des instances d'emplacements mobiles.
"""
movable_locations: List[Location] = []
#Traitement du jugement pour savoir s'il peut ou non être déplacé vers le haut.
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))
#Traitement du jugement pour savoir s'il peut être déplacé vers le bas.
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))
#Traitement du jugement pour savoir s'il peut être déplacé vers la droite.
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))
#Traitement du jugement pour savoir s'il peut être déplacé vers la gauche.
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:
"""
Pour les cellules contenues dans le chemin spécifié vers l'entrée et la sortie
Définissez le type de cellule du chemin.
Parameters
----------
path : list of Location
Les informations de position de chaque cellule de l'entrée à la sortie obtenues par la recherche
Liste stockée.
"""
for location in path:
self._grid[location.row][location.column] = CELL_TYPE_PATH
#Les pièces d'entrée et de sortie incluses dans le chemin sont d'origine
#Reflétez le type de cellule.
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:
"""
La distance de Manhattan entre la position cible et la position de sortie (objectif)
avoir.
Parameters
----------
location : Location
Une instance de l'emplacement cible.
Returns
-------
distance : int
Distance de Manhattan entre la position cible et la position de sortie. Direction de la colonne
La somme de la valeur absolue de la différence et de la valeur absolue de la différence dans le sens des lignes est définie.
"""
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:
"""
Obtient la chaîne de type pour chaque cellule de la grille.
Returns
-------
grid_str : str
Une chaîne de types pour chaque cellule de la grille.
"""
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:
"""
Données pour un seul nœud pour contenir des informations telles que la position et la transition du labyrinthe
Classe à gérer.
Parameters
----------
location : Location
Une instance qui gère les informations de localisation de la cible.
parent : Node or None
Une instance d'un nœud qui gère les informations de position avant de se déplacer. Au début de la recherche
Etc. sera Aucun.
cost : float
Valeur de coût de la position de départ à la position du nœud correspondant (g(n)alors
Valeur obtenue).
heuristic : float
Distance estimée de ce nœud à la sortie (h(n)Valeur obtenue par).
"""
self.location: Location = location
self.parent: Optional[Node] = parent
self.cost = cost
self.heuristic = heuristic
def __lt__(self, other_node: Node) -> bool:
"""
Opérateur de comparaison( < )Méthode de traitement par.
Utilisé pour contrôler les files d'attente prioritaires.
Parameters
----------
other_node : Node
Instances d'autres nœuds à comparer.
Returns
-------
result_bool : bool
Résultat de la comparaison. Le traitement du calcul est le coût de l'entrée (g(n))Quand
Valeur hulistique (h(n)) En comparant la valeur totale
Sera fait.
"""
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]:
"""
Depuis le nœud de sortie, le chemin depuis l'entrée obtenu en recherchant jusqu'à la sortie
avoir.
Parameters
----------
goal_node : Node
Une instance du nœud de sortie cible (objectif).
Returns
-------
path : list of Location
Une liste contenant des instances de chaque emplacement de l'entrée à la sortie.
"""
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:
"""
Une classe pour contrôler les files d'attente prioritaires.
"""
self._container: List[Node] = []
@property
def empty(self) -> bool:
"""
Valeur d'attribut indiquant si la file d'attente est vide.
Returns
-------
result : bool
Défini sur True si vide.
"""
return not self._container
def push(self, node: Node) -> None:
"""
Ajoutez une instance du nœud à la file d'attente.
Parameters
----------
node : Node
Instance du nœud à ajouter.
"""
heapq.heappush(self._container, node)
def pop(self) -> Node:
"""
Extrayez l'instance du nœud de priorité la plus élevée de la file d'attente.
Returns
-------
node : Node
Une instance de la classe Node récupérée.
"""
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*Effectuer le traitement de la recherche par algorithme.
Parameters
----------
init_loc : Location
Recherche de la position de départ (position de l'entrée du labyrinthe).
is_goal_loc_method : callable
Une méthode qui détermine si la position cible est la sortie (objectif).
get_movable_locations_method : callable
Une méthode pour obtenir une liste de positions de cellule à déplacer de la position cible.
hueristic_method : callable
Obtenez la distance entre la position cible et la position de sortie (objectif)
Une méthode d'heuristique pour.
Returns
-------
goal_node : Node or None
Une instance du nœud à l'emplacement de sortie calculé. Vers la sortie
Aucun n'est défini dans les cas où l'itinéraire ne peut pas être calculé.
"""
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
#Une nouvelle destination a déjà été recherchée et ce n'est pas rentable
#Si tel est le cas, ignorez-le.
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('C'est un labyrinthe où la sortie ne peut être calculée.')
else:
print('-' * 20)
path: List[Location] = get_path_from_goal_node(
goal_node=goal_node)
maze.set_path_type_to_cells(path=path)
print('Chemin calculé:')
print(maze)
――Depuis que j'étais à l'origine diplômé d'une école dans le domaine du design, veuillez pardonner à Masakari qui a de solides connaissances dans le domaine de l'informatique.
Recommended Posts