Apunts d’Estructures de Dades i Algorismes: Cerca exhaustiva

Cerca exhaustiva

La cerca exhaustiva és un mètode de disseny d'algorismes que consisteix en mirar-se sistemàtica i intel·ligentment totes les possibles solucions a un problema donat.

Generalment els problemes que es resolen mitjançant aquesta tècnica són problemes d'optimització o combinatoris.

La tècnica consisteix en generar implícitament un arbre representant totes les possibles solucions i explorar-lo en profunditat, deixant de recórrer aquelles branques que corresponguin a «candidats a solució» que no compleixen les restriccions del problema donat. Nosaltres la veurem per backtracking.

Exemple. El problema de les «n» reines

Donat un tauler d'[latex]n[/latex]x[latex]n[/latex] caselles i [latex]n[/latex] reines, cal situar-les de manera que no s'amenacin entre elles (segons les regles dels escacs). Vés aquí algunes opcions:

  1. Podem mirar totes les possibles configuracions i veure quines compleixen les restriccions del problema. Això són [latex]n^2 \choose n[/latex] combinacions; amb [latex]n=8[/latex] això són [latex]{64 \choose 8} = 4426165368[/latex] possibilitats.
  2. Podem limitar-nos a posar una única reina en cada línia. Això són [latex]n^n[/latex] possibilitats; amb [latex]n=8[/latex], [latex]8^8 = 16777216[/latex].
  3. Podem posar una única reina en cada fila i columna. Això són [latex]n![/latex] possibilitats; amb [latex]n=8[/latex], [latex]8! = 40320[/latex].
  4. Podem posar una única reina en cada fila, columna i diagonal.

El problema amb aquestes propostes és que fins que no hem acabat de construir una configuració no es mira si les condicions es compleixen o no. Ja en podríem desestimar moltes mentre s'estan construint: utilitzem la tècnica del backtracking.

Una part important d'aquesta tècnica consisteix en determinar una manera per a representar les possibles configuracions (solucions) del problema. En el cas de les reines, ho farem amb una taula d'[latex]n[/latex] posicions, tal que [latex]v[i][/latex] és la columna on va la reina i que al tauler anirà en [latex](i, v[i])[/latex].

Definim un vector [latex]k[/latex]-completable de la següent manera: sigui [latex](k-1)[/latex]-completable, i [latex]\forall i\ tal\ que\ 1 \le i \le k-1, v[i] \ne v[k], i + v[i] \ne k + v[k], n – v[i] + i \ne n – v[k] + k[/latex]. Les solucions al problema de les [latex]n[/latex] reines són els vector [latex]n[/latex]-completables.

Observacions:

  1. [latex]i \ne j, \forall 1 \le i, j \le k, v[i] \ne v[j], v[i] + i \ne v[j] + j,[/latex] [latex]n – 1 – v[i] + i \ne n – 1 – v[j] + j[/latex] (les dues darrers condicions cobreixen les diagonals).
  2. El vector ha de ser [latex](k – 1)[/latex]-completable i, a més, [latex]\forall 1 \le i \le k – 1, v[i] \ne v[k], v[i] + i \ne v[k] + k, n – 1 – v[i] + i \ne n -1 – v[k] + k[/latex].
  3. Tots els vectors són [latex]1[/latex]-completables.
  4. Les solucions al problema són els vectors n-completables.
Exemple. El problema de la motxilla

«Una motxilla té lloc per a C unitats de pes. Tria d'entre [latex]n[/latex] objectes amb pesos [latex]p[i], …, p[n][/latex] i valor [latex]v[i], …, v[n][/latex] la combinació d'objectes amb pes total inferior a C amb el valor màxim».

Apunts d’Estructures de Dades i Algorismes: Grafs

Definició i propietats

Graf:
[latex]\begin{array}{lll}G: & \small V\grave{e}rtexs/Nodes & V = \{1, 2, 3, 4\} \\ & \small Arestes & E = \left\{\{1, 2\}, \{1, 3\}, \{2, 3\}, \{3, 4\}\right\}\end{array}[/latex]

Graf dirigit (digraf):
[latex]\begin{array}{lll}G': & \small V\grave{e}rtexs/Nodes & V = \{1, 2, 3, 4\} \\ & \small Arcs & E \subset VxV\ \small (un\ arc\ \acute{e}s\ un\ parell\ ordenat\ de\ v\grave{e}rtexs)\\ & & E = \left\{(1, 2), (1, 3), (2, 3), (3, 4)\right\}\end{array}[/latex]

Un camí de longitud [latex]l[/latex] és una seqüència de vèrtexs connectats (per arrestes/arcs) entre ells. Si tots els vèrtexs són diferents, el camí és simple. Un cicle és un camí simple amb la peculiaritat que comença i acaba al mateix vèrtex.

El diàmetre d'un graf és el màxim de tots els camins mínims.

