SHARE
TWEET

Untitled

a guest Dec 11th, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2.  
  3. #informatii despre un nod din arborele de parcurgere (nu din graful initial)
  4. class NodParcurgere:
  5.     def __init__(self, id, info, parinte):
  6.         self.id=id # este indicele din vectorul de noduri
  7.         self.info=info
  8.         self.parinte=parinte #parintele din arborele de parcurgere
  9.  
  10.     def obtineDrum(self):
  11.         l=[self.info]; #lista care incepe cu nodul dat
  12.         nod=self
  13.         while nod.parinte is not None: #parcurg toate nodurile din drum
  14.             l.insert(0, nod.parinte.info)
  15.             nod=nod.parinte
  16.         return l
  17.        
  18.     def afisDrum(self): #returneaza si lungimea drumului
  19.         l = self.obtineDrum()
  20.         print("->".join(l)) #pt [a, b, f] o sa afiseze a->b->f
  21.         return len(l)
  22.  
  23.     def contineInDrum(self, infoNodNou):
  24.         nodDrum = self
  25.         while nodDrum is not None:
  26.             if infoNodNou == nodDrum.info:
  27.                 return True
  28.             nodDrum=nodDrum.parinte
  29.        
  30.         return False
  31.        
  32.     def __repr__(self):
  33.         sir=""     
  34.         sir+=self.info+"("
  35.         sir+="id = {}, ".format(self.id)
  36.         sir+="drum="
  37.         drum=self.obtineDrum()
  38.         sir+=("->").join(drum)
  39.         sir+=")"
  40.         return(sir)
  41.        
  42.  
  43. class Graph: #graful problemei
  44.     def __init__(self, start, scopuri):
  45.         self.nrStive = len(start)
  46.         self.start=start
  47.         self.scopuri=scopuri
  48.  
  49.     #va genera succesorii sub forma de noduri in arborele de parcurgere
  50.     def genereazaSuccesori(self, nodCurent):
  51.         listaSuccesori = []  # pornesc cu lista vida de succesori
  52.         # pentru fiecare stiva i vreau sa incerc sa iau un bloc
  53.         for i in range(self.nrStive):
  54.             # test sa vad daca pot extrage bloc
  55.             if len(nodCurent.info[i]) > 0:
  56.                 # mai jos copiez informatia nodului curent in nodul intermediar
  57.                 infoIntermediar = copy.deepcopy(
  58.                     nodCurent.info)  # face exact ce face for-ul de pe tabla, dar e mai compact
  59.                 nodIntermediar = NodParcurgere(infoIntermediar,
  60.                                                nodCurent)  # fac un nod parcurgere nou daca vreau sa afisez si starea intermediara (fara bloc)
  61.                 # iau primul bloc din stiva i
  62.                 bloc = nodIntermediar.info[i].pop(0)
  63.                 # reparcurg stivele incercand sa pun blocul la loc
  64.                 # pentru fiecare stiva j diferita de stiva i (ca sa nu ajung la starea de dinainte)
  65.                 for j in range(self.nrStive):
  66.                     if i != j:
  67.                         # creez un NodParcurgere nou pentru punerea blocului
  68.                         infoNou = copy.deepcopy(nodIntermediar.info)
  69.                         nodSuccesor = NodParcurgere(infoNou,
  70.                                                     nodIntermediar)  # sau pot pune nodCurent ca parinte daca nu vreau sa afisez si pasii intermediari
  71.                         # actualizez nodul, punand blocul lipsa pe stiva j
  72.                         nodSuccesor.info[j].insert(0, bloc)
  73.                         # adaug nodul succesor in lista de succesori
  74.                         listaSuccesori.append(nodSuccesor)
  75.         return listaSuccesori
  76.        
  77.     def __repr__(self):
  78.         sir = ""
  79.         for (k,v) in self.__dict__.items(): #creez un dictionar(metoda predefinita)
  80.             sir+="{} = {}\n".format(k, v) # {} este echivalent cu %s din C
  81.         return(sir)
  82.        
  83.        
  84.  
  85. ############################################################################################## 
  86. #                                 Initializare problema                                      #
  87. ##############################################################################################     
  88.  
  89. #pozitia i din vectorul de noduri da si numarul liniei/coloanei corespunzatoare din matricea de adiacenta      
  90.  
  91.  
  92. start=[["a"],["b","c"],["d"]]
  93. scopuri=[["c","b"],[],["a","d"]]
  94. gr=Graph(start, scopuri)
  95.  
  96.  
  97.  
  98. #### algoritm BF
  99. #presupunem ca vrem mai multe solutii (un numar fix)
  100. #daca vrem doar o solutie, renuntam la variabila nrSolutiiCautate
  101. #si doar oprim algoritmul la afisarea primei solutii
  102. nrSolutiiCautate=4
  103.  
  104. def breadth_first(gr):
  105.     global nrSolutiiCautate #folosesc global pt a putea folosi variabila globala
  106.     #in coada vom avea doar noduri de tip NodParcurgere (nodurile din arborele de parcurgere)
  107.     c = [NodParcurgere(gr.noduri.index(start), start, None)]
  108.     continua = True #variabila pe care o setez la false cand consider ca s-au afisat suficiente solutii
  109.     while len(c) > 0 and continua:
  110.         print("Coada actuala: " + str(c))
  111.         input()
  112.         nodCurent = c.pop(0)
  113.         print("Se extinde nodul ", nodCurent.info, " din drumul ", end="")
  114.         nodCurent.afisDrum()
  115.  
  116.         if nodCurent.info in scopuri:
  117.             print("----> Solutie: ", end="")
  118.             l = nodCurent.afisDrum()
  119.             print("Lungime solutie:", l)
  120.             nrSolutiiCautate -= 1
  121.             if nrSolutiiCautate == 0:
  122.                 continua = False
  123.         lSuccesori = gr.genereazaSuccesori(nodCurent)
  124.         c.extend(lSuccesori) #adaug in finalul cozii
  125.         print("Se adauga in coada: ", end="")
  126.         if len(lSuccesori) > 0:
  127.             for nod in lSuccesori:
  128.                 print(nod.info, end=" ")
  129.         else:
  130.             print("nimic")
  131.         print("")
  132.  
  133.  
  134. breadth_first(gr)
  135. #bonus: sa afiseze solutia in momentu expandarii
  136. #ca sa nu puna newline: print("fdsf", end="")
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top