Pensez aux recherches de priorité de profondeur et de priorité de largeur en Python

Bonjour: souriant: Cette fois, nous considérerons la recherche de priorité de profondeur et la recherche de priorité de largeur à l'aide d'un labyrinthe. Le labyrinthe utilisé cette fois: arrow_down: 2020-05-25_16h23_17.png

contribution

La saisie se fait sur n lignes.

n-2 est la longueur verticale du labyrinthe, et # est donné là où il n'y a pas d'espace. ex.)

S G
3 5
# B E F G
S A C H #
# D # # #

production

La sortie est de 3 lignes. La première ligne est la distance entre le point de départ et le point de but La deuxième ligne est le nombre de recherches La troisième ligne est l'itinéraire du point de départ au point de but ex.)

Distance entre les points de départ et d'arrivée: 5
Nombre de recherches: 10
Itinéraire: G<= F <= H <= C <= A <= S

Recherche de priorité de profondeur

Flux de code

  1. Lisez les informations d'entrée
  2. Ajouter Start à diverses listes
  3. Retirer de la pile
  4. Jugement d'objectif
  5. Ajoutez des points adjacents à la pile
  6. Ajouter à la liste vérifiée et revenir à 3

la mise en oeuvre

stack


# cording = utf-8
start, goal = input().split()  #Point de départ et point de but
height, width = map(int, input().split())  #Longueur et largeur du labyrinthe
maze, stack, checked, route = [], [], [], {}
num_of_t = 0  #Nombre de recherches
for i in range(height):
    x = input().split()
    maze.append(x) #Labyrinthe
    if start in maze[i]:
        now_height, now_width = i, maze[i].index(start)
start_height, start_width = now_height, now_width #Enregistrer les coordonnées du point de départ
stack += start
checked += start
route[maze[now_height][now_width]] = "Start"


def search(h, w, x = maze, y = stack, z = checked):
    if x[h][w] != "#" and x[h][w] not in z:
        y += x[h][w]
        z += x[h][w]


while stack[-1] != goal:
    stack.pop()
    if now_height < height-1:
        search(now_height+1, now_width)
    if now_width < width-1:
        search(now_height, now_width+1)
    if now_height > 0:
        search(now_height-1, now_width)
    if now_width > 0:
        search(now_height, now_width-1)
    num_of_t += 1
    for j in range(height):
        if stack[-1] in maze[j]:
            route[stack[-1]] = maze[now_height][now_width]
            now_height, now_width = j, maze[j].index(stack[-1])
print("Distance entre les points de départ et d'arrivée:" + str(abs(now_height - start_height) + abs(now_width - start_width)))
print("Nombre de recherches:" + str(num_of_t))
print("racine:", end = "")
while route[goal] != "Start":
    print(goal + " <= ", end="")
    goal = route[goal]
print(goal)

Résultat de sortie

Distance entre les points de départ et d'arrivée: 5
Nombre de recherches: 5
Itinéraire: G<= F <= E <= B <= A <= S

Recherche de priorité de largeur

Flux de code

Changer la pile de recherche de priorité de profondeur en file d'attente

la mise en oeuvre

queue


# cording = utf-8
start, goal = input().split() #Entrez le point de départ et le point objectif
height, width = map(int, input().split()) #Longueur verticale et horizontale du labyrinthe
maze, queue, checked, route = [], [], [], {}
num_of_t = 0 #Nombre de recherches
for i in range(height):
    x = input().split()
    maze.append(x)  #Labyrinthe
    if "A" in maze[i]:
        now_height, now_width = i, maze[i].index(start)
start_height, start_width = now_height, now_width #Enregistrer les coordonnées du point de départ
queue += start
checked += start
route[maze[now_height][now_width]] = "Start"


def search(h, w, x = maze, y = queue, z = checked):
    if x[h][w] != "#" and x[h][w] not in z:
        y += x[h][w]
        z += x[h][w]


