Algorísmia

Conrado Martínez <alg@lsi.upc.edu> <conrado@lsi.upc.edu>

http://www.lsi.upc.edu/~alg



QuickSelect

Algorisme:

Partició(A, i, j, m) ---

if (k == m) return A[k];

if (k < m) return QuickSelect(A, i, m-1, k)

if (k > m) return QuickSelect(A, m+1, j, k)

 = # de comparacions per trobar el k-èssim

Cas pitjor

Cas mitjà

Lliberia std (C++)

nth(...) -> QuickSelect                        sort(..) -> QuickSort

partial_sort(...) -> HeapSort                L.sort(...) -> MergeSort

Select

L’algorisme parteix (conceptualment) la llista en  blocs amb  valors cadascun. Dins de cada bloc, troba la mediana i la situa en una posició coneguda. Això triga .

Un cop fet això, troba la mediana de totes les medianes. Tenim: . Aquesta pseudo-mediana l’utilitza de pivot per a la crida recursiva. En el cas pitjor, ens quedaran elements.

Com trobar la ?


Heaps

Un heap és un arbre binari quasi-complet (totes les branques de la mateixa longitud excepte l’últim nivell on les de la dreta poden tenir un nivell menys) on tot element té una prioritat  (minheap, o  per a un maxheap) que la de qualsevol dels seus descendents.

Representem l’arbre en forma d’array. Per simplificar, suposem els índex .

  1. A[i] conté l’arrel.
  2. Si  llavors A[2i] conté el fill esquerra d’A[i].
  3. Si  llavors A[2i+1] conté el fill dret d’A[i].
  4. Si  llavors A[i/2] conté el pare d’A[i].

Té les següents operacions:

L’alçada d’un heap és . Llavors, els costos de les operacions anteriors, en cas pitjor, és , el nombre màxim de passos que pot arribar a fer l’operació flota (per a enfonsa és  segons on estigui l’element sobre el que actuem).

heapsort (A, n) -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
crea_heap (A, n) // un max-heap

for (int i = n; i > 1; --i) {

swap (A[1], A[i]) // (elimina_max)

enfonsa (A, i-1, 1)

}
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Cost (detallat) del bucle:

Fórmula de Stirling:

selecciona_k_menors (A, n) -
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
crea_heap (A, n) // un min-heap

for (int i = 0; i < k; ++i)

elimina_min (A, n-i);
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Exercici:


Arbres binaris de cerca

És un arbre binari que satisfà l’invariant: per a qualsevol node de l’arbre, tots els elements al subarbre esquerra tenen una clau inferior al node i tots els elements del subarbre dret tenen una clau superior al node.

Per unir dos arbres independents agafem un node comú segons:

join (☐, ☐) = ☐

join (L, ☐) = L

join (☐, R) = R

join (a, b) =  (on a i b tenen fills als dos costats)

Per a més detalls, veure Apunts d’EDA: Diccionaris (ABC i AVL).

Altres:

Un diccionari fa servir una funció de hash que acostuma a utilitzar un modul d’un número aleatori amb un nombre primer. En cas de conflictes es pot utilitzar diverses estratègies: lineal probing, double hashing (una segona funció de hash), etc.



Algorismes golafres (greedy algorithms)

Exemples:


Arbres d’expansió (spanning trees)

Tenim un graf no-dirigit, connex i ponderat, G.

Un arbre d’expansió de G és un subgraf T=<V(G), A>,  tal que T és un arbre (no dirigit, connex, acíclic).

El pes d’un subgraf H és .

L’estructura genèrica d’un algorisme per trobar un arbre d’expansió mínim és:

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
T = Ø; n = |V(G)|

mentre |T| != n-1 fes

e = selecciona_aresta (G, T, w);

T = T  {e}

fmentre
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

  1. Un conjunt d’arestes  és prometedor si existeix un arbre d’expansió mínim (MST) T=<V(G), A’> tal que A.
  2. Un tall de G és un parell <A, B> tal que  i .
  3. Una aresta e = (u, v) respecta el tall <A, B> si els dos extrems d’e estan en A o en B. L’aresta creua el tall si té un extrem en A i l’altre en B.
  4. Un subconjunt C respecta el tall <A, B> si cada aresta en C el respecta.

