Ետադարձում
Ետադարձումը մի ընդհանուր ալգորիթմ է հաշվարկային խնդիրների բոլոր կամ մի քանի լուծումները գտնելու համար, որը աճման համակարգով ստեղծում է խնդիրների լուծման մի քանի տարբերակներ, և բաց է թողնում յուրաքանչյուր մասնակի տարբերակ, որը որ չի հանդիսանում խնդրի լուծման տարբերակ։ Ետադարձման օգտագործման դասական տարբերակը դասագրքում նշվում է 8 թագուհիների հանելուկի օրինակով, որի խնդիրն է ստանդարտ շախմատի տախտակի վրա դասավորել թագուհիներն այնպես, որ ոչ մի թագուհի մյուսին չհարվածի։ Ընդհանուր ետադարձման լուծման եղանակով մասնակի տարբերակները թագուհիները տախտակի առաջին և վերջին շարքերում դասավորելն է այնպես, որ բոլորը գտնվեն տարբեր սյունակներում և շարքերում։ Յուրաքանչյուր մասնակի լուծում, որը կհանգեցնի ցանկացած երկու թագուհիների միմյանց հարվածելուն, կարող է բացառվել, քանի որ այն չի հանգեցնւմ խնդրի վերջնական լուծմանը։ Ետադարձումը կարող է օգտագործվել միայն այն խնդիրների համար, որոնք ընդունում են մասնակի տարբերակի լուծման հասկացությունը, և համեմատաբար ավելի արագ տեստերի, որոշելու համար արդյոք այն ունի վերջնական լուծում, թե ոչ։ Այն անօգուտ է օգտագործել օրինակի համար որոշելու համար դեռ չպատվիրված սեղանի հաշիվը։ Երբ կիրառելի է, ետադարձումը այնուամենայնիվ հաճախ շատ ավելի արագ է, քան բոլոր տարբերակների կոպիտ հաշվարկը, քանի որ այն կարող է բացառել մեծ թվով տարբերակներ միայն 1 տեստով։ Ետադարձումը կարևոր միջոց է սահմանափակման միջոցով լուծվող այնպիսի խնդիրների համար, ինչպիսիք են խաչբառները, բառահաշվարկը, սուդոկուն, և շատ այլ գլուխկոտրուկներ։ Այն հաճախ ամենահարմար, եթե ոչ ամենաարդյունավետ միջոցն է քերականական վերլուծության և այլ համակցական խնդիրների լուծման համար։ Այն նաև հիմքն է այդպես կոչված ծրագրավորման տրամաբանական լեզուների, ինչպիսիք են Icon–ը, Planner-ը և Prolog-ը։ Ետադարձումը նաև օգտագործվում է Mediawiki ծրագրի համար։ Ետադարձումը կախված է օգտագործողի կողմից տրված «սև արկղի գործընթացից», որը որոշում է խնդրի լուծումը, մասնակի տարբերակների էությունը, և թե ինչպես են նրանք վերածվում վերջնական տարբերակների։ Ուստի այն ավելի շատ (metaheuristic-?) է, քան որորշակի ալգորիթմ, չնայած ի տարբերություն շատ այլ meta-heuristic-ների՝ այն երաշխավորում է տալ խնդրի բոլոր վերջնական լուծումները սահմանափակ ժամանակի ընթացքում։ Ետադարձում տերմինը ստեղծվել է ամերիկացի մաթեմատիկոս Դ. Հ. Լեմերի կողմից 1950-ական թվականներին։ Ետադարձման ալգորիթմը առանձնացնում է մի շարք տարբերակներ, որոնք հիմնականում կարող են ստացվել տարբեր եղանակներով, որպեսզի տան տրված խնդրի բոլոր հնարավոր լուծումները։ Ավարտը կատարվում է աստիճանաբար, տարբերակների վերլուծման հաջորդականությամբ։ Ընդհանուր համեմատությամբ մասնակի տարբերակները ծառի կառուցվածքում կազմում են բողբոջները՝ պոտենցիալ «որոնման ծառի»։ Յուրաքանչյուր մասնակի տարբերակ ստեղծողն է այն տարբերակների, որոնք տարբերվում են իրենց տարածվածության աստիճանով։ Ծառի տերևները այն մասնակի տարբերակներն են, որոնք այլևս չեն կարող տարածվել։ Ետադարձման ալգորիթմը անընդհատ առնչվում է այս «որոնման ծառի» հետ բազմաթիվ անգամ ներքևի արմատներից սկսած depth-first order-ում(ալգորիթմ, որի միջոցով որոնում են ծառը, կամ ծառի կառուցվածքը)։ Յուրաքանչյուր c բողբոջի վրա ալգորիթմը որոշում է՝ արդյո՞ք c-ն կարող է հանդիսանալ խնդրի լուծում։ Եթե այն չի կարողանում դա անել, ամբողջ ենթածառը, որը հիմնված է c-ի վրա, բաց է թողնվում։ Այլապես ալգորիթմը առաջինը ստուգում է՝ արդյոք c-ն ինքնին ճիշտ լուծում է թե ոչ, և եթե դա այդպես է, հաղորդում է այդ մասին օգտագործողին, և երկրորդ, անընդհատ հաշվում է ի բոլոր ենթածառերը։ Երկու տեստերը և բողբոջների ավելի փոքր բաղադրիչները որոշվում են օգտագործողի գործողություններով։ Ուստի իրական որոնման ծառը, որը առնչվում է ալգորիթմի հետ, պոտենցիալ ծառի միայն մի մասն է։ Ալգորիթմի ընդհանուր լուծումը պայմանավորված է իրական ծառի բողբջների քանակով և ամեն մի բողբոջը ստանալու և վերլուծելու ժամանակով։ Այս փաստը պետք է հաշվի առնել, երբ ընտրում ենք պոտենցիալ ծառը և իրականացնում ենք կրճատող ստուգումը։