Zásobník, Rad, Prioritný rad

  • modul queue
  • metódy get(), put()
In [1]:
import queue
In [2]:
def rad_vypis(rad, hodnoty): #vypise chovanie radu po vlozeni hodnot
    for hodnota in hodnoty:
        rad.put(hodnota) #vlozime prvok
    while not rad.empty(): #kym nie je prazdny rad
        print(rad.get())
In [3]:
h = [3,2,1,7,8]
In [4]:
rad_vypis(queue.Queue(), h) #rad, FirstInFirstOout
3
2
1
7
8
In [5]:
rad_vypis(queue.LifoQueue(), h) #zasobnik
8
7
1
2
3
In [6]:
rad_vypis(queue.PriorityQueue(), h) #prioritny rad
1
2
3
7
8
In [7]:
rad_vypis(queue.PriorityQueue(), [(2, "S"), (3, "U"), (1, "A"), (4, "1")])
(1, 'A')
(2, 'S')
(3, 'U')
(4, '1')

Teória grafov

  • graf (vrcholy $|V| = n$, hrany $|E| = m$), orientovaný graf (digraf), multigraf (násobné hrany, slučky)
  • susedné vrcholy, vrchol+hrana incidentné
  • reprezentácia grafov (matica susednosti $n \times n$, matica incidencie $n \times m$, zoznam susedov $O(n+m)$, implicitne definované - bludisko)
  • hranovo/vrcholovo ohodnotené grafy
  • postupnosť incidentných vrchol,hrana,vrchol,... vrchol = sled, ťah (nesmie sa opakovať hrana), cesta (nesmie sa opakovať vrchol)
  • prechádzanie grafu - BreathFirstSearch(do šírky, Rad), DepthFirstSearch(do hĺbky, Zásobník)
  • komponenty súvislosti
  • najkratšia cesta - medzi dvoma vrcholmi, z jedného vrcholu do všetkých (Dijkstra), medzi všetkými dvojicami (Floyd-Warshall)
  • súvislosť grafu, cyklus, strom, les, kostra grafu (spanning tree)
  • najlacnejšia kostra
    • budujeme postupne súvislú kostru z počiatočného vrcholu (Jarník/Prim/Dijsktra)
    • pridávame najlacnejšie hrany tak, aby nezvnikol cyklus (Kruskal)

image.png

In [8]:
n, m = [int(_) for _ in input().split()] #pocet vrcholov a hran
7 6
In [10]:
sused = [[] for v in range(n)] #zoznam susedov
for i in range(m):
    u, v = [int(_) for _ in input().split()]
    sused[u].append(v)
    sused[v].append(u)
print(sused)
0 3
1 2
2 4
4 3
1 3
5 6
[[3], [2, 3], [1, 4], [0, 4, 1], [2, 3], [6], [5]]

Prehľadávanie grafu

In [11]:
#BFS - do sirky, najdenie jedneho komponentu suvislosti

rad = queue.Queue() #BFS
navstiveny = [ False for v in range(n)] #vrchol v bol navstiveny
rad.put(0) #zacinajuci vrchol
while not rad.empty():
    v = rad.get() #vyberieme vrchol
    if navstiveny[v] == True: #preskocime
        continue
    print(v)
    navstiveny[v] = True
    for u in sused[v]:
        if not navstiveny[u]:
            rad.put(u)
    
0
3
4
1
2
In [12]:
#DFS - do hlbky, najdenie jedneho komponentu suvislosti

rad = queue.LifoQueue() #DFS
navstiveny = [ False for v in range(n)] #vrchol v bol navstiveny
rad.put(0) #zacinajuci vrchol
while not rad.empty():
    v = rad.get() #vyberieme vrchol
    if navstiveny[v] == True: #preskocime
        continue
    print(v)
    navstiveny[v] = True
    for u in sused[v]:
        if not navstiveny[u]:
            rad.put(u)
0
3
1
2
4

BFS aj DFS pri použití zoznamu susedov majú zložitosť $O(n+m)$

Bludisko - najkratšia cesta pomocou prehľadávania do šírky

