Algoritmai

Algoritmai

Pastaba: tai dar ankstyva versija, galinti turėti klaidų.

Tai yra trumpi konspektai, tinkami pasikartojimui, bet nelabai tinkami mokymuisi. Šie algoritmai daug geriau išdėstyti Cormen, Leiserson, Rivest knygoje Introduction to Algorithms. Paskaitų metu galiu pasistengti juos išdėstyti.

Žymėjimai

Algoritmai užrašyti pseudokodu, kuris, beje, labai primena Python programavimo kalbą.

Skaitytojas turėtų būti susipažinęs su grafų teorijos pagrindais.

Raide G dažnai bus žymimas pradinis grafas, raidėmis V ir E -- atitinkamai jo viršūnių ir briaunų aibės. Užrašas adj(u) reiškia visų viršūnių, gretimų u aibę (adj(u) = {v : (u -> v) in E}). Svoriniame grafe briaunos (u -> v) svorį žymėsime weight[u, v].

Raide Q paprastai žymima eilė. Eilė -- abstraktus duomenų tipas, turintis tris operacijas: enqueue prideda elementą į eilės galą, dequeue ištraukia elementą iš eilės pradžios, is not empty patikrina, ar eilė nėra tuščia.

Algoritmų efektyvumas užrašomas asimptotine notacija. Pvz., užrašas O(|V|²) reiškia, jog padvigubinus pradinio grafo viršūnių skaičių, algoritmo veikimo laikas padidės keturgubai, t.y. kvadratu.

Dinaminis programavimas

Tai - ne algoritmas, o greičiau užduočių sprendimo strategija. Ji aprašyta atskirame puslapyje.

Paieška į gylį (Depth First Search)

Taikymų pavyzdžiai: patikrinti, ar grafas jungus, identifikuoti neorientuoto grafo jungumo komponentes, patikrinti, ar egzistuoja kelias grafe iš viršūnės u iki viršūnės v.

def DFS(G):

    def visit(u):
        visited[u] = True
        for v in adj(u):
            if not visited[v]:
                parent[v] = u
                visit(v)

    for u in V:
        visited[u] = False
        parent[u] = None
    for u in V:
        if not visited[u]:
            visit(u)

    return parent, visited

Grafas yra jungus, jei išoriniame cikle sąlyga if not visited[u] bus patenkinta ne daugiau nei vieną kartą.

Masyvas parent sudaro medį (jei grafas jungus) arba mišką (jei ne). Kiekvienas miško medis atitinka atskirą jungumo komponentę.

Jei norime tik sužinoti, kurias viršūnes galima pasiekti iš viršūnės s, galime apsieiti be išorinio ciklo ir tiesiog iškviesti visit(s). Tuomet visited masyvas nurodys visas pasiekiamas viršūnes.

Efektyvumas -- O(|V|+|E|)

Paieška į plotį (Breadth First Search)

Taikymų pavyzdžiai: rasti trumpiausią kelią iš viršūnės s iki visų kitų viršūnių, kai visų briaunų svoriai vienodi.

def BFS(G, s):
    for u in V:
        visited[u] = False
        parent[u] = None
        distance[u] = Infinity
    visited[s] = True
    distance[s] = 0
    Q = [s]
    while Q is not empty:
        u = Q.dequeue()
        for v in adj(u):
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                distance[v] = distance[u] + 1
                Q.enqueue(v)

    return parent, visited, distance

Masyvas visited nurodo, kurios viršūnės yra pasiekiamos.

Masyvas distance nurodo trumpiausių kelio ilgius.

Masyvas parent aprašo trumpiausių kelių medį. Trumpiausias kelias iš viršūnės s į viršūnę t yra s -> ... parent[parent[parent[t]]] -> parent[parent[t]] -> parent[t] ... -> t, jį reikia „išvynioti“ nuo galo.

Efektyvumas -- O(|V|+|E|)

Topologinis rikiavimas (Topological Sort)

Taikymų pavyzdžiai: darbų rikiavimas pagal priklausomybes.

Grafo viršūnės atitinka darbus, briaunos -- priklausomybes tarp jų. Jei grafe yra briauna u -> v, vadinasi, darbas u turi būti atliktas prieš atliekant darbą v. Grafas yra kryptinis ir beciklis.

