Takaisinkytkentäalgoritmi

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: