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'x caselles i reines, cal situar-les de manera que no s'amenacin entre elles (segons les regles dels escacs). Vés aquí algunes opcions:
- Podem mirar totes les possibles configuracions i veure quines compleixen les restriccions del problema. Això són combinacions; amb això són possibilitats.
- Podem limitar-nos a posar una única reina en cada línia. Això són possibilitats; amb , .
- Podem posar una única reina en cada fila i columna. Això són possibilitats; amb , .
- 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' posicions, tal que és la columna on va la reina i que al tauler anirà en .
Definim un vector -completable de la següent manera: sigui -completable, i . Les solucions al problema de les reines són els vector -completables.
Observacions:
- (les dues darrers condicions cobreixen les diagonals).
- El vector ha de ser -completable i, a més, .
- Tots els vectors són -completables.
- 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 objectes amb pesos i valor la combinació d'objectes amb pes total inferior a C amb el valor màxim».
You are reading: Apunts d'Estructures de Dades i Algorismes
- Apunts d'Estructures de Dades i Algorismes: Càlcul de costs
- Apunts d'Estructures de Dades i Algorismes: Dividir i Vèncer
- Apunts d'Estructures de Dades i Algorismes: Diccionaris
- Apunts d’Estructures de Dades i Algorismes: Grafs
- Apunts d'Estructures de Dades i Algorismes: Cerca exhaustiva
- Apunts d'Estructures de Dades i Algorismes: Les classes de problemes P i NP
- Apunts d'Estructures de Dades i Algorismes: Programació dinàmica
