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».