Redukcije

Redukcija ili svođenje nekih problema na već rešavane

Korisno je utvrditi može li se zadati problem rešiti ako se zna rešenje njemu sličnog problema. Mada ponekad put do utvrđivanja sličnosti dva problema vodi kroz složen proces redukcije zadatog problema na prethodno poznati problem. Naročito su interesantne redukcije među grafovskim algoritmima i grafovskim i matričnim algoritmima, kao i rešavanje problema linearnog i celobrojnog programiranja.

 

Zadaci

Zadatak 1

Naći niz edit operacija minimalne cene koji transformiše niz znakova A = a1 a2 ... an u niz znakova B = b1 b2 ... bm pri čemu važi:

  1. cena umetanja znaka na poziciju i je c·i (c = const.)
  2. cena brisanja k-tog znaka je cj
  3. cena zamene jednog znaka drugim je 1.

Rešenje:

Problem svodimo na problem nalaženja najkraćih puteva iz datog čvora u posebnom grafu G, koji je određen nizovima A i B. Skup čvorova je

V = { (i, k) | 0 ≤ i ≤ n, 0 ≤ k ≤ m }

dok u čvor (i, k) vode grane iz čvorova:

Dakle, matrica susedstva odgovara matrici upoređivanja stringova.

Nalazimo najkraći put od (0, 0) do svih ostalih čvorova i specijalno do čvora (n, m) i dobijamo rešenje.

Taj put odgovara nizu edit operacija najmanje cene koji niz A transformiše u niz B.

Zadatak 2

U datom grafu G = (V, E) izdvojen je čvor v i svakom čvoru w ∈ V pridružena je cena c(w). Cena usmerenog puta v, x₁ , x₂, ..., xₖ, u definiše se izrazom:

       k
       ∑    c(xᵢ);
     i = 1

specijalno, ako (v, u) ∈ E, onda je cena puta v, u nula. Konstruisati efikasan algoritam za nalaženje puteva minimalne cene od v do ostalih čvorova u G.

Rešenje:

Konstruišemo graf H takav da svakom čvoru w iz G odgovaraju dva čvora w₁ (završni), w₂ (polazni) u H, uz granu (w₁, w₂) cene c(w). Za svaku granu (w, u) iz G pravimo granu (w₂, u₁) cene 0 u H.

                                    c(w)
     w  -------- u             w₁ -------- w₂
    c(w)        c(u)                        | 0
                                           u₁ -------- u₂
                                                c(u)

Time smo problem sveli na problem određivanja svih najkraćih puteva od v₂ do svih završnih čvorova u H.

Zadatak 3

Gornje trougaona matrica je kvadratna matrica u kojoj su svi elementi ispod glavne dijagonale jednaki nula. Dokazati da ako postoji algoritam složenosti O(T(n)) za množenje dve n × n gornje trougaone matrice, onda postoji algoritam složenosti O(T(n) + n²) za množenje dve proizvoljne n × n matrice. Može se koristiti pretpostavka da je T(cn) = O(T(n)), c=const.

Rešenje:

A, B - dve proizvoljne kvadratne matrice reda n. Potrebno je svesti izračunavanje A · B na izračunavanje proizvoda nekih gornje-trougaonih matrica.

A i B možemo napisati u obliku zbira jedne donje i jedne gornje trougaone matrice:

    A = GA + DA
    B = GB + DB

    A · B = GA GB + (GA DB + DA GB) + DA DB

Ako algoritam za množenje dve gornje trougaone matrice primenimo na

    ⌈GA DA⌉     ⌈GB DB⌉  - gornje trougaone dimenzija 2n x 2n
    ⌊0  GA⌋  i  ⌊0  GB⌋

Dobijamo prva tri sabirka:

    ⌈ GA  DA ⌉   ⌈ GB  DB ⌉   ⌈ GA GB     GA DB + DA GB ⌉
    |        | x |        | = |                         |
    ⌊ 0   GA ⌋   ⌊ 0   GB ⌋   ⌊ 0                 GA GB ⌋

Poslednji sabirak računamo kao DA DB = ((DBᵀ) (DAᵀ))ᵀ.

Dakle, algoritam za množenje gornje trougaonih matrica primenjujemo jednom na 2n x 2n matrice i jednom na n x n matrice. Pored toga, imamo 3 transponovanja i 2 sabiranja matrica reda n.

Složenost je O(T(2n) + T(n) + n²) = Q(T(n) + n²)

Zadatak 4

Neka je S skup od n tačaka u ravni. Dijametar skupa S je najveće rastojanje nekih dveju tačaka iz S. Označimo sa DM problem odredivanja dijametra skupa od n tačaka, a sa DS problem utvrdjivanja da li su disjunktna dva skupa A i B od ukupno n realnih brojeva. Dokazati da ako postoji algoritam koji problem DM rešava za vreme O(T(n)), onda postoji algoritam složenosti O(T(n) + n) za rešavanje problema DS.

Rešenje: