CS Challenge 10, Bus Solving

Nogle problemer er uundgåeligt svære

Foolish Earthlings, cannot solve the Bus problem!

Hvis man keder sig, når man kører i bus, kan man fordrive tiden med at spille Bus. I enhver af Midttrafiks busser er der to numre, som man kan se her:

Til venstre står buslinjen, i dette tilfælde linje 14. Til højre står busnummeret, som er en identifikation af køretøjet (der står på væggen over chaufføren). Spillet går ud på at lave et regnestykke af busnummerets enkelte cifre, der giver buslinjen som resultat. Alle cifre skal bruges netop een gang. Man må bruge følgende regneoperatorer:

Et ciffer angiver sin egen værdi.
Hvis exp₁ og exp₂ er regneudtryk, så er exp₁+exp₂ et regneudtryk, hvis værdi er summen af de to argumenter.
Hvis exp₁ og exp₂ er regneudtryk, så er exp₁-exp₂ et regneudtryk, hvis værdi er differencen mellem de to argumenter. Det er et krav, at resultatet ikke bliver negativt.
Hvis exp₁ og exp₂ er regneudtryk, så er exp₁*exp₂ et regneudtryk, hvis værdi er produktet af de to argumenter.
Hvis exp₁ og exp₂ er regneudtryk, så er exp₁/exp₂ et regneudtryk, hvis værdi er kvotienten mellem to argumenter. Det er et krav, at divisionen går op.
Hvis exp₁ og exp₂ er regneudtryk, så er exp₁^exp₂ et regneudtryk, hvis værdi er potensen af de to argumenter. Det er et krav, at både base og eksponent er 1-cifrede.
Hvis exp₁ og exp₂ er regneudtryk, så er exp₁@exp₂ et regneudtryk, hvis værdi er sammensætningen af de to argumenter. Fx er 64@719 = 64719
Hvis exp er et regneudtryk, så er S(exp) et regneudtryk, hvis værdi er summen af cifrene (mindst 2) i argumentet.
Hvis exp er et regneudtryk, så er P(exp) et regneudtryk, hvis værdi er produktet af cifrene (mindst 2) i argumentet.

Bemærk, at bussen på billederne er løselig, da:

14 = 3+S(2^7)

Hvis man kører i en bus med busnummer 244 og buslinje 17, så er der derimod ingen løsning.

Spørgsmål A

Afprøv spillet i praksis ved at køre med en af Midtrafiks busser. Nedskriv busnummer, buslinje og eventuel løsning. Angiv dato og tidspunkt for køreturen. Hint: dette spørgsmål er en joke.

Spillet kan oplagt generaliseres til at tillade vilkårligt mange cifre i busnummeret og buslinjen, og så bliver det et meget svært problem. Man kan faktisk bevise, at problemet (teknisk set eksistensen af en løsning) tilhører klassen af NP-fuldstændige problemer, som man formoder ikke har bedre algoritmer end at prøve alle muligheder, i vores tilfælde alle de mulige regneudtryk, der kan stilles op. Spillet deler denne status med mange vigtige datalogiske problemer og andre kendte spil som fx (generaliseret) Donkey Kong, Othello, Tetris og Rush Hour.

Spørgsmål B

Giv argumenter for, at antallet af mulige regneudtryk for et givet busnummer er eksponentielt i antallet af cifre, og at hvert regneudtryks størrelse er polynomielt i antallet af cifre.

Programmet Bus.java løser Bus spillet ved at generere og teste alle regneudtryk på en systematisk men økonomisk måde. Det kaldes fx således:

java Bus 732 14
14 = (3+S((2^7)))
Complexity = 189

Den angivne kompleksitet er antallet af deludtryk, der bliver beregnet undervejs, hvilket er en god målestok for sværhedsgraden af den aktuelle instans.

Spørgsmål C

Forklar, hvordan programmet virker med udgangspunkt i:

klassen Digits
variablen results
metoderne analyze og combine

Selv om problemet er uundgåeligt svært, er nogle løsninger bedre end andre, da de kan anvende heuristikker til at favorisere specialtilfælde og undgå overflødige beregninger. Bemærk, at en heuristik ikke kan ændre den uundgåelige kompleksitet, blot virke i nogle praktiske tilfælde.

Følgende tabel sammenligner den basale Bus algoritme med en bestemt heuristisk Bus algoritme, og forskellen på de to er klar:

Basal Bus Heuristisk Bus

java Bus 732 14 Complexity = 189

java Bus 732 14 Complexity = 69

java Bus 937 200 Complexity = 296

java Bus 937 200 Complexity = 296

java Bus 1234 56 Complexity = 756

java Bus 1234 56 Complexity = 612

java Bus 22222222 117 Complexity = 10356

java Bus 22222222 117 Complexity = 718

java Bus 1234321 1024 Complexity = 169251

java Bus 1234321 1024 Complexity = 104

java Bus 314159265358979323846264338327950288 8199 Complexity = 341

java Bus 22222222222222222222222 117 Complexity = 31516

java Bus 0123456789 3333 Complexity = 48924

Basal Bus	Heuristisk Bus
java Bus 732 14 Complexity = 189	java Bus 732 14 Complexity = 69
java Bus 937 200 Complexity = 296	java Bus 937 200 Complexity = 296
java Bus 1234 56 Complexity = 756	java Bus 1234 56 Complexity = 612
java Bus 22222222 117 Complexity = 10356	java Bus 22222222 117 Complexity = 718
java Bus 1234321 1024 Complexity = 169251	java Bus 1234321 1024 Complexity = 104
	java Bus 314159265358979323846264338327950288 8199 Complexity = 341
	java Bus 22222222222222222222222 117 Complexity = 31516
	java Bus 0123456789 3333 Complexity = 48924

Den basale algoritme har generelt højere kompleksitet og giver op længe før den heuristiske.

Spørgsmål D (frivillig)

Skriv en heuristisk version af Bus.java og sammenlign den med resultaterne i tabellen ovenfor. Tilføj eventuelt endnu mere imponerende instanser. Alternativt: beskriv nogle ideer til, hvordan nogle heuristikker kunne fungere.

Bemærk: hvis man afleverer nul heuristikker vil ens besvarelse faktisk blive godkendt! Til gengæld afholder vi en ekstra lille konkurrence om den bedste heuristiske algoritme. Man vinder, hvis ens algoritme kan klare flere instanser med lavere kompleksitet.

BlueJ version: BusBlueJ.zip.

Du deltager i vores Challenge ved senest den 13. november at sende en e-mail til mis@cs.au.dk med subject Challenge 10 og svarene på spørgsmål B, C og D (i plain text) og koden til spørgsmål D i form af et attachment med en ny udgave af programmet Bus.java.