Diem que un graf [latex]G = (V, E)[/latex] és connex si per tot parell de vèrtexs [latex]u, v \in V[/latex] existeix un camí que comença en [latex]u[/latex] i acaba en [latex]v[/latex].

Un graf no dirigit, connex i acíclic (sense cicles) és un arbre (arbre lliure); és un graf no dirigit on hi ha exactament un camí entre cada parell de vèrtexs. Els arbres tenen les següents propietats:

  • un arbre amb [latex]n[/latex] vèrtex té [latex]n – 1[/latex] arestes;
  • si s'afegeix una aresta a un arbre llavors tindrà un (únic) cicle;
  • si s'elimina una aresta d'un arbre llavors deixa de ser connex.

Continue reading →

Apunts d’Estructures de Dades i Algorismes: Diccionaris

Introducció

Són un tipus abstracte de dades (TAD), és a dir, un conjunt d'elements i un conjunt d'operacions sobre ells.

Un diccionari és un conjunt d'elements amb una clau associada (treta d'un conjunt amb un ordre total definit) amb les operacions de cercar, inserir i esborrar un element.

Una estructura de dades és una estructura que ens permet implementar TAD.

Implementacions de diccionaris

1) Taules (no ordenades)
  • Inserir un element nou: [latex]\theta(1)[/latex].
  • Esborrar un element: cost de cercar l'element ([latex]O(n)[/latex]) + cost de treure'l de la taula (varia segons el mecanisme d'eliminació, possiblement [latex]O(n)[/latex]).
2) Llistes (enllaçades, encadenades)

Per recórrer una llista s'ha de fer de forma seqüencial, mitjançant iteradors (punters).

  • Inserir un element nou:
      – al principi: [latex]\theta(1)[/latex];
      – al final de la llista, recorrent-la sencera: [latex]\theta(n)[/latex].
  • Cercar un element: [latex]O(n)[/latex]
  • Esborrar un element: [latex]O(n)[/latex]
3) Taules de dispersió (hash tables)

El disseny de la funció de hash és molt important per obtenir taules ben equilibrades.

En cas pitjor, el cost serà de [latex]\theta(n)[/latex], inserint al final amb una funció de dispersió que resulti en llistes llargues. Però, si la funció de dispersió està ben dissenyada, repartirà els elements equitativament, resultant llistes de mitjana [latex]\alpha = \frac{n}{M}[/latex] amb un cost [latex]\theta(\alpha)[/latex].

Continue reading →

Apunts d’Estructures de Dades i Algorismes: Dividir i Vèncer

Introducció

L'esquema de programació de dividir i vèncer és una tècnica per a resoldre problemes que consisteix en dividir el problema original en subproblemes (més petits), resoldre els subproblemes i finalment combinar les solucions en una sola que resolgui el problema original. Mitjançant aquest tècnica sovint obtenim una solució recursiva.

Exemples

  1. Cerca dicotòmica: [latex]T(n) = O(log n)[/latex]
  2. Exponenciació ràpida: [latex]T(n) = \theta(log n)[/latex]
    [latex]x^n = \begin{cases}1 & n = 0 \\ (x^2)^{\frac{n}{2}} & n \gt 0, n\ \acute{e}s\ parell \\ x \cdot (x^2)^{\left\lfloor \frac{n}{2} \right\rfloor} & n \gt 0, n\ \acute{e}s\ senar\end{cases}[/latex]
  3. Merge sort: [latex]T(n) = \theta(n log n)[/latex]
  4. Quick sort (inventat el 1960 per Hoare): [latex]T(n) = \begin{cases}\small cas\ millor: & 2T(\frac{n}{2}) + \theta(n) & \rightarrow \theta(n log n) \\ \small cas\ mitj\grave{a}: & \frac{1}{n}\sum_{i=1}^{n}T(i) + T(n-i) + \theta(n) & \Rightarrow \theta(n log n) \\ \small cas\ pitjor: & c + T(n – 1) + \theta(n) & \Rightarrow \theta(n^2)\end{cases}[/latex]

    Consististeix en agafar un pivot [latex]x[/latex] i dividir l'entrada en aquells elements [latex]\le x[/latex] i aquells [latex]\ge x[/latex], i repetir aquest procediment de forma recursiva en els dos grups. En la definició de [latex]T(n)[/latex], [latex]i[/latex] representa el nombre d'elements [latex]\le x[/latex] i depèn del pivot.

    Nota: La llibreria estàndard de C++ disposa d'una implementació de l'algorisme Introsort, que ordena amb quick sort però compta el nombre de crides recursives. A partir d'un cert nombre [latex]c_{2} \cdot log n[/latex] canvia a heap sort.

  5. Quick Select (selecció del [latex]k[/latex]-èssim element d'una taula desordenada)

    [latex]T(n) = \begin{cases}\small cas\ millor\ i\ mitj\grave{a}: & s(n) = s(\frac{n}{2}) + \theta(n) & \Rightarrow \theta(n) \\ \small cas\ pitjor: & s(n) = s(n – 1) + \theta(n) & \Rightarrow \theta(n^2)\end{cases}[/latex]

    Consisteix en agafar un pivot [latex]x[/latex], fer la partició i trobar la posició [latex]q[/latex] de l'element de més a la dreta del primer grup. Si [latex]q = k[/latex] llavors ja hem acabat (el [latex]k[/latex]-èssim és l'element [latex]T[q][/latex]); si [latex]q \lt k[/latex] cerquem l'element [latex]k – q[/latex] al segon grup; finalment, si [latex]q \gt k[/latex], cerquem l'element [latex]k[/latex]-èssim a T1.

    Nota: existeix un altre algorisme de selecció en temps lineal en el cas pitjor: Floyd-Wilson.

  6. Algorisme de Karasuba (per a multiplicar)

    L'algorisme per a multiplicar clàssic du a terme [latex]O(n^2)[/latex] operacions. L'algorisme de Karatsuba és més ràpid per a nombres molt grans.

    Sense pèrdua de generalitat: suposem nombres binaris, de la mateixa longitud i sent aquesta longitud una potència de 2. Per exemple, x = [a|b], y = [c|d].
    [latex](a \cdot 2^{\frac{n}{2}} + b) (c \cdot 2^{\frac{n}{2}} + d) = x \cdot y[/latex]
    [latex]u = (a+b) (c+d)\ \ \ \ v = a \cdot c\ \ \ \ w = b \cdot d[/latex]
    [latex]x \cdot y = v \cdot 2^n + (u – v – w) \cdot 2^(\frac{n}{2}) + w[/latex]

    [latex]T(n) = 3T(\frac{n}{2}) + \theta(n) \Rightarrow T(n) = \theta(n^{log_{2}3 \simeq 1.585})[/latex]