Teorema

Sigui A un conjunt d’arestes prometedor que respecta el tall <U, V(G) - U>. Sigui e l’aresta de pes mínim que creua el tall. Llavors  és prometedor.

Demostració: Sigui T = <V, A’> el MST tal que .

  1. , . Com que T’ és MST,  és prometedor.

Algorisme de Kruskal


- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Ordena E(G) per pes creixent

T = Ø;

mentre |T| != n-1 fes

e = treu la primera aresta de la llista ordenada d’arestes

si e no crea cicle en T llavors

T = T  {e}

fsi

fmentre
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

T és prometedor. U = el conjunt d’arestes en la component connexa del vèrtex més petit d’e=(u, v).

Cost:  (però sovint no es recorren les m arestes)

Algorisme de Prim

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
T = Ø;

vistos = {1}

mentre |T| != n-1 fes

e = (u, v) = l’aresta amb pes mínim que uneix un vèrtex amb un vèrtex .

T = T  {e}

vistos = vistos  {v}

fmentre
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

T és prometedor. <vistos, v-vistos>.

Versió més eficient:

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
T = Ø;

vistos = {1}

mentre |T| != n-1 fes

mindist =

for vvistos fes

si mindist[v] < mindist llavors

cand = v; mindist = mindist[v]

fi

fi

e = (cand, veí[cand])

T = T  {e}

vistos = vistos  {u}

per tot v Adj(G, cand) fes

si v  llavors si mindist[v] > w((v, cand)) llavors

mindist[v] = w((v, cand))

veí[v] = cand

fsi; fsi

fmentre
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Cost: 

Es pot millorar (amb un heap i una taula de dispersió) a .

Particions: Union-Find / MFSets (Merge-Find Sets)

És una estructura de dades amb les operacions int find (int i) const i void union (int i, int j) (a vegades anomenada merge) que operen sobre grups de conjunts.

Per exemple, podem tenir els conjunts {1,2,3,4,5}, {10,11}, {7,8,23}. La funció find, donat un element d’un dels conjunts, ens retorna un element representatiu del conjunt (sempre el mateix preguntat per a qualsevol element del conjunt), permetent-nos saber si dos elements estan dins del mateix conjunt o no. La funció union fusiona dos conjunts (donats dos elements de conjunts diferents).

Possibles implementacions:

Implementació del mètode union quan s’utilitza la representació QuickUnion:

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
int ri = find(i);

int rj = find(j);

if (ri != rj) { // P[ri] == ri, P[rj] == rj

        P[rj] = ri;

}
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

La implementació del find seria:

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
while (P[i] != i) i = P[i];

return i;
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Si volem evitar que, a mida que fem unions l’altura dels arbres vagi creixent, el que podem fer és aprofitar el vector element->pare de manera que els elements arrel, en lloc de contenir el seu mateix identificador (per marcar que és una arrel), continguin un nombre negatiu (per marcar que és un arrel) i que aquest nombre indiqui quants elements té l’arbre. Llavors podem canviar el mètdode d’unió:

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

// nova implementació del find:

while (P[i] > 0) i = P[i]
int ri = find(i);

int rj = find(j);

if (ri != rj) {

        if (P[ri] <= P[rj]) {

                int tmp_rj = P[rj];

                P[rj] = ri;

                P[ri] += tmp_rj;

        } else {

                // anàlogament...

        }

}
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Així sempre estarem penjant l’arbre més baix de l’arbre més alt. Estem limitant l’altura màxima a logn.

Per reduir més l’altura, podem modificar la funció find de manera que canviï els nodes que recorre perquè apuntin a l’avi més amunt (compressió parcial de camins). Fins i tot podem utilitzar un find amb compressió total de camins (fent dos recorreguts, un per trobar l’arrel i un segon per assignar tots els nodes recorreguts a l’arrel).

Aplicat a l’algorisme de Kruskal

Podem implementar l’algorisme de Kruskal utilitzant una estructura Union-Find amb representació Quick-Union i compressió de camins (total o parcial). L’algorisme (suposant arestes ja ordenades o ordenació en temps lineal) tindrà un cost  (on  és la funció inversa d’Ackermann) o, de forma menys precisa,  (on  és l’enter  tal que  -el logaritme  vegades-; és un nombre que creix molt lentament).

Problemes de camins

Algorisme de Dijkstra (pesos positius!)

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

u = selecciona el vèrtex ¬VIST amb D mínima

per tota v  Successors(G, u)

        si (D[u] + w(u, v)) < D[v]

                D[v] = D[u] + w(u,v)

        fsi

fi
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

El resultat és . Demostració:

  1. distància mínima entre s i u passant per VIST.

Trobem els casos:

  1. w vist: per definició,  i no es modifica .
  2. w no vist: distància mínima entre s i w passant per VIST.
  3. w no és successor, no és possible que el camí sigui més curt.. BLAH BLAH BLAH

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

VISTOS = {s}

forall v in V(g)                                        # O(n)

        D[v] = +INFINITY

end

D[s] = 0

forall v in Adj(G, s)                                # O(m)

        D[v] = w(s, v) // camí[v] = s

end

while VISTOS != V(G)                                # O(nlogn) + O(n+m) = O(mlogn)

        v = vèrtex ¬VIST amb D mínima                # [ O(logn) ] - amb un heap

        VISTOS = VISTOS + {u}                # [ O(1) ]

forall v’ in Adj(G, v)                        # [ O(logn * grau(v)) ] - logn per culpa de flotar el heap

                if D[v’] > D[v] + w(v, v’)

                        D[v’] = D[v] + w(v, v’) // camí[v’] = v

        end

endwhile

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Per poder implementar això ens cal una estructura de dades composta per la combinació d’un min-heap i un diccionari.


Codis de Huffman

        pi = probabilitat del símbol xi ()        li = longitud del codi assignat a x

Longitud mitjana de la codificació d’un caràcter:

Un codi de Huffman és un codi lliure de prefixos de longitud mitjana mínima. La seva representació natural és mitjançant un arbre binari; així, podem veure la longitud d’un codi com l’altura de l’arbre. Així, podem trobar un codi de Huffman construïnt un arbre des de baix ajuntant les lletres i subarbres (construïts fins al moment) de probabilitat menor.

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

struct node {

        char info;

        node *left, *right;

        node(char c): info(c), left(NULL), right(NULL) { }

};

typedef node* tree;

tree build_code(const vector<double>& w, const vector<char>& c) {

        priority_queue<double, tree> Q;

        for (int i = 0; i < w.size(); ++i) {

        tree t = new node(c[i]);

                Q.insert(w[i], t);

        }

while (Q.size() > 1) {                                                # O(nlogn)

        tree t1 = Q.find_min(); double w1 = Q.prio_min();

        Q.del_min();

        tree t2 = Q.find_min(); double w2 = Q.prio_min();

        Q.del_min();

        tree t = new node(NULL); t->left = t1; t->right = t2;

        Q.insert(w1+w2, t);

}

return Q.find_min();

}
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Demostració:

Tenim els símbols x1, x2, x3, …, xn (de menys freqüent a més freqüent). Per inducció:


Programació dinàmica

El principi d’optimalitat de Bellman ens diu que en alguns problemes, «donada una seqüència òptima de decisions, les seves subseqüències també ho són». Així podem trobar l’òptim a partir de decisions més petites. El problema és que haurem de resoldre varis cops els mateixos subproblemes recorrents. Per evitar-ho veurem: memoizació, tria de l’ordre de resolució dels subproblemes, desigualtat quadrangular.

Algorisme de Floyd

Tenim un graf amb V={1, …, n} on volem trobar les distàncies entre tots els vèrtex.

Definim: :

Tenim la següent recorrència:

Implementació:

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

// Inicialitzar Dprev                                # O(n^2)

for (int k = 1; k <= n; ++k) {                        # O(n^3)

for (int u = 1; u <= n; ++u)

for (int v =1; v <= n; ++v)

                        D[u][v] = min(Dprev[u][v], Dprev[u][k] + Dprev[k][v]);

}

Dprev = D;

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

De fet, amb una sola matriu en tenim prou, ja que  i   (ja que l’únic node involucrat és k).

