Backtrack (visszalépéses) algoritmus segítség, magyarázat?

Ha már szorgalmi, elsőként pl. ezt olvasd el:

[link]

Lényegében azt kell csinálnia a backtrackingnak, hogy elkezdi bepróbálni a dobozokat, ha elakadt a bepakolás akkor visszalép egyet és bepróbálja az utolsó lép helyére mást. Ezt végigpróbálgatja, majd még egyet visszalép és a helyett máshogy dönt és úgy végigpróbálgatja stb stb.

Értelem szerűen ha egyből megvan akkor kész is. Meg egyéb sarokesetekre is fel kell készülni.

Értelem szerűen egy rekurzív algoritmus ez.

"Értelem szerűen egy rekurzív algoritmus ez."

Vagy nem.. :))

@05:15

Ezt kifejtenéd? Ez így egy nagy nulla volt ideírni, semmi indok semmi csak idehánytad.

Nem nagyon kell ezt kommentálni.

A rekurzió egy elég veszélyes művelet azoknál, akik nem ismerik a számítógépek architektúráját. Ezért nem is ajánlatos rekurzióra biztatni efféle emberkéket. Kivált nem olyan feladatnál, amelynek megoldástere ennyire tág.

Amellett, alap, hogy ami rekurzióval megoldható, az megoldható iteratívan is. Ergo, abszolút nem igaz az a tétel, amire hivatkoztál, hogy "értelemszerűen" rekurzió..

"A rekurzió egy elég veszélyes művelet azoknál, akik nem ismerik a számítógépek architektúráját."

Tök mindegy, hogy Snapdragon 854, amd a6, intel core i7 stb. Nem előfeltétele a rekurzió megírásának. Régebbi rekurzív kódom is kiválóan fut újabb architektúrájú gépen, esélyem se volt hogy akkor ismerjem amikor még nem is létezett.

Azt kell tudni, hogy a rekurzió hogy működik.

Kinek mi baja lenne hogy annyira veszélyes?

"Amellett, alap, hogy ami rekurzióval megoldható, az megoldható iteratívan is. Ergo, abszolút nem igaz az a tétel, amire hivatkoztál, hogy "értelemszerűen" rekurzió.."

Értelem szerűen mert rekurzív összefüggések vannak. A probléma részproblémákra való bontása rekurzívan. Nem mondtam csak rekurzívan lehet megoldani, de máshogy bonyolultabb. Ha nem hiszed akkor kódold le a hanoi tornyait rekurzívan meg nem rekurzívan is!

A backtraxking amúgy tipikusan nem rekurzívan van megvalósítva.

A rekurzió megva rekurzív robbanás miatt nem nagyon használható az iparban csak bizonyos optimalizációk mellett. Persze tény, hogy ezt néhány nyelv elég jól támogatja.

De aki naívan elkezd rekurzív algoritmusokat írni, majd azt valódi problémákra ráengedni, az meg fog lepődni.

Csak részben van igazatok. Van amikor igen is jól használható a rekurzió. Tudom van olyan probléma ahol nyersen nem éri meg a "rekurzív robbanás" miatt. Azonban az a kijelentés hogy az iparban nem használatos az tévedés. Ez tipikusan egy olyan feladat ahol jól alkalmazható. Annyira nem kell félni tőle.

Fogtam magam és implementáltam pythonban.

Csak a pszeudokódot rakom ki nyilvánosan: [link]

Legrosszabb esetbe se megy túl (jó 1-el lehet hogy igen) a rekurziós mélység a dobozok darabszámánál az én implementációmban. A számítás nem csinál olyan exponenciális robbanást az iteratívhoz képest mint például a fibonacci számok esetében.

Nem ez volt se az első, se az utolsó amit rekurzívan megcsináltam backtrack-et.

"Legrosszabb esetbe se megy túl (jó 1-el lehet hogy igen) a rekurziós mélység a dobozok darabszámánál az én implementációmban. "

Akarom mondani a dobozok darabszámának felénél tovább nem megy legrosszabb esetben sem. (Max 1-el esetleg.)