Kombinatorisk explosion
Kombinatorisk explosion är en term som används för att beskriva effekten av en kraftig ("explosiv") ökning av tidskomplexiteten för en algoritm med en ökning av storleken på problemets indata [1] .
Mer exakt betyder detta att algoritmen i fråga inte är polynom, det vill säga tiden för att lösa problemet är inte begränsad av något polynom i längden på inmatningen. Typiskt har sådana problem exponentiell eller till och med superexponentiell komplexitet.
Namnets ursprung beror på att det inte går att hitta något annat sätt att lösa problemet. , förutom en fullständig uppräkning av alla möjliga alternativ. I detta fall är tiden som krävs för lösningen proportionell mot antalet av alla möjliga konfigurationer, vilket bestäms utifrån vissa kombinatoriska överväganden (kombinationer, permutationer).
För att kringgå det kombinatoriska explosionsproblemet eftersträvas speciella lösningsmetoder, i synnerhet används heuristiska algoritmer .
Exempel
Kombinatorisk explosion inträffar i många sökproblem [2] , i sekvensberäkningsproblem som löses med brute force- metoder . [3] [4]
Problemet med resande säljare
I det klassiska resandeförsäljarproblemet krävs det att hitta den optimala sekvensen för att besöka städer av en resande säljare. Det enda exakta sättet att lösa problemet är att gå igenom alla möjliga vägar och välja den som tar minst tid. Således visar sig komplexiteten för att lösa problemet med resande säljare vara proportionell mot antalet av alla möjliga sekvenser av städer, vilket ges av permutationsformeln:
Schack
Så, till exempel, är det hypotetiskt möjligt att beräkna alla alternativ för drag i brädspelet schack från början av spelet till slutet genom en fullständig uppräkning av alla kombinationer. Men för närvarande och i en nära framtid [2] är det praktiskt taget omöjligt att lösa ett sådant problem. Till exempel, för en dator som kan beräkna en miljon spelkombinationer per sekund med eliminering av uppenbart icke-optimala grenar , kommer det att ta 1 sekund att beräkna 6 drag framåt, 11 dagar för 12 drag och cirka 32 000 år för 18 drag. [2]
Anteckningar
- ↑ Web-ordbok över cybernetik och system . Tillträdesdatum: 29 maj 2010. Arkiverad från originalet den 6 augusti 2010.
- ↑ 1 2 3 A Dictionary of Computing . Datum för åtkomst: 29 maj 2010. Arkiverad från originalet den 8 juni 2013.
- ↑ Artiklar om artificiell intelligens . Hämtad 29 maj 2010. Arkiverad från originalet 23 augusti 2011.
- ↑ Denys Duchier, Claire Gardent och Joachim Niehren. Samtidig begränsningsprogrammering i Oz för naturlig språkbehandling . Tillträdesdatum: 29 maj 2010. Arkiverad från originalet den 12 augusti 2011.