L’algorisme de Floyd és molt simple d’implementar i té temps . En canvi, aplicar n cops una implementació eficient de l’algorisme de Dijkstra () té temps . Floyd és preferible per a grafs molt densos (on m és gran).

Si volem saber no només el cost sinó també els camins, hem de recordar l’última k on hem reduït el valor de ; en altres paraules, el menor valor de k tal que .

Problema de la motxilla (Knapsack)

vi = «valor de l’objecte i»,                         xi és 1 si l’objecte es posa a la motxilla

wi = pes de l’objecte i,                                 i 0 en cas contrari.

C = capacitat de la motxilla,                         

Volem  tal que .

Definim  «el valor màxim al que es pot arribar amb els objectes de l’1 al i per a una motxilla amb capacitat j».

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

# Cost temporal:

# Cost espacial:

for (int j = 0; j <= C; ++j)

        U[0][j] = 0;

for (int i = 1; i <= n; ++i) {

        for (int j = 0; j <= C; ++j) {

                if (j >= w[i] and v[i] + U[i-1][j-w[i]] > U[i-1][j]) U[i][j] = V[i]+U[i-1][j];

else U[i][j] = U[i-1][j];

                }

        }

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

De forma similar a l’algorisme de Floyd, podem reduir el cost espacial. En aquest cas, tenim prou amb una matriu uni-dimensional (millorant el cost espacial a ). Canviem el bucle interior per:

        for (int j = C; j >= 0; --j) {

                //

        if (j >= w[i] and v[i] + U[j-w[i]] > U[j]) U[j] = U[j - w[i]] + V[i];

                }

Per saber quins elements cal posar a la motxilla, necessitem la versió inicial del bucle (amb la matriu bi-dimensional). Llavors, si U[n][C]=U[n-1][C] vol dir que no es posa n a la motxilla, si si U[n][C]>U[n-1][C] llavors sí que es posa. El cost de reconstruir els objectes és .

Fixem-nos que C és exponencial respecte a n (ja que la mida de l’entrada C no és proporcional al propi C, sinó al nombre de bits de l’entrada, logC). Per això el problema és NP-Complet.

Optimització d’arbres amb probabilitats d’accés als nodes

Tenim un arbre t

S = {x1, x2, …, xn}

x0=-infty < x1 < x2 < x3 < … < xn < xn+1=+infty

ßi = Prob {accés a xi}, 1 <= i <= n

 = Prob {accés a (xi-1xi)}, 1 <= i <= n+1

p = ()

Longitud mitjana dels camins en t:

L(t, p) =

ai = profunditat de la fulla i-èssim en t

bi = profunditat del node i-èssim en t

L(tOPTIM, p) =

Sij = {xi, xi+1, …, xj}

p’ = (alphai’, …, alphaj+1’, ßi’, …, ßj’)

alphal’ = alphal / Wij ; ßl’ = ßl / Wij

tij = arbre òptim per a Sij

Cij = L(tij, p’)

wij =

  1. Ci, j-1 = 0
  2. Cij =

Cij =

wij·cij =

WijCij =

WijCij=Wij+Wi,m-1·Ci,m-1+Wm+1,j·Cm+1,j

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

for (int i = 1; i <= n; ++i) {

        W[i][i-1] = 0;

        for (int j = i; j <= n; ++j)

                W[i][j] = W[i][j-1] + alpha[j+1] + beta[j]

}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

for (int i = n; i >= 1; --i) {

        D[i][i-1] = 0;

        for (int j = i; j <= n; ++j)

                D[i][j] = +INFINITY;

                for (int m = i; m <= j; ++m) {

                        if (D[i][m-1]+D[m+1][j] < D[i][j]) {

                                D[i][j] = D[i][m-1]+D[m+1][j];

                                ROOT[i][j] = m;                        // per reconstruir l’arbre

                }

                D[i][j] += W[i][j];

        }

}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

struct node {

        …

        node *left, *right;

};

typedef node* bst;

