Suurin ero taaksepäin ja haarautumisen ja sidotun välillä on se backtracking on algoritmi joidenkin tai kaikkien ratkaisujen tallentamiseen tiettyihin laskennallisiin ongelmiin, erityisesti rajoitteiden tyytyväisyysongelmiin, kun taas haara ja sidottu on algoritmi, joka löytää optimaalisen ratkaisun moniin optimointitehtäviin, erityisesti diskreetissä ja yhdistelmäoptimoinnissa.

Algoritmi on menetelmällinen vaiheiden sarja tietyn ongelman ratkaisemiseksi. Algoritmeja on erilaisia, ja kaksi niistä on taaksepäin suuntautuvia ja haarautuneita ja sidottuja.

Taaksepäin, haara ja sidottu

Mikä on Backtracking

Backtracking on algoritmi, joka ratkaisee ongelman rekursiivisella tavalla. Se on järjestelmällinen tapa kokeilla erilaisia ​​päätöksiä, jotta löydetään oikea päätös. Se selvittää ratkaisun etsimällä tietyn ongelman ratkaisutilasta menetelmällisesti.

Kaikkien taaksepäin suuntautuvien ratkaisujen on täytettävä monimutkainen joukko nimenomaisia ​​ja implisiittisiä rajoituksia. Selkeä rajoitus rajoittaa kaikkia vektorielementtejä, jotka valitaan annetusta joukosta. Lisäksi implisiittinen rajoitus löytää ratkaisutilaan joukot, jotka voivat täyttää ehtofunktion.

Mikä on haara ja sidottu

Haara ja sidottu sopii paremmin tilanteisiin, joissa emme voi soveltaa ahneita menetelmiä ja dynaamista ohjelmointia. Yleensä tämä algoritmi on hidas, koska se vaatii eksponentiaalista monimutkaisuutta pahimmassa tapauksessa, mutta joskus se toimii kohtuullisella tehokkuudella. Tämä menetelmä auttaa kuitenkin määrittämään globaalin optimoinnin ei-kuperissa ongelmissa.

Lisäksi ongelman ratkaisemiseksi tämä menetelmä jakaa annetun alitehtävän vähintään kahteen uuteen rajoitettuun alitehtävään.

Ero taaksepäin ja haara ja sidottu

Määritelmä

Backtracking on algoritmi kaikkien ratkaisujen etsimiseen joihinkin laskennallisiin ongelmiin, etenkin rajoitusten tyytyväisyysongelmiin, jotka lisäävät ehdokkaita ratkaisuihin. Haara ja sidottu on algoritmi erillisille ja yhdistelmäoptimointitehtäville ja matemaattiselle optimoinnille. Näin ollen tämä on tärkein ero taaksepäin ja haarautumisen ja sidotun välillä.

Käsitellä asiaa

Lisäksi backtracking löytää ratkaisun yleiseen ongelmaan etsimällä ratkaisun ensimmäiseen osaongelmaan ja ratkaisemalla rekursiivisesti muita osaongelmia ensimmäisen ongelman ratkaisun perusteella. Haara ja sidottu ratkaisee kuitenkin tietyn ongelman jakamalla sen vähintään kahteen uuteen rajoitettuun alitehtävään. Siksi tämä on toinen ero taaksepäin ja haarautumisen ja sidotun välillä.

Tehokkuus

Johtopäätös

Backtracking on algoritmi joidenkin tai kaikkien ratkaisujen tallentamiseen tiettyihin laskennallisiin ongelmiin, etenkin rajoitetun tyytyväisyyden ongelmiin. Toisaalta Branch and Bound on algoritmi, jolla löydetään optimaaliset ratkaisut moniin optimointitehtäviin, erityisesti diskreetissä ja yhdistelmäoptimoinnissa. Tämä on tärkein ero Backtrackingin ja Branch and Boundin välillä.

Viite:

1. "DAA -algoritmien suunnittelutekniikat - Javatpoint." Www.javatpoint.com, saatavana täältä. "Esittely taaksepäin - Javatpoint." Www.javatpoint.com, saatavana täältä 3. "Takaisin kulkeminen." Wikipedia, Wikimedia Foundation, 7. joulukuuta 2018, saatavana täältä. "Haara ja sidottu." Wikipedia, Wikimedia Foundation, 8. lokakuuta 2018, saatavana täältä. "Mitä on paluumatka? - Määritelmä Techopediasta. ” Techopedia.com, saatavana täältä.

Kuva:

1. “Algoritmit v.s. Ohjelmointikielet ”Lubaochuan-Oma työ (CC BY-SA 4.0) Commons Wikimedian kautta