Alguns apunts addicionals:

  • El merge sort (implementat correctament) és un algorisme d'ordenació estable, amb el quick sort aquest no és el cas.
  • L'algorisme quick sort cau en el seu temps pitjor quan l'entrada ja està ordenada.

Implementació del quick sort

int partició<vector<elem>& v, int e, int d) {
    // Hoare
    Elem x = v[e];
    int i = e - 1;
    int j = d + 1;
    while (true) {
        while (v[--j] > x);
        while (v[++i] < x);
        if (i >= j) return j;
        swap (v[i], v[j]);
    }
}
void quicksort(vector<elem>& v, int e, int d) {
    if (e < d) {
        int p = partició(v, e, d);
        quicksort(v, e, p);
        quicksort(v, p+1, e);
    }
}

Enllaços rellevants

Apunts d’Estructures de Dades i Algorismes: Càlcul de costs

Introducció

Els algorismes són per tot arreu i per això volem analitzar-ne les característiques. Algunes de les característiques més importants dels algorismes són:

  • correctesa!
  • senzillesa
  • escalabilitat
  • modularitat
  • eficiència
  • fiabilitat
  • etc.



Nosaltres en concret en mirarem l'eficiència i l'ús dels recursos del sistema a nivell teòric, és a dir, el temps d'execució, la quantitat de memòria que utilitzen, etc.


Suposarem que el cost de totes les operacions elementals és constant, i anomenem «n» la mida de l'entrada, en funció de la qual veurem el cost en temps i memòria dels algorismes.

Def. Donat un algorisme A, amb conjunt d'entrades [latex]\vartheta[/latex], el seu cost (eficiència) és una funció: [latex]\begin{array}{ll}T: & \vartheta \rightarrow \mathbb{R}^{+} \\ & \alpha \mapsto T(\alpha)\end{array}[/latex]

Per facilitar la manipulació de cost restringim el conjunt [latex]\vartheta[/latex] al conjunt [latex]\vartheta_{n}[/latex], que correspon al de totes les entrades de mida [latex]n \in \mathbb{R}[/latex].

Def. Donat un algorisme A, amb un conjunt d'entrades de mida n (\(\vartheta_{n}\)), el cost d'A en el cas millor, pijtor i mitjà és:

  • [latex]T_{millor}(n) = min\left\{T_{n}(\alpha) | \alpha \in \vartheta_{n}\right\}[/latex]
  • [latex]T_{pitjor}(n) = max\left\{T_{n}(\alpha) | \alpha \in \vartheta_{n}\right\}[/latex]
  • [latex]T_{mitj\grave{a}}(n) = \sum_{\alpha \in \vartheta_{n}} Pr(\alpha) \cdot T_{n}(\alpha)[/latex]
    (suposant un coneixement de la distribució estadística de les entrades)

Observacions:

  • [latex]T_{millor}(n) \le T_{n}(\alpha) \le T_{pitjor}(n)[/latex]
  • [latex]T_{millor}(n) \le T_{mitj\grave{a}}(n) \le T_{pitjor}(n)[/latex]

Continue reading →

 
Skip to toolbar