[GO] 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:

contribution

La saisie se fait sur n lignes.

• La première ligne correspond aux points de départ et d'arrivée du labyrinthe ――La deuxième ligne est la longueur verticale et horizontale du labyrinthe
• Les lignes 3 à n sont des informations de labyrinthe

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.