Algoritmo esmė: paieška į gylį. Kai baigiame darbą su viršūne (aplankę visas iš jos pasiekiamas viršūnes), dedame ją į rezultatų sąrašo pradžią.

def TopologicalSort(G):

    def visit(u):
        visited[u] = True
        for v in adj(u):
            if not visited[v]:
                visit(v)
        result.insert_in_front(u)

    result = []
    for u in V:
        visited[u] = False
    for u in V:
        if not visited[u]:
            visit(u)
    return result

Efektyvumas -- O(|V|+|E|)

Stipriai susietų komponenčių radimas (Strongly Connected Components)

Kryptiniame grafe reikia surasti stipriai susietas komponentes -- viršūnių poaibius, pasižyminčius tokiomis savybėmis:

• iš kiekvienos poaibio viršūnės galima pasiekti bet kurią kitą to paties poaibio viršūnę ir
• poaibis yra maksimalus, t.y. prijungus bet kurią kitą viršūnę prie poaibio pirmoji savybė nebebus tenkinama.

Algoritmo esmė: dvi paieškos į gylį. Pirmoji analogiška topologiniam rikiavimui. Antroji daroma "topologine tvarka" (kabutėse, nes cikliniame grafe topologinė tvarka neegzistuoja) atvirkštiniame grafe GT ir suranda stipriai susietas komponentes.

def SCC(G):

    def visit1(u):
        visited[u] = True
        for v in adj(u):
            if not visited[v]:
                visit1(v)
        l.insert_in_front(u)

    def visit2(u):
        visited[u] = True
        component.add(u)
        for v in adj'(u):
            if not visited[v]:
                visit2(v)

    # rikiuojam viršūnes
    for u in V:
        visited[u] = False
    l = []
    for u in V:
        if not visited[u]:
            visit1(u)

    # randam komponentes
    for u in V:
        visited[u] = False
    components = []
    for u in l:
        if not visited[u]:
            component = []
            visit2(u)
            components.add(component)
    return components

Jei adj(u) = {v : (u -> v) in E}, tai adj'(u) = {v : (v -> u) in E}.

Efektyvumas -- O(|V|+|E|)

Minimalus jungiamasis medis: Kruskalo algoritmas

Esmė: nagrinėjame visas briaunas svorių didėjimo tvarka. Jei galime briauną prijungti prie konstruojamo medžio (t.y. ją prijungus nesusidarys ciklas), ją prijungiame, jei ne -- išmetame.

def Kruskal(G):
    for u in V:
        make_set(u)
    tree = []
    for (u, v) in E, in order by nondecreasing weight[u, v]:
        if find_set(u) != find_set(v):
            union(u, v)
            tree.add((u, v))
    return tree

Naudojame disjoint sets duomenų struktūrą (operacijos make_set, find_set, union).

Algoritmo efektyvumas: O(|E| log |E|).

Minimalus jungiamasis medis: Primo algoritmas

def Prim(G, r):
    for u in V:
        key[u] = Infinity
    key[r] = 0
    parent[r] = None
    while Q is not empty:
        u = Q.extract_min()
        for v in adj(u):
            if v in Q and weight[u, v] < key[v]:
                parent[v] = u
                key[v] = weight[u, v]
    return parent

Viršūnė r bus sukonstruoto medžio šaknis. Tai gali būti bet kuri grafo viršūnė.

Efektyvumas priklauso nuo prioritetinės eilės realizacijos. Naudodami binary heap gausime O(|E| log |V|), naudodami Fibonacci heap gausime O(|E| + |V| log |V|).

Trumpiausio kelio paieška: Dijkstros algoritmas

Taikymų pavyzdžiai: rasti trumpiausią kelią iš viršūnės s iki visų kitų viršūnių, kai briaunų svoriai yra skirtingi.

Algoritmas neveikia, jei grafe yra neigiamo svorio ciklų.

Čia naudojama prioritetinė eilė. Operacija extract_min suranda elementą u, kurio svoris (distance[u]) yra mažiausias.

def Dijkstra(G, s):
    for u in V:
        parent[u] = None
        distance[u] = Infinity
    distance[s] = 0
    Q = V
    while Q is not empty:
        u = Q.extract_min()
        for v in adj(u):
            if distance[u] + weight[u, v] < distance[v]:
                distance[v] = distance[u] + weight[u, v]
                parent[v] = u

    return parent, distance

