Առաջադրություն 8

Կոնտեքստ:
Վիճակագրական մեքենայական թարգմանության մեջ տարածված ենթախնդիր է Բառերի ترتیبը (Word Ordering)։ Ձեզ տրվում է «բառերի պարկ» (խառը կարգով տրված բառերի բազմություն), և դուք պետք է վերականգնեք նախադասության սկզբնական կարգը՝ առավելագույնի հասցնելու հաջորդականության հավանականությունը։

Թող \(W = \{w_1, w_2, \dots, w_N\}\) լինի \(N\) եզակի բառերից կազմված բազմություն։
Ձեզ տրված է բիգրամ լեզվային մոդել \(P(w_j | w_i)\), որը տալիս է \(w_j\) բառի \(w_i\)-ից հետո հայտնվելու հավանականությունը։
Կան երկու հատուկ նշաններ՝ \(⟨\text{S}⟩\) (Սկիզբ) և \(⟨\text{E}⟩\) (Վերջ)։ Նախադասությունը պետք է սկսվի \(⟨\text{S}⟩\)-ով և ավարտվի \(⟨\text{E}⟩\)-ով։

Նպատակ.
Գտնել \(\pi\) վերադասավորումը (permutation) \(W\)-ի բառերի վրա, որը առավելագույնի է հասցնում նախադասության հավանականությունը՝
\[
P(\pi) = P(w_{\pi_1} | ⟨\text{S}⟩) \times \left( \prod_{i=1}^{N-1} P(w_{\pi_{i+1}} | w_{\pi_i}) \right) \times P(⟨\text{E}⟩ | w_{\pi_N})
\]

A* ալգորիթմը կիրառելու համար այս առավելագույնի խնդիրն փոխակերպում ենք նվազագույնի խնդրի՝ սահմանելով բառ \(u\)-ից բառ \(v\) անցման արժեքը որպես բացասական լոգարիթմական հավանականություն.
\[
C(u, v) = -\ln(P(v | u))
\]

Մաս A․ Վիճակների տարածության ֆորմալացում
Ֆորմալացրեք այս խնդիրը որպես վիճակների տարածության գրաֆի որոնում, որը հարմար է A* ալգորիթմի համար։
Մասնավորապես, սահմանեք՝

    1. Վիճակի \(n\)-ի կառուցվածքը։
    2. Սկզբնական վիճակը և Նպատակ վիճակը։
    3. Հաջորդների ֆունկցիան (ինչպես են գեներացվում անցումները) և կուտակված արժեքը \(g(n)\)։

[3 միավոր]

Մաս B․ Հուրիստիկայի նախագծում
Հիմնական բարդությունը պայմանավորված է որոնման տարածության ֆակտորիալ կառուցվածքով (\(N!\)), որի պատճառով տրիվիալ հուրիստիկան (օր.՝ \(h=0\)) հաշվարկային առումով դառնում է անիրագործելի նույնիսկ համեմատաբար փոքր մուտքերի (օր.՝ \(N > 15\)) համար։
Նախագծեք ոչ տրիվիալ հուրիստիկա \(h(n)\), որը գնահատում է նախադասությունը լրացնելու համար մնացած արժեքը։ Ձեր հուրիստիկան պետք է բավարարի հետևյալ չափանիշներին․

    1. Այն պետք է լինի ընդունելի (admissible)։
    2. Այն պետք է լինի մոնոտոն (կոնսիստենտ)։

Սահմանեք ձեր հուրիստիկան մաթեմատիկորեն։ Դեռևս կարիք չկա ապացուցել դրա հատկությունները, բայց պետք է բացատրեք ձեր նախագծման տրամաբանությունը։

Հուշում․ Դիտարկեք այն բառերի բազմությունը, որոնք դեռ չեն տեղադրվել։ Վավեր ամբողջացված նախադասությունում այս բառերից յուրաքանչյուրը պետք է ունենա ճիշտ մեկ մուտքային կող (incoming edge)։

[5 միավոր]

Մաս C․ Տեսական ապացույցներ
Օգտագործելով Մաս B-ում սահմանած \(h(n)\) հուրիստիկան, տվեք պաշտոնական ապացույցներ հետևյալ հատկությունների համար․

    1. Ընդունելիություն (Admissibility)․ ապացուցեք, որ \(h(n) \le h^*(n)\), որտեղ \(h^*(n)\)-ը իրական նվազագույն արժեքն է մինչև նպատակը։
    2. Մոնոտոնիկություն (Monotonicity)․ ապացուցեք, որ \(h(n) \le cost(n, n') + h(n')\), որտեղ \(n'\)-ը \(n\)-ի հաջորդն է։

[5 միավոր]
[Ընդամենը 13 միավոր]