Kombinatorikus robbanás
A kombinatorikus robbanás egy olyan kifejezés, amely az algoritmus időbonyolultságának éles ("robbanásszerű") növekedésének hatását írja le a probléma bemenő adatainak méretének növekedésével [1] .
Pontosabban ez azt jelenti, hogy a vizsgált algoritmus nem polinomiális, vagyis a probléma megoldásának idejét nem korlátozza a bemenet hosszában szereplő polinom. Az ilyen problémák általában exponenciális vagy akár szuper-exponenciális összetettséggel rendelkeznek.
A név eredete abból adódik, hogy a probléma megoldására más módot nem találunk. , kivéve az összes lehetséges opció teljes felsorolását. Ebben az esetben a megoldáshoz szükséges idő arányos az összes lehetséges konfiguráció számával, amelyet bizonyos kombinatorikus megfontolások (kombinációk, permutációk) alapján határoznak meg.
A kombinatorikus robbanás probléma megkerülésére speciális megoldási módszereket keresnek, különösen heurisztikus algoritmusokat alkalmaznak .
Példák
A kombinatorikus robbanás számos keresési feladatban [2] , nyers erő módszerekkel megoldott sorozatszámítási feladatokban fordul elő . [3] [4]
Az utazó eladó probléma
A klasszikus utazó eladó problémában meg kell találni az utazó eladó városlátogatásának optimális sorrendjét. A probléma megoldásának egyetlen pontos módja az, ha végigmegyünk minden lehetséges útvonalon, és kiválasztjuk azt, amelyik a legkevesebb időt vesz igénybe. Így az utazó eladó probléma megoldásának összetettsége arányosnak bizonyul a városok összes lehetséges sorozatának számával, amit a permutációs képlet ad meg:
Sakk
Így például hipotetikusan ki lehet számítani a sakktáblás játék összes lépésének lehetőségét a játék elejétől a végéig az összes kombináció teljes felsorolásával. Jelenleg és a közeljövőben [2] azonban gyakorlatilag lehetetlen megoldani egy ilyen problémát. Például egy olyan számítógépnél, amely másodpercenként millió játékkombinációt képes kiszámítani a nyilvánvalóan nem optimális ágak kiküszöbölésével, 1 másodpercbe telik a 6 előrelépés kiszámítása, 11 nap 12 lépésnél, és körülbelül 32 000 év 18 lépésnél. [2]
Jegyzetek
- ↑ Webes kibernetikai és rendszerszótár . Hozzáférés dátuma: 2010. május 29. Az eredetiből archiválva : 2010. augusztus 6..
- ↑ 1 2 3 A számítástechnikai szótár . Hozzáférés dátuma: 2010. május 29. Az eredetiből archiválva : 2013. június 8.
- ↑ Cikkek a mesterséges intelligenciáról . Letöltve: 2010. május 29. Az eredetiből archiválva : 2011. augusztus 23..
- ↑ Denys Duchier, Claire Gardent és Joachim Niehren. Párhuzamos kényszerprogramozás Oz nyelven természetes nyelvi feldolgozáshoz . Hozzáférés dátuma: 2010. május 29. Az eredetiből archiválva : 2011. augusztus 12.