bst reconstruir_bst(int i, int j, const vector<vector<int> >& ROOT) {

        if (i > j) return NULL;

        int m = ROOT[i][j];

        node *r = new node;

        r->info = x[m];

        r->left = reconstruir_bst(i, m-1, ROOT, ...):

        r->right = reconstruir_bst(m+1, j, ROOT, …);

        return r;

}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Cost en espai:        - W, ROOT, D        

Cost en temps        - W                

                - reconstruir_bst        

                - D                

Podem millorar el cost en temps de  a .

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

for (int m = ROOT[i][j-]; m <= ROOT[i+1][j]; ++m

        ROOT[i][j] = m;

D[i][j] += W[i][j]

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Problema d’optimització de segells/monedes

Tenim n tipus de segells, amb valors v1, v2, …, vn, tals que . Volem aconseguir un valor  utilizant aquests tipus de segells. L’algorisme voraç només funcionarà si els tipus de segells disponibles compleixen unes certes propietats (per exemple que tots els valors comparteixin una mateixa base: 1, b, b2, b3, ...).

Quan no funciona el voraç podem utilitzar el següent algorisme:

C[w] = C(i, w)

Cprev[w] = C(i-1, w)

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

for (int w = 0; w <= V; ++w) {                // Espai:   Temps:

        C[w] = Cprev[w];

        for (int k = 1; k <= w/v[i]; ++k) {

                C[w] += Cprev[w-k*v[i]];

        }

        Cprev = C;

}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Podem millorar el temps a utilitzant la següent recurrència:

C(i, w) = C(i-1, w) + C(i, w-vi)

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

for (int w = 0; w <= V; ++w) {

        if (w >= v[i]) C[w] += C[w-v[i]];

}

return C[v];

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Regressió lineal

Cj = cost de la regressió segmentada dels punts p1, …, pj

Cn = el que busquem

                                

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

for (int i = 1; i <= n; ++i) {                // Cost temporal:         Cost temporal:

        E[i][i] = E[i][i+1] = 0;

        for (int j=i+2; j <= n; ++j)

                E[i][j] = ecm(P, i, j); // calculem aij, bij... amb les formules de dalt

}

vector<double> C(n+1);

C[1] = 0;

C[2] = penalty;

for (int j = 3; j <= n; ++j) {

        double min = E[1][j];

for (int i = 2; i <= j-1; ++i) {

        if (min > C[i-1]+E[i][j]) {

                min = C[i-1]+E[i][j];

        }

}

C[j] = min + penalty;

}

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Mitjançant programació dinàmica és possible reduir el cost a .

Fluxos sobre xarxes i programació lineal

Una xarxa és un graf dirigit G=<V,E> que té un node font (source)  que no té predecessor (), un node desaigua (sink)  que no té successors (), on tot vèrtex  és incident al menys a un arc ( o ) i tenim capacitats assignades als arcs .

Un flux f sobre una xarxa és una funció    tal que

  1.   (condicions de capacitat)
  2.  (v: vèrtex intern),  (condicions de conservació del flux).

Notació

  1.  - flux entrant
  2.  - flux sortint
  3. , ;

La font “genera” flux si . El desaigua “absorveix” flux si .

Problema: El valor  d’un flux  és . Donada una xarxa R, volem trobar un flux  sobre R de valor màxim (max-flow).

Lema: Per tot flux , , .

Def: Un tall s-t en R és un parell <A,B> tal que , , , .

Def: La capacitat  d’un tall s-t <A,B> és .

Lema:

Per tot flux  i tot tall s-t <A,B> es compleix .

Dem:         

        

        


  1. f(x,y)        forma part de f
    out(x)
    -f(x,y)        forma part de f
    in(y)

  2. (al revés que en a)

  3. f(x,y)

  4. -f(x,y)

Teorema: per tot flux  i tot tall s-t <A,B> .

.

Corrolari 1:

Corrolari 2:

Teorema (MAXFLOW-MINCUT)

Per tota xarxa R el valor del flux màxim f* és igual a la capacitat del tall mínim en R <A*, V\A*>. v(f*)=c(A*, V\A*).

Algorisme de Ford-Fulkerson (1956)

Def: Graf residual Gf

Donat un flux sobre G, el graf residual  té el mateix conjunt de vèrtex que G i el conjunt d’arcs   es defineix:

  1. si  i   llavors  tal que  (arcs d’avanç, forward edges)
  2. si  i  llavors  tal que  (arcs de retrocès, backward edges).

Def: Sigui P un camí simple (on no es visita dos cops un mateix vèrtex) d’ a  en , .

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

augmentar(P, f)

        b = bottleneck(P,f)

        f’ = f

per tot e=(u,v)) en P:

        si e és un forward edge llavors:

                f’(e) = f(e)+b

        sinó:

                // e és un backward edge

                f’((v,u)) = f((u,v)) - b

        fsi

