J'ai essayé d'implémenter la recherche de priorité de largeur avec python (file d'attente, dessin personnalisé)

Scène où la recherche de priorité de largeur (BFS) est requise (préface)

J'ai rencontré un problème pour trouver la distance la plus courte entre deux points dans un graphique de structure arborescente avec Atcoder. À ce moment-là, j'ai créé l'algorithme moi-même, mais je ne pouvais pas résoudre le problème, j'ai donc décidé de créer correctement BFS. Lors de son utilisation, j'utiliserai une bibliothèque pratique Cette fois, je vais programmer et organiser l'idée de base. La réimplémentation à l'aide de la bibliothèque sera effectuée à une date ultérieure.

la mise en oeuvre

Puisque l'introduction est bonne, implémentez-la ci-dessous.

Définition de la classe de structure graphique

#Créer une structure graphique
class cglaph():
  def __init__(self):
    #Initialisation du nœud
    self.nodes={}

  def addnode(self,num):#① Ajouter un nœud
    for i in self.nodes.keys():
      if i==num:
        return(False)
    else:
      self.nodes[num]=list()
      return(True)

  def addedge(self,ag1,ag2):#② Ajouter un bord
    node1=min(ag1,ag2)
    node2=max(ag1,ag2)
    addok=False

    for i in self.nodes.keys():
      if i==node1:
        for j in self.nodes.keys():
          if j==node2:
            addok=True

    if addok:
      self.nodes[node1].append(node2)
      self.nodes[node2].append(node1)

  def printnodes(self):    #③ Afficher le nœud
    print("■Glaph:")
    print("vertice:neighbors")
    for k,v in self.nodes.items():
      print(k,":",v)


  def getnodes(self):#④ Renvoie une liste de nœuds
    keylist=list()

    for i in self.nodes.keys():
      keylist.append(i)
    return keylist

  def getedge(self, node):#⑤ Renvoie l'arête (nœud connecté) du nœud spécifié.
    return self.nodes[node]

Concept de cette classe de structure arborescente

Les informations de nœud sont stockées dans un type de dictionnaire. Stockez le numéro de nœud dans la clé et les nœuds connectés à ce nœud dans une liste dans la valeur. Insérez la méthode suivante. ① Ajouter un nœud ② Ajouter un bord ③ Affichage des nœuds (et des nœuds qui leur sont connectés) ④ Renvoie une liste de nœuds ⑤ Renvoie une liste de nœuds connectés au nœud spécifié

Définition de classe de structure de file d'attente

#Définition de la structure de la file d'attente
class cqu():
  def __init__(self):
    #Initialisation de la file d'attente
    self.qu=list()
    self.head=0
    self.tail=-1

  def quval(self):#① Taille de la queue
    return self.tail-self.head+1

  def printqu(self):#② Afficher le contenu de la file d'attente
    print(str(self.qu[self.head:self.tail+1])+",head:"+str(self.head)+",tail:"+str(self.tail))
    print(self.qu)

  def enqu(self,num):#③ Encu
    self.qu.append(num)
    self.tail+=1
 
  def dequ(self):#④ Decue
    if self.quval()!=0:
      outv=self.qu[self.head]
      self.head+=1
      return outv

    else:
      return False

Concept de classe de structure de file d'attente

La file d'attente a une structure de liste et des variables telles que des pointeurs indiquant le début et la fin. Ayez la méthode suivante. ① Renvoie la taille de la file d'attente ② Afficher le contenu de la file d'attente ③ Encu ④ Decue

Créer une arborescence

G=cglaph()

G.addnode(1)#Ajouter un nœud
G.addnode(2)
G.addnode(3)
G.addnode(4)
G.addnode(5)
G.addedge(1,2)#Ajouter un bord
G.addedge(2,3)
G.addedge(3,4)
G.addedge(4,5)
G.addedge(2,4)
G.printnodes()#Liste des nœuds

nodelist=G.getnodes()#Obtenir la liste des nœuds
print ("NODE LIST:",nodelist)

G.getedge(1)#Nœud connecté au nœud 1

L'image est le graphique ci-dessous cap1.PNG

Implémentation BFS


StartNode=1

#Graphique cible G
G.printnodes()

#Liste pour enregistrer la distance
NodeList=G.getnodes()
#print(NodeList)
DistList=[0]*len(NodeList)

#Génération de structure de file d'attente
Q=cqu()

#① Mettre en file d'attente le nœud de démarrage de la recherche
Q.enqu(StartNode)
#Q.printqu()

while Q.quval():#② Boucle jusqu'à ce que la taille de la file d'attente devienne 0
  #print("=====loop=====")
  #Q.printqu()
  #print("Qval"+str(Q.quval()))

  checknode=Q.dequ()#③ Decue
  #print("deQ:"+str(checknode))

  nextnodes=G.getedge(checknode)#④ Acquérir le nœud connecté au nœud acquis par mise en file d'attente
  #print("next nodes:"+str(nextnodes))

  for i in nextnodes:#⑤ Donnez la distance à chaque nœud connecté
    #print(i)
    if DistList[NodeList.index(i)]==0:#⑥ Jugez s'il a été fouillé (la distance a été donnée au nœud)
      if i!=StartNode:#⑦ Le nœud de démarrage de la recherche est hors de portée
        #print("enq")
        Q.enqu(i)#⑧ Mettre en file d'attente, donner la distance si elle n'est pas recherchée (la faire rechercher)
        DistList[NodeList.index(i)]=DistList[NodeList.index(checknode)]+1#⑨ Recherche Augmentez la distance du nœud d'origine de +1
    
    #print(DistList)

print("Liste des distances",DistList)

S'il s'agit d'une implémentation simple, il y en a beaucoup sur d'autres sites, j'ai donc laissé un commentaire pour le débogage que je crée.

L'algorithme consiste à retirer la file d'attente et à déterminer le nœud de départ. Mettez en file d'attente le nœud connecté au nœud de départ. répéter.

Dessiner des graphiques et des résultats de recherche

import matplotlib.pyplot as plt
import collections
import copy

#Dessiner un graphique en fonction de la distance de recherche
N=len(nodelist)
x=DistList#la coordonnée x est la distance
y=[0]*N#Pour la coordonnée Y, les nœuds avec la même coordonnée X sont disposés à intervalles égaux (les intervalles égaux sont calculés ci-dessous).===
c=collections.Counter(DistList)#Trouvez le nombre d'éléments qui se chevauchent.
tmp=c.most_common()

c2=collections.Counter(DistList)#Compteur de correction


tmpmean=copy.deepcopy(tmp)
for i in range(len(tmp)):
  tmpmean[i]=(c[i]-1)*0.5+1


for i,n in zip(DistList,range(N)):
  if c[i]!=1:#1 est y=0 ligne
    y[n]=-c2[i]+tmpmean[i]
    c2[i]-=1
#===Jusqu'à présent x,Je veux juste trouver la coordonnée y

print("x:",x)
print("y:",y)

#Création de graphes
plt.figure(1)

#Dessin de nœud
plt.scatter(x,y)

#Donnez un nom de nœud à la position du nœud
ax=plt.axes()
for i in range(N):
  ax.annotate(str(nodelist[i])+":"+str(DistList[i]),(x[i],y[i]),size=20)

#Dessiner des bords
for i in nodelist:
  edges=G.getedge(i)
  for j in edges:
    plt.plot((x[nodelist.index(i)],x[nodelist.index(j)]),(y[nodelist.index(i)],y[nodelist.index(j)]), color='red')


plt.xlim(-1, 5)
plt.ylim(-3, 3)

cap2.PNG

L'annotation attachée à chaque nœud est (numéro de nœud: distance du nœud de début de recherche).

Résumé, futurs numéros

-BFS lui-même peut être facilement implémenté en utilisant une structure de file d'attente. ・ Nous résumerons la mise en œuvre à l'aide de la bibliothèque en prévision de la pratique. -Si plusieurs nœuds avec la même distance (même hiérarchie) se succèdent, le graphique sera tordu. Examinez l'algorithme de dessin de graphique.

Les références

BFS (Width Priority Search) Super Introduction! ~ Utilisez la file d'attente de façon vivante ~

[Algorithme de dessin graphique et derrière Networkx] (https://qiita.com/odanny/items/7c550010f5915ae4acdc)

Créez votre propre classe de structure de graphique et son dessin avec python

Remarque sur le type de dictionnaire Python très utile

Comptez le nombre d'occurrences de chaque élément de la liste avec Python Counter

Recommended Posts

J'ai essayé d'implémenter la recherche de priorité de largeur avec python (file d'attente, dessin personnalisé)
Algorithme en Python (recherche de priorité de largeur, bfs)
J'ai écrit la file d'attente en Python
J'ai essayé d'implémenter la régression logistique de Cousera en Python
J'ai essayé d'implémenter le filtre anti-spam bayésien de Robinson avec python
J'ai essayé d'implémenter la fonction gamma inverse en python
Exercice Python Recherche prioritaire sur 1 largeur
Implémentation de SimRank en Python
Dichotomie avec Python
Dessin graphique avec python
Traitement des requêtes en Python
Recherche linéaire en Python
Recherche binaire en Python
Implémentation de Shiritori en Python
Implémenter la recherche de priorité en profondeur (DFS) et la recherche de priorité de largeur (BFS) en python
J'ai implémenté une commande de remplacement de type Vim dans Slackbot #Python
[Python] BFS (recherche de priorité de largeur) ABC168D
J'ai écrit python en japonais
Dessin de bougie avec python
Recherche de priorité de largeur / recherche bidirectionnelle (édition Python)
Recherche binaire en Python / C ++
Algorithme en Python (dichotomie)
Pile et file d'attente en Python
Implémentation de Supreme Solver dans Python 3
Je comprends Python en japonais!
[Python] Recherche de priorité de profondeur et recherche de priorité de largeur
Ce que j'ai appris en Python
J'ai essayé d'implémenter l'algorithme de calcul séquentiel non biaisé de Donald Knuth en Python
Ecrire une dichotomie en Python
Implémentation de la segmentation d'image en python (Union-Find)
[Python] J'ai essayé d'implémenter un échantillonnage de Gibbs marginalisé
Recherche de priorité de largeur (BPF) Peut-être compris (python)
Règles d'apprentissage Widrow-Hoff implémentées en Python
Algorithme en Python (recherche de priorité en profondeur, dfs)
J'ai écrit Fizz Buzz en Python
Implémentation de la méthode de propagation d'étiquettes en Python
Écrire une recherche de priorité en profondeur en Python
J'ai essayé d'étudier le processus avec Python
Scikit-learn ne peut pas être installé en Python
Implémentation des règles d'apprentissage Perceptron en Python
J'ai essayé la notification de ligne en Python
Implémenté en 1 minute! LINE Notify en Python
Recherche de priorité de profondeur à l'aide de la pile en Python
J'ai écrit la pile en Python
J'ai essayé de résoudre la recherche de priorité de profondeur (DFS) d'AtCoder en Python (résultat: TLE ...)
J'ai mis Python 2.7 dans Sakura VPS 1 Go.
J'ai essayé d'implémenter PLSA en Python
Livre Ali en python: Auto-implémentation de la file d'attente prioritaire
Un client HTTP simple implémenté en Python
J'ai essayé d'implémenter la permutation en Python
J'ai fait un programme de gestion de la paie en Python!
Algorithme en Python (ABC 146 C Dichotomy
Module d'implémentation de file d'attente et Python "deque"
Essayez de dessiner une animation simple en Python
Implémenté en Python PRML Chapitre 7 SVM non linéaire
Rechercher et lire des vidéos YouTube avec Python
J'ai essayé d'implémenter PLSA dans Python 2