Ետադարձում

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

Ծածկագիրը

Որպեսզի օգտագործվի ետադարձումը խնդիրների հատուկ դասի համար, պետք է ապահովել P տվյալները խնդիրների հատուկ տեսակի համար, և 6 գործողության պարամետրեր՝ root(սկզբնաղբյուր), accept(ընդունել), first(սկիզբ), next(հաջորդ) output(տվյալների հաղորդման գործընթաց)։ Այս գործողությունները պետք է ընդունեն P տվյալները որպես չափորոշիչ և պետք է անել հետևյալը.

1. root(P) մասնակի տարբերակները տեղադրվում է որոնմնան ծառի արմատի մեջ
2. reject(P,c) դառնում է true, միայն եթե մասնակի տարբերակը՝ c-ն լիովին ավարտված չէ
3. accept(P,c) դառնում է true եթե c-ն P-ի լուծումն է
4. first(P,c) ստեղծում է c տարբերակի առաջին տարածումը
5. next(P,c) ստեղծում է տարբերակի առաջին երկընտրական տարածումը s տարածումից հետո
6. output(P,c) օգտագործում է P-ի c լուծումը։

Օգտագործման նկատառումները
Reject գործողությունը պետք է լինի boolean-valued fanction , որը վերադարձնում է true(ճիշտ), միայն երբ հաստատվում է, որ c-ի ոչ մի վերլուծություն ճիշտ լուծում չէ P-ի համար։ Եթե գործողությունը չի հասնում որոշակի արդյունքի, այն պետք է վերադառնա դեպի false(սխալ)։ Ոչ ճիշտ false արդյունքը կարող է հանգեցնել նրան, որ bt գործողությունը բաց թողնի մի քանի ճիշտ տարբերակներ։
Մյուս կողմից, ետադարձման ալգորիթմի էֆեկտիվությունը կախված է նրանից, որ reject-ը վերադարձնի true այն տարբերակների համար, որոնք որքան հնարավոր է մոտ են գտնվում արմատին։ Եթե reject-միշտ վերադարձնում է false, ալգորիթմը դեռ կգտնի լուծումներ, բայց այն համարժեք կլինի կոպիտ սահմանափակ որոնման։
Accept գործողությունը պետք է վերադարձնի true, եթե c-ն պատրաստի վերջնական տարբերակ է P խնդրի համար, և հակառակ դեպքում՝ false։ Այն կարող է ենթադրել, որ մասնակի տարբերակ c-ն և նրա բոլոր նախկին տարբերակները անցել են reject ստուգումը։
Նշենք, որ ընդհանուր ծածկագիրը չի ենթադրում, որ իրական լուծումները միշտ հանդիսանում են պոտենցիալ ծառի տերևները։ Այլ կերպ ասած՝ այն ընդունում է հնարավորությունը, որ P-ի համար իրական լուծումը կարող է հետագայում վերլուծվել, որպեսզի հայտնաբերվեն այլ ճիշտ տարբերակներ։ 1-ին և հաջորդ գործողությունները արվում են ետադարձման ալգորիթմով, հաշվելու համար ծառի c բողբոջի ավելի փոքր բաղադրիչները որոնք են այն տարբերակները, որ տարբերվում են c-ից տարածման միայն մի քայլով։ First կոճակը(P,c) պետք է արտադրի c-ի նախնական տարբերակը որոշ սահմանված կարգով, և next(P,c) կոճակը պետք է հայտնաբերի s բողբոջի հաջորդ զույգին այդ նույն կարգով։ Երկու գործողություններն էլ պետք է հայտնաբերեն «Անվավեր» տարբերակը, որը այստեղ նշված է 'Λ' նշանով, եթե պահանջված ավելի նախնական տարբերակը գոյություն չունի։
Root, first և next գործառույթները որոշում են մասնակի տարբերակների խումբը և պոտենցիալ որոնման ծառը։ Նրանք պետք է ընտրվեն այնպես, որ P-ի ամեն մի լուծում հայտնվի ծառի վրա, և ոչ մի մասնակաի տարբերակ մեկ անգամից ավել չհանդիպի։ Ավելին, նրանք պետք է ընդունեն շատ արդյունավետ reject ստորոգելին։