fper

retorna f’

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Algorisme de Ford-Fulkerson:

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

per tot e en E(g):

        f(e) = 0

fper

Gf = G

mentre existeixin camins d’s a t en Gf:

        P <- eligir un camí d’s a t en Gf

        f’ = augmentar(P, f)

        f = f’ // actualitzar Gf

fmentre

return f

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

...

Exercici de fiabilitats

Recorrència bàsica:

on  compleix .

Cost: temporal , espacial .

Recorrència de com l’he implementat jo:

Alternativa:  on  és el cost del component més barat.

Cost: temporal i espacial .

Programació lineal (LP)

x1 = # de litres de vi del tipus A per setmana                x2 = # de litres de vi del tipus B per setmana

u1 = benefici per litre                                        u2 = benefici per litre

M1 = màx. # de litres de vi del tipus A

M2 = màx. # de litres de vi del tipus B

M = màx. # de litres per setmana

x1 >= 0   (1)                x1 <= M1   (3)

x2 >= 0   (2)                x2 <= M2   (4)                x1+x2 <= M   (5)

Volem maximizar la funció objectiu x1u1+x2u2. (Per exemple, en un cas u1 = 1, u2 = 6, M1 = 200, M2 = 300, M = 400). Els possibles resultats són:

  1. No existeixen solucions factibles. Cap  satisfà simultàniament totes les restriccions.
  2. La regió de factibilitat no està acotada i la funció objectiu pot ser  (màx) o  (min).
  3. La regió de factibilitat no està buida, està acotada i existeix un vèrtex de la regió de factibilitat (polítop) que és una solució òptima.

L’algorisme simplex comença en un vèrtex qualsevol i es mou a un vèrtex adjacent que augmenti la funció adjacent, fins que arriba a l’òptim.

Variacions de LP

  1. Maximització / minimització

  2. Igualtats / desigualtat

  1. on
     és una variable de «slack» o «dèficit».

  2. on
     és una variable de «superàvit».
  1. Restricció de positivitat
  1. Substituir tota aparició d’ en LP per .

Amb aquests canvis podem convertir un LP a la «forma estàndard».

-   -   -   -

Volem , amb  i unes restriccions de la forma , …, .

                

En forma estàndard això ho expressem de la següent forma (on v són vectors):

max cT·x

x >= 0

A·x <= b

Si tenim un problema primal de maximització, el seu problema dual és un problema de minimització que per cada variable del problema primal té una restricció i a l’inrevés.

Problema primal

max x1+6x2

x1 <= 200

x2 <= 300

x1+x2 <= 400

x1 >= 0

x2 >= 0

Problema dual


min 200y
1+300y2+400y3

y1+y3 >= 1

y2+y3 >= 6

y1, y2, y3 >= 0

Propietat: qualsevol solució factible del dual té un valor objectiu que acota superiorment el valor objectiu de qualsevol solució factible del primal.

Coroŀlari: si el valor objectiu d’una solució factible del primal és igual al valor objectiu d’una solució factible llavors són solucions òptimes per al primal i el dual.

Podem representar el problema dual com:

min bT·y

y >= 0

yT·A >= c

Algorisme Simplex (Dantzing, 1947)

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

v = vèrtex de la regió factible

mentre existeix un vèrtex v’ adjacent a v tal que el seu objectiu és major que el de v, fes

        // cTv’ >= cTv

        v = v’

fmentre

- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -

Pot arribar a tenir cost exponencial, però a la pràctica això no pasa.

Altres algorismes:

Problema ILP

El problema de LP amb una restricció addicional d’integritat () és NP-hard, ja que permet solucionar el problema de la motxilla.