Busca de força bruta

Archiu:חידת שמונה המלכות.jpg

El problema de les huit reines pot ser resolt per força bruta, pero no és adequat per l'elevat número de combinacions possibles.

En informàtica, la busca per força bruta, busca combinatòria, busca exhaustiva o simplement força bruta és una tècnica trivial pero a sovint usada, que consistix en enumerar sistemàticament tots els possibles candidats per a la solució d'un problema, en la finalitat de chequear si dit candidat satisfà la solució al mateix.

Per eixemple, un algoritme de força bruta per a trobar el divisor d'un número natural n consistiria en enumerar tots els sancers des d'1 fins a n, chequeando si cada u d'ells dividix n sense generar restant. Un atre eixemple de busca per força bruta, en este cas per a solucionar el problema de les huit reines (posicionar huit reines en el tauler d'escacs de manera que cap d'elles atac al restant), consistiria en examinar totes les combinacions de posició per a les 8 reines (en total 64!/8!(64-8)! = 4.426.165.368 posicions diferents), comprovant en cada una d'elles si les reines s'ataquen mútuament.

La busca per força bruta és senzilla d'implementar i, sempre que existixca, troba una solució. No obstant, el seu cost d'eixecució és proporcional al número de solucions candidates, el qual és exponencialment proporcional al tamany del problema. Pel contrari, la busca per força bruta s'usa habitualment quan el número de solucions candidates no és elevat, o be quan este pot reduir-se prèviament usant algun atre método heurístic.

És un método utilisat també quan és més important una implementació senzilla que una major rapidea. Est pot ser el cas en aplicacions crítiques a on qualsevol error en l'algoritme pot carrejar séries conseqüències; també és útil com a método "base" quan es desija comparar l'eixercite d'atres algoritmes metaheurísticos. La busca de força bruta pot ser vista com el método metaheurístico més simple.

La busca per força bruta no es deu confondre en backtracking, método que descarta un gran número de conjunts de solucions, sense enumerar explícitament cada una de les mateixes.

Implementació de la busca per força bruta

Algoritme bàsic

Per a poder utilisar la busca per força bruta a un tipo específic de problema, es deuen implementar les funcions primer, següent, valgut, i mostrar. Totes arreplegaran el paràmetro P indicant una instància en particular del problema:

1. primer (P): genera la primera solució candidata per a P.
2. següent (P, c): genera la següent solució candidata per a P despuix d'una solució candidata c.
3. valgut (P, c): chequea si una solució candidata c és una solució correcta de P.
4. mostrar (P, c): informa que la solució c és una solució correcta de P.

La funció següent deu indicar d'alguna forma quàn no existixen més soluciones candidates per al problema P despuix de l'última. Una forma de realisar açò consistix en tornar un valor "nul". D'esta mateixa forma, la funció primer tornarà un valor "nul" quan no existixca cap solució candidata al problema P.

Usant tals funcions, la busca per força bruta s'expressa per mig del següent algoritme:

c $\leftarrow$ primer(P)
mentres c != null
  si valgut(P,c) llavors mostrar(P, c)
  c $\leftarrow$ següent(P,c)

Per eixemple, per a buscar els divisores d'un sancer n, l'instància del problema P és el propi número n. la cridada primer (n) tornarà 1 sempre i quan n $\ge$ 1, i "nul" en un atre cas; la funció següent (n,c) deu tornar c + 1 si c $<$ n, i "nul" cas contrari; vàlit (n,c) tornarà verdader si i solament si c és un divisor de n.

Variacions comunes en l'algoritme

L'algoritme descrit anteriorment crida a la funció mostrar per a cada solució al problema. Est pot ser fàcilment modificat de manera que termine una volta trobe la primera solució, o be despuix de trobar un determinat número de solucions, despuix de provar en un número específic de solucions candidates, o despuix d'haver consumit una cantitat fixa de temps de CPU.

Explosió combinacional

La principal desventaja del método de força bruta és que, per a la majoria de problemes reals, el número de solucions candidates és prohibitivamente elevat.

Per eixemple, per a buscar els divisores d'un número n tal i com es descriu anteriorment, el número de solucions candidates a provar serà de n. Per tant, si n consta de, digam, 16 dígits, la busca requerirà d'a lo manco 10¹⁵ comparacions computacionals, tasca que pot tardar varis dies en un ordenador personal. Si n és un bit de 64 dígits, que aproximadament pot tindre fins a 19 dígits decimals, la busca pot tardar de l'orde de 10 anys.

Este creiximent exponencial en el número de candidats, quan creix el tamany del problema ocorre en tot tipo de problemes. Per eixemple, si busquem una combinació particular de 10 elements llavors tindrem que considerar 10! = 3,628,800 candidats diferents, la qual cosa en un PC habitual pot ser generat i provat en menys d'un segon. No obstant, afegir un únic element més —la qual cosa supon solament un 10% més en el tamany del problema— multiplicarà el número de candidats 11 voltes — lo que supon un 1000% d'increment. Per a 20 elements el número de candidats diferents és 20!, és dir, aproximadament 2.4×10¹⁸ o 2.4 millons de millons de millons; la busca podria tardar uns 10 000 anys. A este fenomen no desijat se li denomina explosió combinacional.

Vore també

• Atac de força bruta
• Cota superior asintòtica