Masyvas distance nurodo trumpiausių kelių ilgius.

Masyvas parent aprašo trumpiausių kelių medį. Trumpiausias kelias iš viršūnės s į viršūnę t yra s -> ... parent[parent[parent[t]]] -> parent[parent[t]] -> parent[t] ... -> t, jį reikia „išvynioti“ nuo galo.

Efektyvumas priklauso nuo prioritetinės eilės realizacijos. Ja pakeitus paprastu perėjimu per viršūnes gausime O(|V|²), naudodami binary heap gausime O(|E| log |V|), naudodami Fibonacci heap gausime O(|E| + |V| log |V|).

Trumpiausio kelio paieška: Bellmano-Fordo algoritmas

Algoritmas rasti trumpiausią kelią iš viršūnės s iki visų kitų viršūnių, kai briaunų svoriai yra skirtingi.

Algoritmas gali atpažinti neigiamo svorio ciklo egzistavimą.

def BellmanFord(G, s):
    for u in V:
        distance[u] = Infinity
        parent[u] = None
    distance[s] = 0
    for i in 1 .. |V| - 1:
        for (u, v) in E:
            if distance[v] > distance[u] + weight[u, v]:
                distance[v] = distance[u] + weight[u, v]
                parent[v] = u
    for (u, v) in E:
        if distance[v] > distance[u] + weight[u, v]:
            raise "neigiamo svorio ciklas!"
    return distance, parent

Efektyvumas -- O(|V| |E|)

Trumpiausio kelio paieška becikliame grafe

Algoritmas rasti trumpiausią kelią iš viršūnės s iki visų kitų viršūnių, kai briaunų svoriai yra skirtingi.

Grafas turi būti beciklis (DAG'as).

def DAGShortestPath(G, s):
    for u in V:
        distance[u] = Infinity
        parent[u] = None
    distance[s] = 0
    vertex_ordering = TopologicalSort(G)
    for u in vertex_ordering:
        for v in adj(u):
            if distance[v] > distance[u] + weight[u, v]:
                distance[v] = distance[u] + weight[u, v]
                parent[v] = u
    return distance, parent

Efektyvumas -- O(|V|+|E|)

Visų trumpiausių kelių paieška: Floyd-Warshall algoritmas

Algoritmas randa trumpiausių kelių ilgius tarp visų viršūnių porų.

weight[u, v] -- briaunos (u -> v) ilgis (jei tokia briauna egzistuoja) arba begalybė (jei ne). weight[u, u] = 0.

def FloydWarshall(G, s):
    for u in V:
        for v in V:
            d[u, v] = weight[u, v]
    for w in V:
        for u in V:
            for v in V:
                d[u, v] = min(d[u, v], d[u, w] + d[w, v])
    return d

Efektyvumas -- O(|V|³)

Maksimalus srautas: Edmonds-Karp algoritmas

Edmundo-Karpo algoritmas yra platesnio Fordo-Fulkersono metodo taikymas.

G - grafas, s - šaltinio viršūnė, t - tikslo viršūnė, c[u, v] -- briaunos (u -> v) talpa.

def EdmundKarp(G, s, t, c):
    for (u, v) in E:
         f[u, v] = f[v, u] = 0
    while True:

        # konstruojam liekamąjį grafą
        Eresidual = []
        for u in V:
            for v in V:
                cresidual[u, v] = c[u, v] - f[u, v]
                if cresidual[u, v] > 0:
                    Eresidual += (u, v)
        Gresidual = (V, Eresidual)

        # ieškom jame trumpiausio kelio iš s į t
        parent, visited, distance = BFS(Gresidual, s)
        if not visited[t]:
            # jei kelio nėra, reiškia, srautas f jau maksimalus
            return f
        path = []
        v = t
        while v != s:
            u = parent[v]
            path += (u, v)
            v = u

        # randame jo talpą
        cpath = Infinity
        for (u, v) in path:
            cpath = min(cpath, cresidual[u, v])

        # plečiame srautą
        for (u, v) in path:
            f[u, v] += cpath
            f[v, u] = -f[u, v]

Efektyvumas -- O(|V| |E|²)