while queue[0] != goal:
    place = queue.pop(0)
    tmp = len(queue)
    if now_height < height-1:
        search(now_height+1, now_width)
    if now_width < width-1:
        search(now_height, now_width+1)
    if now_height > 0:
        search(now_height-1, now_width)
    if now_width > 0:
        search(now_height, now_width-1)
    num_of_t += 1
    if tmp < len(queue):
        for i in range(1, len(queue) - tmp+1):
            route[queue[-i]] = place
    for j in range(height):
        if queue[0] in maze[j]:
            now_height, now_width = j, maze[j].index(queue[0])
print("Distance entre les points de départ et d'arrivée:" + str(abs(now_height - start_height) + abs(now_width - start_width)))
print("Nombre de recherches:" + str(num_of_t))
print("racine:", end = "")
while route[goal] != "Start":
    print(goal + " <= ", end="")
    goal = route[goal]
print(goal)

Résultat de sortie

Distance entre les points de départ et d'arrivée: 5
Nombre de recherches: 8
Itinéraire: G<= F <= H <= C <= A <= S

Considération

Les connaissances sur l'algorithme ont été suffisamment approfondies. Certaines personnes peuvent être capables de l'écrire plus court, mais pour le moment, je suis comme ça.

Recommended Posts

Pensez aux recherches de priorité de profondeur et de priorité de largeur en Python
À propos de la différence entre "==" et "is" en python
Pensez à créer un environnement Python 3 dans un environnement Mac
À propos de __all__ en python
À propos des objets et des classes Python
À propos des variables et des objets Python
À propos de Python, len () et randint ()
À propos de la date et du fuseau horaire Python
Pile et file d'attente en Python
À propos de Python et des expressions régulières
Unittest et CI en Python
À propos de "for _ in range ():" de python
À propos des opérations Python et OS
Python # À propos de la référence et de la copie
À propos de Python sort () et reverse ()
Différence entre list () et [] en Python
À propos de l'installation des séries Pwntools et Python2
Ce que les débutants pensent de la programmation en 2016
Différence entre == et est en python
Manipuler des fichiers et des dossiers en Python
À propos de Python dict et des fonctions triées
Affectations et modifications des objets Python
[Python] À propos des classes Executor et Future
À propos de Python, à partir et à l'importation, comme
Vérifiez et déplacez le répertoire en Python
Chiffrement avec Python: IND-CCA2 et RSA-OAEP
Hashing de données en R et Python
J'ai essayé d'étudier le processus avec Python
Synthèse de fonctions et application en Python
Exporter et exporter des fichiers en Python
Inverser le pseudonyme plat et le katakana en Python2.7
Lire et écrire du texte en Python
[GUI en Python] Menu PyQt5 et barre d'outils-
Créer et lire des paquets de messages en Python
Réfléchissez sérieusement au langage à utiliser dans l'enseignement de la programmation et l'enseignement de la programmation.
Chevauchement d'expressions régulières en Python et Java
Différence d'authenticité entre Python et JavaScript
Notes utilisant cChardet et python3-chardet dans Python 3.3.1.
Les modules et packages en Python sont des "espaces de noms"
Évitez les boucles imbriquées en PHP et Python
Différences entre Ruby et Python dans la portée
Modulation et démodulation AM avec Python Partie 2
différence entre les instructions (instructions) et les expressions (expressions) en Python
Valeurs authentiques et vecteurs propres: Algèbre linéaire en Python <7>
[Python] Doux Est-ce doux? À propos des suites et des expressions dans les documents officiels
Module d'implémentation de file d'attente et Python "deque"
Graphique à lignes pliées et ligne d'échelle en python
Vulkan compute avec Python avec VkInline et pense à l'apprentissage automatique GPU et plus
Implémenter le filtre FIR en langage Python et C
Différences entre la syntaxe Python et Java
Vérifier et recevoir le port série en Python (vérification du port)
Rechercher et lire des vidéos YouTube avec Python
Différence entre append et + = dans la liste Python
Différence entre non local et global en Python
Ecrire le fichier O_SYNC en C et Python
Gérer les "années et mois" en Python
Lire et écrire des fichiers JSON avec Python
Représentez facilement des données graphiques dans le shell et Python
Méthodes et champs privés en python [chiffrement]
Rechercher et vérifier la matrice inverse en Python