[Python] Recherche de priorité de profondeur et recherche de priorité de largeur

J'ai appris (en quelque sorte) la différence entre les deux que je ne comprenais pas en étudiant l'algorithme, alors j'ai décidé de l'expliquer. Cette fois, nous utiliserons des méthodes qui utilisent des structures de données appelées respectivement piles et files d'attente. Il ne gère pas la récurrence.

Qu'est-ce que la recherche de priorité en profondeur?

La recherche avec priorité à la profondeur (Fukasa Yusentansaku, anglais: recherche en profondeur d'abord, DFS, également connue sous le nom de méthode de retour arrière) est un algorithme de recherche d'arbres et de graphiques. L'algorithme commence à la racine (dans le cas d'un graphe, détermine quel nœud racine) et recherche autant que possible jusqu'à ce qu'il revienne en arrière. Aussi appelé "recherche verticale". [De Wikipedia](https://ja.wikipedia.org/wiki/%E6%B7%B1%E3%81%95%E5%84%AA%E5%85%88%E6%8E%A2%E7% B4% A2)

image Nous prioriserons la recherche depuis la partie profonde du labyrinthe, et lorsque nous atteindrons une impasse, nous reviendrons et essayerons d'aller dans un endroit que nous n'avons pas encore visité.

Qu'est-ce que la recherche de priorité de largeur?

La recherche de priorité de largeur (Habayu Sentansaku, anglais: première recherche en largeur) est un algorithme utilisé pour rechercher des structures arborescentes et des graphiques dans la théorie des graphes. L'algorithme commence par le nœud racine et recherche tous les nœuds adjacents. Ensuite, la même chose est répétée pour chacun de ces nœuds les plus proches pour trouver le nœud à rechercher. Également appelée «recherche horizontale». La recherche de priorité de largeur se développe et inspecte de manière exhaustive tous les nœuds du graphique afin de trouver une solution. Contrairement à la recherche de la meilleure priorité, il n'utilise pas l'héristique pour la recherche de nœuds et recherche le graphe entier sans se demander s'il est proche du nœud cible jusqu'à ce que le nœud cible soit trouvé. De Wikipedia

image Après avoir tout exploré à côté de là où vous êtes, passez au suivant. Vous donnez la priorité à la largeur par rapport à la profondeur.

DFS (recherche de priorité de profondeur) utilisant la structure de la pile

Qu'est-ce que la pile

Dernier entré premier sorti LIFO (dernier entré, premier sorti) L'image d'empiler des livres et de les prendre dans l'ordre du haut. (Le livre qui a été placé plus tard est retiré en premier.)

D'après l'exemple ATC001 A Énoncé du problème La ville où vit Takahashi a une forme rectangulaire et est divisée en sections en forme de grille. Chaque côté du rectangle est parallèle à l'est-ouest et au nord-sud. Chaque section est soit une route, soit un mur, et Takahashi peut déplacer la route vers le nord, le sud, l'est et l'ouest, mais pas en diagonale. De plus, la section de clôture ne peut pas être dépassée. Déterminez si Takahashi peut atteindre la poissonnerie par la route sans casser la clôture.

#===Entrée standard et organisation des données utilisées===#
h, w = map(int, input().split())
sx, sy, gx, gy = None, None, None, None
town = []
edge = ['#'] * (w+2) #Entourez le haut et le bas d'un mur
for i in range(h):
    line = list(input())
    line = ['#'] + line + ['#'] #Entourez la gauche et la droite d'un mur
    for j in range(w+2):
        if line[j] == 's':
            sx, sy = j, i+1 #Coordonnées de départ
    for j in range(w+2):
        if line[j] == 'g':
            gx, gy = j, i+1 #Coordonnées de l'objectif
    town.append(line)
town = [edge] + town + [edge] #Plan de la ville dans cette affaire
visited = [[False]*(w+2) for _ in range(h+2)] #Enregistrez où vous avez visité la ville

#===Recherche de priorité de profondeur lancée===#
stack = [[sx, sy]] #Mettez les coordonnées du point de départ dans la pile
visited[sy][sx] = True #Le point de départ"A visité"À
while stack: #Tant qu'il y a du contenu dans la pile
    x, y = stack.pop()
    if town[y][x] == 'g':
        print('Yes')
        exit() #Si votre emplacement actuel est l'objectif'Yes'Est sortie pour terminer l'exécution
    hjkl = [[x-1, y], [x, y-1], [x+1, y], [x, y+1]] #Prochain endroit à visiter: en haut à gauche, en bas à droite
    for dx, dy in hjkl:
        if (dx<1) or (dx>w+1) or (dy<1) or (dy>h+1) or town[dy][dx] == '#' or visited[dy][dx] is True:
            #Sautez si la direction du voyage est un mur, en dehors de la plage de la ville ou si vous avez déjà visité
            continue
        #Sinon, placez le sens de déplacement sur une nouvelle pile et marquez-la comme visitée.
        stack.append([dx, dy])
        visited[dy][dx] = True

print('No') #Quand tu ne peux pas atteindre'No'Production

BFS (recherche de priorité de largeur) utilisant la structure de file d'attente

Qu'est-ce que la file d'attente

Premier entré, premier sorti FIFO (premier entré, premier sorti) Image que les personnes alignées à la caisse enregistreuse sont traitées à partir de la personne alignée en premier (premier entré, premier sorti)

D'après l'exemple ABC007 C Énoncé du problème Takahashi aime les labyrinthes. J'essaie de résoudre un labyrinthe sur une planche à deux dimensions qui peut se déplacer vers le haut, le bas, la gauche et la droite. Tout d'abord, la taille de la planche et les coordonnées des points de départ et d'arrivée du labyrinthe sont données. Ensuite, un tableau indiquant si chaque cellule est une cellule vide praticable (.) Ou une cellule de paroi infranchissable (#) est donné. Le plateau est entouré de carrés muraux. Le point de départ et le point de but sont toujours des carrés vides, et vous pouvez toujours atteindre le point de but en suivant les carrés vides. Plus précisément, il est conseillé de se référer à un exemple d'entrée / sortie. Maintenant, il veut trouver le nombre minimum de mouvements requis pour résoudre le labyrinthe ci-dessus. Lorsque j'étudiais comment le trouver, j'ai trouvé qu'une méthode appelée "recherche de priorité de largeur" était efficace. (Partiellement omis)

#===Entrée standard et organisation des données utilisées===#
r, c = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
sx, sy, gx, gy = [i-1 for i in [sx, sy, gx, gy]] #Corriger les coordonnées à indexer
maiz = []
for _ in range(r):
    line = list(input())
    maiz.append(line)

#===Recherche de priorité de largeur lancée===#
queue = [[sx, sy]] #Mettre en file d'attente le point de départ
maiz[sy][sx] = 0 #Partir de 0 pas
visited = [[False]*c for _ in range(r)] #Notez si vous avez visité
while queue:
    x, y = queue.pop(0)
    visited[y][x] = True #Faites-le visiter
    hjkl = [[x-1, y], [x, y-1], [x+1, y], [x, y+1]] #Prochain endroit à visiter: en haut à gauche, en bas à droite
    for dx, dy in hjkl:
        if (maiz[dy][dx] == '.') and (visited[dy][dx] is False):
            #Si vous pouvez continuer et que vous n'avez pas encore visité, faites la queue et enregistrez l'effort
            queue.append([dx, dy])
            maiz[dy][dx] = maiz[y][x]+1

print(maiz[gy][gx]) #Se référer au nombre de pas enregistrés au point de but

Question: à propos de l'ordre de la direction diagonale de la direction de déplacement

Ordre du sens de marche

Il y a un total de 24 ordres différents dans 4 directions, mais l'ordre des directions de voyage est probablement n'importe quoi. (S'il vous plaît laissez-moi savoir s'il existe un modèle qui ne fonctionne pas si vous procédez dans cet ordre.)

Direction diagonale

Je procéderai. Selon le problème, il y a une condition que vous pouvez procéder en diagonale, alors soyez flexible. AOJ 1160 Combien d'îles y a-t-il?