In [44]:
lines = [
"...........",
"...........",
"....#......",
"....#......",
"....#.#....",
"....#.#....",
"......#....",
"......#...."]
n,m = len(lines), len(lines[0])
mapa = [[x for x in line] for line in lines]
In [18]:
print(n, m)
#len na zvyraznenie startovacie a cielove policko
mapa[6][2] = 'S'
mapa[6][8] = 'C'

for riadok in mapa:
    print(*riadok, sep="")
8 11
...........
...........
....#......
....#......
....#.#....
....#.#....
..S...#.C..
......#....
In [43]:
def da_sa(r, s): #da sa ist na poziciu [r, s]?
    if not 0 <= r < n: #cislo riadku mimo rozsah
        return False
    if not 0 <= s < m: #stlpec mimo rozsah
        return False
    return mapa[r][s] == '.'

def najdi(mapa, start, ciel): #najdi najmensi pocet krokov zo startovacie policka do cieloveho
    smery = [(0,1), (0, -1), (1, 0), (-1, 0)] #styri smery: vpravo, vlavo, dole, hore
    
    rad = queue.Queue() #do sirky
    rad.put(start)
    mapa[start[0]][start[1]] = 0
    while not rad.empty():
        r, s = rad.get()
        for smer_r, smer_s in smery:#vsetky susdne policka
            nr, ns = r+smer_r, s+smer_s #suradnice noveho policka
            if da_sa(nr, ns):
                #print(nr, ns)                
                mapa[nr][ns] = 1+ mapa[r][s]
                if nr == ciel[0] and ns == ciel[1]:
                    return mapa[nr][ns]
                rad.put( (nr, ns) ) #pridame do radu
    return -1
for riadok in mapa:
    print(*riadok)
najdi(mapa, (6, 2), (6,8))
for riadok in mapa:
    print(*riadok)
. . . . . . . . . . .
. . . . . . . . . . .
. . . . # . . . . . .
. . . . # . . . . . .
. . . . # . # . . . .
. . . . # . # . . . .
. . . . . . # . . . .
. . . . . . # . . . .
8 7 6 7 8 9 10 11 . . .
7 6 5 6 7 8 9 10 11 12 .
6 5 4 5 # 7 8 9 10 11 12
5 4 3 4 # 6 7 8 9 10 11
4 3 2 3 # 5 # 9 10 11 12
3 2 1 2 # 4 # 10 11 12 .
2 1 0 1 2 3 # 11 12 . .
3 2 1 2 3 4 # . . . .

A* algoritmus

A* algorithm

  • pozerá sa cez heuristický odhad vzdialenosti do cieľa a vyberá v poradí aktuálna_vzdialenosť+odhad, najjednoduchšia heuristika je Manhattanská vzdialenosť, $L_1$
In [46]:
def Astar(mapa, start, ciel): #najdi najmensi pocet krokov zo startovacie policka do cieloveho
    smery = [(0,1), (0, -1), (1, 0), (-1, 0)] #styri smery: vpravo, vlavo, dole, hore
    
    rad = queue.PriorityQueue() #priorita podla odhadu
    rad.put((0, start[0], start[1])) #nulova priorita/odhadovana vzdialenost, r, s
    mapa[start[0]][start[1]] = 0
    while not rad.empty():
        w, r, s = rad.get()
        for smer_r, smer_s in smery:#vsetky susdne policka
            nr, ns = r+smer_r, s+smer_s #suradnice noveho policka
            if da_sa(nr, ns):
                #print(nr, ns)                
                mapa[nr][ns] = 1+ mapa[r][s]
                if nr == ciel[0] and ns == ciel[1]:
                    return mapa[nr][ns]
                rad.put( (mapa[nr][ns]+ abs(nr-ciel[0])+abs(ns-ciel[1]), nr, ns) ) #pridame do radu
    return -1
for riadok in mapa:
    print(*riadok)
Astar(mapa, (6, 2), (6,8))
for riadok in mapa:
    print(*riadok)
. . . . . . . . . . .
. . . . . . . . . . .
. . . . # . . . . . .
. . . . # . . . . . .
. . . . # . # . . . .
. . . . # . # . . . .
. . . . . . # . . . .
. . . . . . # . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . 4 5 # 7 8 9 10 . .
. 4 3 4 # 6 7 8 9 10 .
4 3 2 3 # 5 # 9 10 11 .
3 2 1 2 # 4 # 10 11 12 .
2 1 0 1 2 3 # 11 12 . .
3 2 1 2 3 4 # . . . .