Շուտ կանգ առնելու տարբերակները
Վերը նշված ծածկագիրը կօգտագործի output-ը՝ բոլոր տարբերակների համար, որանք հանդիսանում են P-ի լուծում։ Ալգորիթմը հեշտությամբ թարմացվում և կանգ է առնում առաջին լուծումը կամ որոշակի քանակով լուծումներ գտնելուց հետո, կամ որոշակի քանակով մասնակի տարբերակները ստւգելուց հետո, կամ CPU տրված ժամանակի ավարտից հետո։

Սահմանափակ լրացումները
Ընդհանուր constraint satisfaction-? խնդիրները ներառում են գտնելը մի շարք թվեր x=(x(1), x(2),…..x(n), յուրաքանչյուրը մի շարքում(1,2,….m) , որը ………..-?
Այս դասի խնդիրների համար P-ի որպես օրինակ օգտագործվող տվյալները կլինեն m-ն և n-ն, և ստորոգելի F-ն։ Այս խնդրի սովորական ետադարձման եղանակով տրվող լուծման մեջ կարելի է առանձնացնել մի մասնակի տարբերակ՝ որպես թվերի ցուցակ c = (c[1],c[2], … c[k]), ցանկացած k-ի համար 0-i և n-ի միջև, որոնք պետք է նշանակվեն k օրինակները x[1],x[2], …, x[k])։ Արմատի տարբերակը հետագայում կլինի դատարկ ցուցակ()։First և next գործողությունները այնուհետև կունենան այս տեսքը.

function first(P,c)

k ← length(c)

if k = n

then return Λ

else return (c[1], c[2], …, c[k], 1)


function next(P,s)

k ← length(s)

if s[k] = m

then return Λ

else return (s[1], s[2], …, s[k-1], 1 + s[k])

Այստեղ length (c)- ն միավորների թիվն է c ցուցակում։
Reject-ը պետք է դառնա true , եթե F-ը չի կարող որոշվել n թվերի ցուցակով, որը սկսվում է c-ի k միավորներով։ Որպեսզի ետադարձումը արդյունավետ լինի, պետք է հնարավոր լինի վերլուծել այս իրավիճակը առնվազն մի քանի c տարբերակների համար։
Օրինակ, եթե F-ը մի քանի Boolean-? ստորոգելիների միացումն է, F = F[1] F[2] F[p], և յուրաքանչյուր F[i] կախված է փոքր subset of variables-? x[1], …, x[n] հետո reject գործողությունը կարող է պարզապես ստուգել F[i] –ը, որը կախված է միայն variable-ներից x[1], …, x[k], և դառնում են true եթե այս բառերից մեկը դառնում է false։ Փաստորեն, reject-ը միայն պետք է ստուգի այս բառերը, որոնք կախված են միայն նրանից, որ x[1], …, x[k-1] –ը հետագայում ստուգվեն որոնման ծառի մեջ։
Ընդհանրաապես ավելի լավ է բացել veriable-ների ցուցակը այնպես, որ այն սկսվի ամենահավանական օրինակներից։ Կարելի է նաև անել next գործողությունը՝ ընտրելու համար թե որ օրինակը պետք է նշանակվի, երբ բաղդատւմ ենք մասնակի տարբերակը, որը հիմնված է փոխարինելի օրինակների նշանակության վրա։ Հետագա բարելավումները կարող են ձեռք բերվել constraint propagation-ի միջոցով։ Ի հավելումն հիշողության և վերականգնման հետ կապված խնդիրներին՝ ետադարձումը պահպանում է փոփոխվող հետքեր, որպեսզի պահպանվի արժեքի փոխման գործընթացի պատմությունը։ Գործողության արդյունավետ կատարումը թույլ կտա խուսափել տարբերակների փոփոխականությունից, քանի որ այն կջնջի բոլոր փոփոխությունները 1 գործողությամբ։ Variable trail-? ի մեկ այլ տարբերակ է պահել փոփոխման ժամանակը, թե երբ է վերջին փոփոխությունը կատարվել։