User:SERINE

Ետադարձումը մի ընդհանուր ալգորիթմ է հաշվարկային խնդիրների բոլոր կամ մի քանի լուծումները գտնելու համար, որը աճման համակարգով ստեղծում է խնդիրների լուծման մի քանի տարբերակներ, և բաց է թողնում յուրաքանչյուր մասնակի տարբերակ, որը որ չի հանդիսանում խնդրի լուծման տարբերակ: Ետադարձման օգտագործման դասական տարբերակը դասագրքում նշվում է 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-? ի մեկ այլ տարբերակ է պահել փոփոխման ժամանակը, թե երբ է վերջին փոփոխությունը կատարվել: