Explozie combinatorie
Explozie combinatorie este un termen folosit pentru a descrie efectul unei creșteri bruște („explozive”) a complexității în timp a unui algoritm cu o creștere a dimensiunii datelor de intrare ale problemei [1] .
Mai precis, aceasta înseamnă că algoritmul luat în considerare nu este polinom, adică timpul de rezolvare a problemei nu este limitat de niciun polinom în lungimea intrării. De obicei, astfel de probleme au o complexitate exponențială sau chiar super-exponențială.
Originea numelui se datorează faptului că nu poate fi găsită o altă cale de a rezolva problema. , cu excepția unei enumerari complete a tuturor opțiunilor posibile. În acest caz, timpul necesar soluției este proporțional cu numărul tuturor configurațiilor posibile, care este determinat din anumite considerații combinatorii (combinații, permutări).
Pentru a ocoli problema exploziei combinatorii, se caută metode speciale de rezolvare, în special se folosesc algoritmi euristici .
Exemple
Explozia combinatorie apare în multe probleme de căutare [2] , în probleme de calcul secvențial rezolvate prin metode de forță brută . [3] [4]
Problema vânzătorului ambulant
În problema clasică a vânzătorului ambulant, este necesar să se găsească succesiunea optimă de vizitare a orașelor de către un vânzător ambulant. Singura modalitate exactă de a rezolva problema este să parcurgeți toate rutele posibile și să alegeți cea care durează cel mai puțin. Astfel, complexitatea rezolvării problemei vânzătorului ambulant se dovedește a fi proporțională cu numărul tuturor secvențelor posibile de orașe, care este dat de formula de permutare:
Șah
Deci, de exemplu, este ipotetic posibil să se calculeze toate opțiunile pentru mișcările din jocul de masă de șah de la începutul jocului până la sfârșit printr-o enumerare completă a tuturor combinațiilor. Cu toate acestea, în prezent și în viitorul apropiat [2] , este practic imposibil de rezolvat o astfel de problemă. De exemplu, pentru un computer capabil să calculeze un milion de combinații de joc pe secundă cu eliminarea ramurilor în mod evident neoptimale , va dura 1 secundă pentru a calcula 6 mutări înainte, 11 zile pentru 12 mutări și aproximativ 32.000 de ani pentru 18 mutări. [2]
Note
- ↑ Dicționar web de cibernetică și sisteme . Data accesului: 29 mai 2010. Arhivat din original pe 6 august 2010.
- ↑ 1 2 3 Un dicționar de calcul . Data accesului: 29 mai 2010. Arhivat din original pe 8 iunie 2013.
- ↑ Articole despre inteligența artificială . Preluat la 29 mai 2010. Arhivat din original la 23 august 2011.
- ↑ Denys Duchier, Claire Gardent și Joachim Niehren. Programare concomitentă de constrângeri în Oz pentru procesarea limbajului natural . Data accesului: 29 mai 2010. Arhivat din original la 12 august 2011.