Kombinatorinen räjähdys

Kombinatorinen räjähdys on termi, jota käytetään kuvaamaan jyrkän ("räjähdysmäisen") kasvun vaikutusta algoritmin aikamonimutkaisuuteen, kun ongelman syöttödatan koko kasvaa [1] .

Tarkemmin sanottuna tämä tarkoittaa, että tarkasteltavana oleva algoritmi ei ole polynomi, eli tehtävän ratkaisuaikaa ei rajoita mikään syötteen pituuden polynomi. Tyypillisesti tällaisilla ongelmilla on eksponentiaalinen tai jopa supereksponentiaalinen monimutkaisuus.

Nimen alkuperä johtuu siitä, että muuta tapaa ongelman ratkaisemiseksi ei löydy. , paitsi täydellinen luettelo kaikista mahdollisista vaihtoehdoista. Tässä tapauksessa ratkaisun vaatima aika on verrannollinen kaikkien mahdollisten konfiguraatioiden lukumäärään, joka määräytyy tietyistä kombinatorisista näkökohdista (yhdistelmät, permutaatiot).

Kombinatorisen räjähdysongelman ohittamiseksi etsitään erityisiä ratkaisumenetelmiä, erityisesti heuristisia algoritmeja .

Esimerkkejä

Kombinatorinen räjähdys esiintyy monissa hakuongelmissa [2] , raa'an voiman menetelmillä ratkaistavissa sekvenssilaskentaongelmissa . [3] [4]

Matkamyyjän ongelma

Klassisessa matkustavamyyjä-ongelmassa on löydettävä optimaalinen järjestys matkustavan myyjän kaupungeissa vierailuille. Ainoa tarkka tapa ratkaista ongelma on käydä läpi kaikki mahdolliset reitit ja valita se, joka vie vähiten aikaa. Siten matkustavan myyjän ongelman ratkaisemisen monimutkaisuus osoittautuu verrannolliseksi kaikkien mahdollisten kaupunkijonojen lukumäärään, joka saadaan permutaatiokaavalla:

Shakki

Joten esimerkiksi on hypoteettisesti mahdollista laskea kaikki siirtovaihtoehdot shakin lautapelissä pelin alusta pelin loppuun laskemalla kaikki yhdistelmät täydellisesti. Kuitenkin tällä hetkellä ja lähitulevaisuudessa [2] tällaista ongelmaa on käytännössä mahdotonta ratkaista. Esimerkiksi tietokoneessa, joka pystyy laskemaan miljoona peliyhdistelmää sekunnissa ja eliminoimalla ilmeisen epäoptimaaliset haarat , kestää 1 sekunti laskea 6 siirtoa eteenpäin, 11 päivää 12 siirtoa varten ja noin 32 000 vuotta 18 siirtoa varten. [2]

Muistiinpanot

  1. ↑ Kybernetiikan ja järjestelmien verkkosanakirja . Käyttöpäivä: 29. toukokuuta 2010. Arkistoitu alkuperäisestä 6. elokuuta 2010.
  2. ↑ 1 2 3 Tietojenkäsittelyn sanakirja . Käyttöpäivä: 29. toukokuuta 2010. Arkistoitu alkuperäisestä 8. kesäkuuta 2013.
  3. ↑ Tekoälyä käsitteleviä artikkeleita . Haettu 29. toukokuuta 2010. Arkistoitu alkuperäisestä 23. elokuuta 2011.
  4. ↑ Denys Duchier, Claire Gardent ja Joachim Niehren. Samanaikainen rajoitusohjelmointi Ozissa luonnollisen kielen käsittelyyn . Käyttöpäivä: 29. toukokuuta 2010. Arkistoitu alkuperäisestä 12. elokuuta 2011.