Floyd-Warshall pre ohodnotené grafy

  • dynamické programovanie dist[i,j,k] ... vzdialenosť z vrchola i do vrchola j ak môžeme použiť ako vrcholy na cesty vrcholy 0,..,k
In [56]:
  for k in range(n):
    for i in range(n):
        for j in range(n):
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) #cestu i->j rozsirime cez k, t.j. i->k->j
---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
<ipython-input-56-bf73437689be> in <module>
      2   for i in range(n):
      3       for j in range(n):
----> 4           dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) #cestu i->j rozsirime cez k, t.j. i->k->j

NameError: name 'dist' is not defined

Ohodnotené grafy - Dijkstra

  • vypočíta najkratšie vzdialenosti z jedného vrchola do všetkých ostatných
  • pri dosiahnutí cieľového vrchola sa môže ukončiť pri prehľadávaní len do jedného koncového vrchola

image.png

In [58]:
n, m = [int(_) for _ in input().split()] #pocet vrcholov a hran
sused = [[] for v in range(n)]
for i in range(m):
    u, v, w = [int(_) for _ in input().split()]
    sused[u].append( (v, w) )
    sused[v].append( (u, w) )
print(sused)
7 11
0 1 7
0 3 5
1 2 8
1 3 9
1 4 7
2 4 5
3 4 15
3 5 6
4 5 8
5 6 11
4 6 9
[[(1, 7), (3, 5)], [(0, 7), (2, 8), (3, 9), (4, 7)], [(1, 8), (4, 5)], [(0, 5), (1, 9), (4, 15), (5, 6)], [(1, 7), (2, 5), (3, 15), (5, 8), (6, 9)], [(3, 6), (4, 8), (6, 11)], [(5, 11), (4, 9)]]

Namiesto aktualizácie doteraz najlepšej ceny vo vrchole je v nasledujúcom kóde použitý prioritný rad, ktorý vyberie najlacnejšie spojenie do nového vrcholu.

In [59]:
rad = queue.PriorityQueue() #Prioritný rad (Dijkstra)
navstiveny = [ False for v in range(n)] #vrchol v bol navstiveny
rad.put( (0, 3) ) #zaciname vo vrchole D, vzdialenost je nulova
while not rad.empty():
    vaha, v = rad.get() #vyberieme dalsi vrchol, teda najblizsi
    if navstiveny[v]:
        continue
    navstiveny[v] = True
    print(v, vaha) #prisli sme do vrchola v s celkovou vzdialenostou vaha
    for u, w in sused[v]: #sused u vo vzdialenosti w
        if not navstiveny[u]:
            rad.put( (vaha+w, u) )
3 0
0 5
5 6
1 9
4 14
2 17
6 17

Najlacnejšia kostra grafu (Mininum spanning tree)

  • Jarník/Prim/Dijsktra algoritmus - postupné generovanie kostry, pridávanie vždy najlacnejšej hrany z už spojených vrcholov v kostre do vrchola mimo už existujúcu kostru
In [55]:
rad = queue.PriorityQueue() #Prioritný rad (Dijkstra)
navstiveny = [ False for v in range(n)] #vrchol v bol navstiveny
rad.put([0, 3, None]) #pociatocna vzdialenost, zacinajuci vrchol, prichadzajuci z vrchola
suma = 0
while not rad.empty():
    d, v, prichod = rad.get() #vyberieme vrchol s najmensou hodnotou-vzdialenostou d
    if navstiveny[v]: #ak sme prisli k uz spracovanemu vrcholu, tak ho preskocime/ignorujeme
        continue
    if prichod != None:
        print(v, prichod, d)
        suma += d
    navstiveny[v] = True
    for u, w in sused[v]: #vrchol u = sused vrchola v, vaha w
        if not navstiveny[u]:
            rad.put([w, u, v])
print("Cena kostry:", suma)
0 3 5
5 3 6
1 0 7
4 1 7
2 4 5
6 4 9
Cena kostry: 39