(Translated by https://www.hiragana.jp/) Backtracking is een programmeertechniek voor optimalisaties, oplossen van puzzels en
programmeren van denkspelen, b.v. schaakcomputer.
Backtracking is een implementatie van kunstmatige intelligentie.
Backtracking is een fascinerende programmeertechniek welke kan worden gebruikt
voor optimalisaties, oplossen van puzzels en het programmeren van een
computer-tegenstander bij denkspelen.
Er zijn boeken over volgeschreven, maar in een notedop komt het hier op neer:
De computer doorloopt 'een boom van mogelijkheden' (met takken en zijtakken).
Zo'n tak kan b.v. betekenen: een stukje van een puzzel inpassen, of een zet
of tegenzet overwegen in een schaakpartij.
Als hij de top van een tak heeft verwerkt, volgt hij het spoor weer terug in de boom
tot het punt waarop hij gebleven was, waarna een volgende tak beklommen wordt.
Een ander aspect is dat een tak soms voortijdig wordt afgewezen, als duidelijk
is dat die niet succesvol zal zijn. Hierdoor kan je het proces sterk optimaliseren.
landelijk OV-rooster maken voor treinstellen, treinpersoneel, baanvakken en perrons
Optimaal lesrooster maken voor leerlingen, leraren en leslokalen
Vraag en Aanbod optimaliseren b.v. met
Lineair programmeren
in Operationele Analyse.
Het incomplete block design b.v. bij marktonderzoek, product testing:
Stel je wilt 8 smaken laten beoordelen, maar om praktische redenen kan je maar 4 smaken
per respondent laten proeven.
Van 4 uit 8 kan je 70 combinaties maken (8 over 4 = (8*7*6*5)/(4*3*2*1) = 70) geeft 70 testgroepen, maar er is in dit geval ook een manier
om met een set van 14 groepen een Balanced Incomplete Block Design te maken.
Toernooi/competitie indeling (kandidaten en tegen-kandidaten uit dezelfde lijst)
Dating: een lijst kandidaten met een lijst tegen-kandidaten matchen (in theorie)
Schaken. Van de oude 'Chess Challenger' kon beetje speler prima winnen,
maar heb je al eens tegen 'Deep Blue' of 'Deep Fritz' gespeeld?
Alleen de sterkste spelers maken nog kans tegen software uit de winkel.
Dammen, ook bij dammen hebben alleen de spelers op wereldniveau nog kans.
4 op een rij,
is inmiddels door de computer opgelost!
Degene die begint kan altijd winnen.
Computers presteren inmiddels beter dan mensen bij de meeste denkspelen.
Mensen hebben ook een soort alpha-beta algoritme, vooral gebaseerd op intuïtie.
Je maakt misschien kans als je varianten ziet die door het computer Alpha�beta algoritme
worden afgekapt, in schaaktermen: verzin een verrassend
dame-offer!
Cijfers
uit TV-programma 'Cijfers en Letters' oplossen
Logikwis puzzels
Met een set van aanwijzingen moet je de juiste combinaties zien te vinden.
Extra uitdaging voor een generiek programma: hoe vertaal je de tekstuele aanwijzingen in bruikbare code voor de computer?
Dat lukt alleen als de aanwijzingen binnen een beperkte set van model-aanwijzingen blijven.
sudoku (zowel ontwerpen als oplossen), inleiding...
Een magisch vierkant van domino-stenen
Het vierkleurenprobleem. Het is bewezen dat je de landen in een landkaart met
vier kleuren
kunt inkleuren zonder dat er twee aangrenzende landen van dezelfde kleur zijn. Je kan het voor een gegeven kaart ook programmeren.
Zie ook het boek 'Spelen met Puzzels' uit 1978 van Pieter van Delft en Jack Botermans,
voor een haast onuitputtelijke bron van breinbrekers waarvan er veel geschikt zijn om te programmeren.
Het is nog regelmatig te koop bij tweedehandswinkels.
de computerspellen The 7th guest
en The 11th hour
bevatten een leuk aantal puzzels die met de computer kunnen worden opgelost,
of waarin de computer een sluwe tegenstander kan zijn.
Er zijn verschillende stijlen (elk met zijn eigen voordeel):
Recursie - hierin schrijf je ��n routine die zichzelf aanroept,
zodanig dat het de oefening herhaalt met een kleiner gedeelte van de opgave.
Je programma kan er soms onwaarschijnlijk simpel uit zien, en toch werkt het!
Oude of primitieve programmeertalen ondersteunden dit vrij slecht, maar
de moderne talen zoals Visual Basic, C, Delphi en Java hebben er geen enkel probleem mee.
��n grote 'while'-loop, dit is in vrijwel elke taal te realiseren.
Als je een backtrack-programmeertaal kiest zoals b.v Prolog dan de kern al voor je gedaan.
Deze recursieve talen gaan meestal wel iets kwistiger met geheugen om.
Dus als je opgave te groot is kunnen er geheugenproblemen optreden.