Tässä opetusohjelmassa opit, mikä on takaisinkelausalgoritmi. Löydät myös esimerkin perääntymisestä.
Takaisinkelausalgoritmi on ongelmanratkaisualgoritmi, joka käyttää raakaa voimaa lähestymistavan avulla halutun lähdön löytämiseen.
Raa'an voiman lähestymistapa kokeilee kaikkia mahdollisia ratkaisuja ja valitsee halutut / parhaat ratkaisut.
Termi takaisinveto viittaa siihen, että jos nykyinen ratkaisu ei ole sopiva, palaa takaisin ja kokeile muita ratkaisuja. Siten rekursiota käytetään tässä lähestymistavassa.
Tätä lähestymistapaa käytetään ongelmien ratkaisemiseen, joilla on useita ratkaisuja. Jos haluat optimaalisen ratkaisun, sinun on käytettävä dynaamista ohjelmointia.
Valtion avaruuspuu
Avaruustilapuu on puu, joka edustaa kaikkia ongelman mahdollisia tiloja (ratkaisu tai ratkaisematon) juuresta alkutilana lehteen päätetilana.
Valtion avaruuspuu
Takaisinkytkentäalgoritmi
Backtrack (x), jos x ei ole ratkaisu, palauta väärän arvon, jos x on uusi ratkaisu, lisää ratkaisujen luetteloon backtrack (laajenna x)
Esimerkki takaisinkelausmenetelmästä
Ongelma: Haluat löytää kaikki mahdolliset tapat järjestää 2 poikaa ja 1 tyttö kolmelle penkille. Rajoitus: Tyttö ei saa olla keskipenkillä.
Ratkaisu: Yhteensä on 3! = 6 mahdollisuutta. Kokeilemme kaikkia mahdollisuuksia ja löydämme mahdolliset ratkaisut. Kokeilemme rekursiivisesti kaikkia mahdollisuuksia.
Kaikki mahdollisuudet ovat:
Kaikki mahdollisuudet
Seuraava tilatilapuu näyttää mahdolliset ratkaisut.
Valtion puu kaikilla ratkaisuilla
Algoritmien takaisinkytkentä
- Löydät kaikki Hamiltonin polut kaaviosta.
- N Queen -ongelman ratkaisemiseksi.
- Sokkelonratkaisuongelma.
- Ritarin kiertueongelma.
