Fórum Root.cz
Hlavní témata => Vývoj => Téma založeno: Honza 26. 01. 2017, 17:50:22
-
Ahoj,
mám do školy udělat implementaci dijsktrova algoritmu a úplně si nevím rady s jednou věcí - mám tento kód napsaný
class Vertex:
def __init__(self, id, name):
self.id = id
self.name = name
class Edge:
def __init__(self, source, target, weight):
self.source = source
self.target = target
self.weight = weight
class Dijkstra:
def __init__(self):
self.vert_dict = {}
self.num_vertices = 0
def computePath(self, sourceId):
pass
def getShortestPathTo(self, targetId):
pass
def createGraph(self, vertexes, edgesToVertexes):
self.graph = {}
for vert in vertexes:
self.graph[vert] = []
for edge in edgesToVertexes:
self.graph[edge.source].append(edge)
def resetDijkstra(self):
pass
def getVertexes(self):
return self.vert_dict.keys()
A popis metod u třídy Dijkstra
createGraph(self, vertexes, edgesToVertexes) - metoda vytvoří graf ze zadaných vrcholů - toto myslím, že mám dobře
getVertexes(self) - metoda vrátí vrcholy, nad kterými je možné provést Dijkstrův algoritmus. TJ vrcholy, které jsou vytvořeny pomocí metody init - to si také myslím, že mám dobře
computePath(self, sourceId) - metoda nalezne nejkraští cesty ze zadaného vrcholu do všech vrcholů v grafu. Metoda nic nevrací, ale po skončení operace by měly mít všechny vrcholy vyplněnou proměnou minDistance, která reprezentuje minimální vzdálenost o zadaného vrcholu - tohle nevím jak udělat. Mohl by mi prosím někdo poradit? :)
-
Takže jediná věc, co ti z domácího úkolu chybí, je ten domácí úkol? ;)
Zamysli se, co budeš potřebovat. Co třebas nějakou datovou strukturu, kde si budeš držet zatím nehotové vrcholy?
-
computePath(self, sourceId) - metoda nalezne nejkraští cesty ze zadaného vrcholu do všech vrcholů v grafu. Metoda nic nevrací, ale po skončení operace by měly mít všechny vrcholy vyplněnou proměnou minDistance, která reprezentuje minimální vzdálenost o zadaného vrcholu - tohle nevím jak udělat. Mohl by mi prosím někdo poradit? :)
Vrchol už nesmí být obyčejný seznam, ale třída, která bude mít:
* číslo (na začátku +nekonečno, -1 nebo tak něco) udávající minimální vzdálenost
* seznam sousedů/hran stejně jako to máš teď.
A potom tvoje funkce vždycky nalije vrcholy do nějakého pomocného pole (příp. haldy pro lepší složitost), updatne všem sousedům tato čísla, vytáhne z pomocného pole vrchol s nejmenším číslem a opakuje.
-
Myslel jsem to, tak že to vytvoření grafu a vracení vrcholů mám v pořádku (alespoň se domnívám) :)
Ok, takže bych to viděl na nějakou frontu? Respektive nějakou prioritní frontu, která mi to seřadí podle hran s nejmenší cestou?
-
Já to chápu takhle -
V počátečním uzlu (N) budu mít cestu nejmenší - 0 a předka None, pak porovnám váhu všech hran a vydám se tou nejmenší, kde nastavím jako váhu 0 + 5 = 5, předek N. Poté znovu porovnám od tohoto uzlu (M) nejmenší hranu (tady bude asi problém toho, aby to nebyl ta hrany, po které jsem přijel) a opět jí přiřadím váhu 5 + 2 = 7, předek bude M...
-
Já ten algoritmus chápu, kdybych ho měl nakreslit na papíře jak se to chová, tak je to v pořádku.
Pro mě je právě ten nejhorší problém to pak dostat do kódu :/ to mi prostě vůbec nejde... Kdyby vám mohl poprosit právě, o nějaký návod krok za krokem, jak to vytvořit. Něco jako 1) potřebuješ frontu, za 2) proiteruješ jí, 3)...
-
Myslel jsem to, tak že to vytvoření grafu a vracení vrcholů mám v pořádku (alespoň se domnívám) :)
Je správně, ale zadání po tobě vyžaduje, aby to kromě seznamu sousedů umělo držet i číslo, což bych právě řešil přes tu třídu.
V počátečním uzlu (N) budu mít cestu nejmenší - 0 a předka None, pak porovnám váhu všech hran a vydám se tou nejmenší, kde nastavím jako váhu 0 + 5 = 5, předek N. Poté znovu porovnám od tohoto uzlu (M) nejmenší hranu
To právě nebude fungovat. Mějme vrcholy A, B, C a hrany
A → B (2)
A → C (2)
A → C (3)
(a začínáme v A). Ty se vydáš do B, nastavíš cenu na 2, a z B se vydáš do C, tam nastavíš cenu na 4, ale správná cena je 3. Proto nesmíš jít po nejlevnější hraně z aktuálního vrcholu, ale z nejlevnějšího vrcholu - a proto tam máš tu haldu.
Pro mě je právě ten nejhorší problém to pak dostat do kódu :/ to mi prostě vůbec nejde... Kdyby vám mohl poprosit právě, o nějaký návod krok za krokem, jak to vytvořit.
Začal bych tím, že přepíšeš ten pseudokód z Wikipedie do Pythonu ;)
-
zahodil bych třídu Vector. Stačí čísla vrcholů. Nestačí reprezentovat hrany jako n-tice? Ta tvá reprezentace je strašné plýtvání.
smíte používat nějakou knihovnu pro haldu?
pokud smíte používat libovolnou knihovnu, celé bych to zahodil a použil igraph
-
oprava:
zahodil bych třídu Vertex.
-
zahodil bych třídu Vertex.
Jé, to jsem si nevšiml, do ní přece může uložit to číslo, které požaduje zadání.
Stačí čísla vrcholů.
A někam musí ukládat ty vzdálenosti - může to dávat do druhého seznamu. A tady se dá vybrat, jestli to právě mít „správně“ (třída), nebo o něco menší a rychlejší (seznamy)
-
S tím pseudokódem nevím - nevím jak ho dát do Pythonu...
Laboroval jsem do teď nad tím a fakt nevím, asi by bylo dobré si zopakovat celý předmět od začátku... :/
Jinak ty třídy apod. musí vypadat přesně tak, jak to tady mám napsané. Žádné knihovny používat nemůžeme a taky musíme místo haldy používat prioritní frontu.
-
zahodil bych třídu Vertex.
Jé, to jsem si nevšiml, do ní přece může uložit to číslo, které požaduje zadání.
Stačí čísla vrcholů.
A někam musí ukládat ty vzdálenosti - může to dávat do druhého seznamu. A tady se dá vybrat, jestli to právě mít „správně“ (třída), nebo o něco menší a rychlejší (seznamy)
čísla vrcholů jsou indexy listu, vzdálenosti jsou hodnoty. Není důvod číslovat vrcholy jinak než od nuly.
Jako vstup lze zadat jen počet vrcholů a hrany. Není třeba vrcholy vyjmenovávat. Tak to má i igraph.
-
Žádné knihovny používat nemůžeme a taky musíme místo haldy používat prioritní frontu.
to je to stejné, prioritní fronta se většinou implementuje pomocí haldy. nesmíte používat ani vestavěné knihovny?
třeba zde je pěkné řešení. těžko se dá vymyslet něco lepšího.
https://gist.github.com/kachayev/5990802
Můžeš to zkusit naroubovat na tu svou kostru. defaultdict se dá nahradit a heapq s trochou úsilí také.
-
Žádné knihovny používat nemůžeme a taky musíme místo haldy používat prioritní frontu.
Neznám zadání, nicméně pokud nemáš předepsanou interní formu reprezentace grafu, můžeš použít adjacency matrix, potom pro Dijkstru prioritní frontu nepotřebuješ: https://gist.github.com/shintoishere/f0fa40fe1134b20e7729
Složitost to má O(V^2), kde V je počet vrcholů, takže se to prakticky hodí jen pro grafy, které mají hodně hran a málo vrcholů.
-
def dijkstra(edges, f, t):
g = {}
for l,r,c in edges:
g.setdefault(l, []).append((c,r))
q, seen = [(0,f,())], set()
while q:
(cost,v1,path) = heappop(q)
if v1 not in seen:
seen.add(v1)
path = (v1, path)
if v1 == t: return (cost, path)
for c, v2 in g.get(v1, ()):
if v2 not in seen:
heappush(q, (cost+c, v2, path))
return float("inf")
# následují funkce převzaté z heapq.py
def heappush(heap, item):
heap.append(item)
_siftdown(heap, 0, len(heap)-1)
def heappop(heap):
lastelt = heap.pop()
if heap:
returnitem = heap[0]
heap[0] = lastelt
_siftup(heap, 0)
return returnitem
return lastelt
def _siftup(heap, pos):
endpos = len(heap)
startpos = pos
newitem = heap[pos]
childpos = 2*pos + 1
while childpos < endpos:
rightpos = childpos + 1
if rightpos < endpos and not heap[childpos] < heap[rightpos]:
childpos = rightpos
heap[pos] = heap[childpos]
pos = childpos
childpos = 2*pos + 1
heap[pos] = newitem
_siftdown(heap, startpos, pos)
def _siftdown(heap, startpos, pos):
newitem = heap[pos]
while pos > startpos:
parentpos = (pos - 1) >> 1
parent = heap[parentpos]
if newitem < parent:
heap[pos] = parent
pos = parentpos
continue
break
heap[pos] = newitem
nahradil jsem v tom řešení z https://gist.github.com/kachayev/5990802 importované moduly vloženým kódem. Můžeš to zkusit nějak obfuskovat, aby to vypadalo jako tvůj výtvor.