Beste
Heeft iemand een algemeen stappenplan dat gevolg kan worden voor backtracking(in python) ? Want ik heb volgend week daar examen van en ik snap het eerlijk gezegd nog niet zo goed, recursie gaat beter maar ook nog moeilijkheden mee.
alvast bedankt!
Laatste berichten
-
08:24
Schroefdraad berekening 7
-
00:15
[scheikunde] Kan chloorgas de geleiding van elektriciteit belemmeren? 9
-
22:27
positie 1
-
21:15
Weerfrustratie 9
-
18:08
geen minkowski-ruimte toch? Doe ik dit nou fout? 15
-
14:16
do-re-mi-fa-so vliegtuigen 7
-
14:16
Kunnen quantum Zonnecellen 190% quantum efficiënt zijn 3
-
13:57
De Euro Nederlandse 100 qubit computer komt eraan
-
10:42
projectiel 8
-
10:37
Verschil tussen deze 2 vragen 5
-
09:25
[scheikunde] berekeningen labo vitamine c bepaling 1
-
22 apr
[wiskunde] rode en witte ballen verdelen 8
-
22 apr
Rotatie van het heelal 41
-
22 apr
Muntje opgooien 14
-
21 apr
Reactiviteit silyl enol ethers 1
-
21 apr
Criterium voor vochtretentie
-
21 apr
speciale rel. theorie 5
-
21 apr
Vogels in de stad zijn goede klussers
-
21 apr
Ervaringen met "herontdekkingen" 15
-
20 apr
Herleiden afmetingen vanaf een foto 19
Nieuwsberichten
-
04 mar
Een nieuw soort magnetisme: altermagnetisme
-
31 okt
AI kan via stem diabetes vaststellen 11
-
21 okt
Einstein krijgt wéér gelijk 45
-
07 feb
witter dan wit 20
-
19 jun
irrigatie en de aardas
[informatica] backtracking
Moderators: ArcherBarry, Fuzzwood
-
- Berichten: 778
Re: backtracking
Wat weet je er zelf wel over?
Een algemeen stappenplan kan zijn:
"Als je op een keuzepunt staat, maak je een keuze, en probeer je of de gekozen route naar een oplossing leidt. Loop je bij de gekozen route vast, dan ga je terug naar je keuzepunt, en maak je een andere keuze."
Een algemeen stappenplan kan zijn:
"Als je op een keuzepunt staat, maak je een keuze, en probeer je of de gekozen route naar een oplossing leidt. Loop je bij de gekozen route vast, dan ga je terug naar je keuzepunt, en maak je een andere keuze."
-
- Berichten: 2.609
Re: backtracking
Zoals hierboven gezegd ben je inderdaad nogal vaag.
De uitleg van Back2Basics in pseudocode zou er als volgt uitzien:
Stel dat we een puzzel willen oplossen. Een puzzel heeft een zekere staat (configuratie van de elementen) en een zekere oplossing (eindconfiguratie die we willen bereiken). In een bepaalde staat proberen we 1 voor 1 alle mogelijke moves uit in die staat en we roepen de DFS functie recursief op. Als een oplossing gevonden wordt dan moeten er geen andere moves meer uitgevoerd worden. Indien er geen oplossing gevonden werd, dan maken we de move ongedaan en proberen we een andere move uit. Als geen enkele van de moves tot een oplossing leidde, dan returnen we False. De code zal backtracken tot het al dan niet een oplossing vindt.
DFS staat voor "depth first search". Met die zoekterm vind je op het internet eventueel meer info en voorbeelden.
De uitleg van Back2Basics in pseudocode zou er als volgt uitzien:
Stel dat we een puzzel willen oplossen. Een puzzel heeft een zekere staat (configuratie van de elementen) en een zekere oplossing (eindconfiguratie die we willen bereiken). In een bepaalde staat proberen we 1 voor 1 alle mogelijke moves uit in die staat en we roepen de DFS functie recursief op. Als een oplossing gevonden wordt dan moeten er geen andere moves meer uitgevoerd worden. Indien er geen oplossing gevonden werd, dan maken we de move ongedaan en proberen we een andere move uit. Als geen enkele van de moves tot een oplossing leidde, dan returnen we False. De code zal backtracken tot het al dan niet een oplossing vindt.
Code: Selecteer alles
def DFS(staat):
if isOplossing(staat):
return True
for move in mogelijkeMoves(staat):
pasMoveToe(staat, move)
check = DFS(staat)
if check:
return True
else:
maakMoveOngedaan(staat, move)
return False
DFS(beginstaat)
