Van itt valaki, aki érti a backtracking (visszalépéses keresés) programozási módszert, és el is tudná nekem magyarázni, ha megkérem?
Az a gond, hogy egyszerűen nem tudom kigondolni. A lényegét értem, viszont mikor arra kerül sor, hogy leprogramozzam, egyszerűen nem megy... Rekurzívan oldottunk meg 1-2 feladatot, és hiába próbálkozok, egyedül nem megy.
Pl. van egy olyan feladat, hogy: Adott egy n elemű számsorozat. Helyezzünk közéjük n-1 műveletjelet, úgy, hogy az eredmény egyenlő legyen egy adott számmal. A műveletjeleket balról jobbra vesszük figyelembe, nem a matematika szabályainak megfelelően.
Ez hogyan lehetne megoldani? Akárhogyan próbálkozok, viszonylag mindig hamar belebukok a megoldásba. Ha valaki tudna segíteni, nagyon hálás lennék!
válasza: válasza:Ott van hozzá kód is alul, olvasd el, látom beraktad a c++-t a címkék közé, szóval még érted is a kódot.
Ezen tovább nem lehet segíteni, kicsit törni kell a fejedet rajta, hiába, ez van.
válasza:Bajnak nem baj, hogy ezt mondod, legszívesebben én sem foglalkoznék ilyesmivel. :)) De jelenleg ezt tanuljuk, határidőre kéne feladatokat megoldanom, és nem mennek... Más programozási feladatokat mondhatni könnyen és elég jól meg tudok oldani, sőt, mindig arra törekszek, hogy minnél jobb legyen, minnél több hibát tudjon kezelni, stb.
A rekurziót még úgy ahogy megértettem, és pár próbálkozás után le tudom programozni azt, amit akarok. De ez a backtracking módszer soha nem ment, pedig most tanulom talán másodjára. :(
válasza:"A rekurziót még úgy ahogy megértettem"
Pontosan kell érteni a rekurziót, onnan egy ugrás a backtracking megértése majd alkalmazása.
Backtracking az egy fát jár be (mely a problémának az állapotterét reprezenálja) , minden lehetséges megoldás egy-egy levele ennek a fának. Legrosszabb esetben a levélnél látszik hogy megoldás e, akkor hatékony a backtracking módszer, ha már a részfákra megállapítja viszonylag gyorsan hogy annak egyetlen levele sem megoldás. Csillagászati méretű is lehet egy-egy részfa mérete mely teljes bejárása hosszú idő, a backtrack még is gyorsan bejárhatja, mivel nagy részfákat feleslegesen be sem jár. Persze ez implementáció és feladatfüggő.
Mindig kell valamilyen heurisztika,( még ha olyan egyszerű is mint a százas szeg,) az hogy mikor nem érdemes azon a részfán tovább menni.
Pl a 8 királynő problémájánál ha egymás alatt van 2 királynő akkor nem kell próbálkozni a többi királynő rakosgatásával. Amíg nem ismertem a backtracking-ot addig fél óra alatt sem találtam egy megoldást sem fel is adtam. Később amikor megismertem a módszert akkor 5 perc sem kellett hogy találjak egy megoldást, pedig csak gépiesen futtam fejben a Backtracking-ot és rakosgattam közben a sakktáblán a bábukat.
-------------
"van egy olyan feladat, hogy: Adott egy n elemű számsorozat. Helyezzünk közéjük n-1 műveletjelet, úgy, hogy az eredmény egyenlő legyen egy adott számmal. A műveletjeleket balról jobbra vesszük figyelembe, nem a matematika szabályainak megfelelően."
Ez pofon egyszerű. Az én logikám szerint nyilván kell tartani a backtrack-ra használt eljárás/függvény hívási mélységét, hogy a hívott rekurzív eljárás/függvény tudja hogy hol tartunk. Az aktuális részeredményt át kell neki adni. For ciklussal végig kell menni a műveletek halmazán és végre kell hajtani, bele kell "csempészni" a rekurzív hívásokat.
válasza:"Mindig kell valamilyen heurisztika,( még ha olyan egyszerű is mint a százas szeg,) az hogy mikor nem érdemes azon a részfán tovább menni."
Ahhoz hogy hatékony legyen, különben csak akkor lehet hatékony ha kicsi a problématér.
válasza:Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!