Kombinatorisk eksplosion

Kombinatorisk eksplosion er et udtryk, der bruges til at beskrive effekten af ​​en skarp ("eksplosiv") stigning i tidskompleksiteten af ​​en algoritme med en stigning i størrelsen af ​​problemets inputdata [1] .

Mere præcist betyder dette, at den algoritme, der overvejes, ikke er polynomiel, det vil sige, at tiden til at løse problemet ikke er begrænset af noget polynomium i længden af ​​input. Typisk har sådanne problemer eksponentiel eller endda supereksponentiel kompleksitet.

Navnets oprindelse skyldes, at der ikke findes en anden måde at løse problemet på. , bortset fra en komplet opremsning af alle mulige muligheder. I dette tilfælde er den tid, der kræves for løsningen, proportional med antallet af alle mulige konfigurationer, som bestemmes ud fra visse kombinatoriske overvejelser (kombinationer, permutationer).

For at omgå det kombinatoriske eksplosionsproblem søges specielle løsningsmetoder, især anvendes heuristiske algoritmer .

Eksempler

Kombinatorisk eksplosion forekommer i mange søgeproblemer [2] , i rækkefølge beregningsproblemer løst ved brute force metoder . [3] [4]

Problemet med den rejsende sælger

I det klassiske rejsende sælgerproblem er det påkrævet at finde den optimale rækkefølge for at besøge byer af en rejsende sælger. Den eneste nøjagtige måde at løse problemet på er at gå gennem alle mulige ruter og vælge den, der tager mindst tid. Således viser kompleksiteten ved at løse det rejsende sælgerproblem at være proportional med antallet af alle mulige sekvenser af byer, som er givet af permutationsformlen:

Skak

Så for eksempel er det hypotetisk muligt at beregne alle muligheder for træk i brætspillet skak fra begyndelsen af ​​spillet til slutningen ved en komplet opregning af alle kombinationer. Men i øjeblikket og i den nærmeste fremtid [2] er det praktisk talt umuligt at løse et sådant problem. For eksempel, for en computer, der er i stand til at beregne en million spilkombinationer pr. sekund med eliminering af åbenlyst ikke-optimale grene , vil det tage 1 sekund at beregne 6 træk frem, 11 dage for 12 træk og omkring 32.000 år for 18 træk. [2]

Noter

  1. ↑ Webordbog over kybernetik og systemer . Dato for adgang: 29. maj 2010. Arkiveret fra originalen 6. august 2010.
  2. ↑ 1 2 3 A Dictionary of Computing . Dato for adgang: 29. maj 2010. Arkiveret fra originalen 8. juni 2013.
  3. ↑ Artikler om kunstig intelligens . Hentet 29. maj 2010. Arkiveret fra originalen 23. august 2011.
  4. ↑ Denys Duchier, Claire Gardent og Joachim Niehren. Samtidig begrænsningsprogrammering i Oz til naturlig sprogbehandling . Dato for adgang: 29. maj 2010. Arkiveret fra originalen 12. august 2011.