Trouver le diamètre du graphique par recherche de priorité de largeur (mémoire Python)
Je me suis enregistré avec Qiita, mais je ne l'ai pas tellement utilisé, alors je vais l'essayer.
Objectif de cet article
・ Mémo personnel ・ J'ai déjà cherché un article sur la recherche de priorité de largeur Python, mais je ne l'ai pas trouvé, alors j'aimerais le publier pour des débutants similaires. ・ Quelqu'un peut vous dire comment mieux écrire si vous écrivez ici
Conclusion
-Le diamètre d'un graphe qui est connecté et qui n'a pas de longueur de côté peut être obtenu par la recherche de priorité de largeur (BFS). -L'opération pour récupérer l'élément du haut de la liste est lente ・ Cependant, l'utilisation de deque l'améliorera un peu.
Problème à résoudre et politique de réponse
problème
ABC151 D - Maze Master
Résolvez ceci. (La question D d'ABC reçoit parfois une question graphique.) Veuillez vérifier l'énoncé du problème sur le lien.
Politique de réponse
Interprétez-le comme un problème de graphique. Le labyrinthe est représenté par un graphe connecté en connectant les sommets adjacents en haut, en bas, à gauche et à droite avec la masse en tant que sommet. Par conséquent, ce problème peut être considéré comme «le problème de trouver le diamètre d'un graphe qui est connecté et qui n'a pas de longueur de côté». Ici, le diamètre est la valeur maximale de la distance entre les sommets.
Qu'est-ce que la recherche de priorité de largeur (BFS)?
Pour plus de détails, consultez d'autres articles, mais la recherche de priorité de largeur est un algorithme permettant de trouver un emplacement accessible à partir d'un certain sommet (appelons-le start).
Cette fois, je vais appliquer cela ** Trouvez la distance maximale depuis le départ **. Tout d'abord, préparez une liste d'arêtes qui se connectent à chaque sommet, puis entrez la distance depuis le début dans la liste préparée (distance) conformément à l'organigramme suivant.
Si vous remplacez la partie «depuis le début» écrite en rouge dans cet organigramme par «depuis la fin», elle devient une recherche prioritaire en profondeur (DFS). Cependant, le diamètre du graphique n'est pas calculé par DFS.
La recherche avec priorité à la largeur ne provoque pas de détour car elle se déplace immédiatement vers les sommets accessibles. Par conséquent, la distance la plus courte peut être obtenue. Bien sûr, à moins que les côtés aient de la longueur.
Enfin, faites cela pour tous les sommets du graphe et imprimez la plus grande des valeurs obtenues pour terminer.
H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]
edge=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
for w in range(W):
if maze[h][w]=='#':
numcount+=1
n+=1
continue
if h>0 and maze[h-1][w]=='.':
edge[n].add(n-W)
if h<H-1 and maze[h+1][w]=='.':
edge[n].add(n+W)
if w>0 and maze[h][w-1]=='.':
edge[n].add(n-1)
if w<W-1 and maze[h][w+1]=='.':
edge[n].add(n+1)
n+=1
def dfs(start):
reach=[start]
distance=[-1 for _ in range(H*W)]
distance[n]=0
while reach:
_from=reach.pop(0)
for _to in edge[_from]:
if not(_to in reach) and distance[_to]==-1:
reach.append(_to)
distance[_to]=distance[_from]+1
return(max(distance))
n=0
ans=set()
for h in range(H):
for w in range(W):
if maze[h][w]=='.':
ans.add(dfs(n))
n+=1
print(max(ans))
Vous pouvez maintenant AC.
Atteindre le haut de la liste est lent
En gros, c'est bien, mais ... python est assez lent et deviendra rapidement TLE si vous ne faites pas attention. Il vaut mieux réduire au maximum les opérations chronophages. Par exemple, la récupération d'un élément du haut d'une liste est très lente.
import time
list_1=[i for i in range(100000)]
list_2=[i for i in range(100000)]
#Extraire les éléments du début
start_1=time.time()
while list_1:
x=list_1.pop(0)
end_1=time.time()
#Extraire les éléments de la fin
start_2=time.time()
while list_2:
x=list_2.pop(-1)
end_2=time.time()
print('Depuis le début:{}'.format(end_1-start_1))
#=>Depuis le début: 1.4942412376403809
print('À partir de la fin:{}'.format(end_2-start_2))
#=>À partir de la fin: 0.014818668365478516
Même si je fais la même opération, cela prend environ 100 fois plus de temps lorsque je retire l'élément depuis le début. C'était bien cette fois, mais je pense qu'il vaut mieux prendre des mesures lorsque de nombreuses opérations similaires se poursuivent.
utiliser deque
Lors de la récupération d'un élément du haut d'une liste, un type appelé deque est utile. Voir ici pour plus de détails. collections --- type de données de conteneur (documentation Python 3.7.3)
Grosso modo -Deque est rapide lors de l'extraction d'éléments depuis le début ou la fin d'un tableau ・ La liste est rapide lors de la sortie du centre Ça ressemble à ça.
import time
from collections import deque
list_1=[i for i in range(100000)]
deq=deque([i for i in range(100000)])
#Commencez par le début avec la liste
start_1=time.time()
while list_1:
x=list_1.pop(0)
end_1=time.time()
#Commencez par le début avec deque
start_3=time.time()
while deq:
x=deq.popleft()
end_3=time.time()
print('list：{}'.format(end_1-start_1))
#=>list：1.4939298629760742
print('deque：{}'.format(end_3-start_3))
#=>deque：0.009586334228515625
Cela s'est terminé très tôt. Le problème cette fois est que la longueur de la liste est d'environ 400, donc cela ne fait pas beaucoup de différence (plutôt lent), mais plus elle est longue, plus elle a de chances d'en bénéficier. La réponse en utilisant deque est la suivante.
from collections import deque
H,W=[int(s) for s in input().split()]
maze=[input() for _ in range(H)]
edge=[set() for _ in range(H*W)]
n=0
numcount=0
for h in range(H):
for w in range(W):
if maze[h][w]=='#':
numcount+=1
n+=1
continue
if h>0 and maze[h-1][w]=='.':
edge[n].add(n-W)
if h<H-1 and maze[h+1][w]=='.':
edge[n].add(n+W)
if w>0 and maze[h][w-1]=='.':
edge[n].add(n-1)
if w<W-1 and maze[h][w+1]=='.':
edge[n].add(n+1)
n+=1
def dfs(start):
reach=deque([start]) #Cette ligne change
distance=[-1 for _ in range(H*W)]
distance[n]=0
while reach:
_from=reach.popleft() #Cette ligne change
for _to in edge[_from]:
if not(_to in reach) and distance[_to]==-1:
reach.append(_to)
distance[_to]=distance[_from]+1
return(max(distance))
n=0
ans=set()
for h in range(H):
for w in range(W):
if maze[h][w]=='.':
ans.add(dfs(n))
n+=1
print(max(ans))
Résumé
Cette fois, j'ai découvert BFS. Pour être honnête, je n'avais pas réalisé que le diamètre était calculé par BFS avant de résoudre ce problème. J'aimerais essayer de résoudre d'autres problèmes de graphes et les poster quand j'en ai le temps.
Recommended Posts