მატრიცათა მიმდევრობის გადამრავლების ამოცანა

გადავწყვიტე წელს უნივერსიტეტში დავბრუნდე მაგისტრანტის სახით, მაგრამ ამისთვის ჯერ გამოცდა უნდა ჩავაბარო რამდენიმე დღეში. საკითხების სიაში დინამიური პროგრამირების კლასიკური ამოცანებიც შედის, რომელთაგან ერთ-ერთი ”მატრიცათა მიმდევრობის გადამრავლების” ამოცანაა (Matrix chain multiplication). ამ პოსტში მისი ამოხსნის შესახებ დავწერ. მაგალითები და ფსევდო კოდები Introduction to Algorithms წიგნიდან ავიღე.

სანამ ამოცანის დასმაზე გადავალ, მოკლედ გავიხსენოთ მატრიცების გადამრავლება. ეს არის ბინარული ოპერაცია, როდესაც ორ მატრიცაზე ოპერაციების ჩატარებით ვიღებთ ახალ, მესამე მატრიცას.

აქ ვხედავთ, რომ გამრავლებისთვის აუცილებელია პირველი მატრიცის სვეტების რაოდენობა მეორე მატრიცის სტრიქონების რაოდენობას ემთხვეოდეს. შესაბამისად, თუ პირველი მატრიცის განზომილებებია p და q, ხოლო მეორე მატრიცის – q და r, მათი გადამრავლებისთვის pqr ცალი წრფივი გამრავლების ოპერაცია დაგვჭირდება.

მატრიცების გამრავლების ოპერაცია ასოციაციურია, ანუ (AB)C = A(BC), მაგრამ არა კომუტატური – AB ნამრავლის შედეგი შეიძლება არ იყოს BA ნამრავლის შედეგად მიღებული მატრიცის ტოლი.

ვთქვათ მოცემულია A1,A2,A3 მატრიცების მიმდევრობა, სადაც A1 მატრიცის განზომილებებია 10 x 100, A2 – 100 x 5,   A3 – 5 x 50. იმის მიხედვით, თუ რა თანმიმდევრობით გავამრავლებთ მატრიცებს, სხვადასხვა რაოდენობის ოპერაცია დაგვჭირდება, თუმცა ასოციაციურობის გამო საბოლოო შედეგი ყოველთვის ერთი და იგივე მატრიცა იქნება. მაგალითად:



ამოცანა შემდეგში მდგომარეობს: მოცემული გვაქვს (A1, A2, A3,… An) მატრიცათა მიმდევრობა, სადაც Ai მატრიცას გააჩნია განზომილებები Pi-1 x Pi (i = 1,2,3..n) და უნდა ვიპოვოთ გადამრავლების ისეთი მიმდევრობა (ფრჩხილები ისე გავანაწილოთ), რომ წრფივი გამრავლების ოპერაციების რაოდენობა მინიმალური იყოს.

ცხადია, ამოხსნის ერთ-ერთი გზა განლაგებების ყველა ვარიანტის სრული გადარჩევაა, მაგრამ ვარიანტების რაოდენობა ექსპონენციალურად იზრდება როცა მატრიცების რაოდენობას ვზრდით. ამიტომ ბევრი მატრიცის შემთხვევაში ასეთი მიდგომა არ გამოდგება და უფრო ოპტიმალური ვარიანტი დაგვჭირდება.

დავაკვირდეთ მატრიცას, რომელსაც სულ ბოლოს – ყველა გადამრავლების შედეგად მივიღებთ. ის აუცილებლად იქნება ისეთი ორი მატრიცის ნამრავლი, რომ ორივე მათგანი თავისთავად ოპტიმალურად იყოს მიღებული მათი შემცველი მატრიცების მიმდევრობისთვის და ამავდროულად მათი ერთმანეთზე გადამრავლების ღირებულებაც მინიმალური იყოს.

ორი მატრიცის გადამრავლების ღირებულება დავარქვათ წრფივი გამრავლების ოპერაციების რაოდენობას, რაც იმ ორი მატრიცის გადამრავლებისთვის არის საჭირო.

ამიტომ თუ ამოვხსნით ზუსტად იგივე ქვეამოცანას იმ ორი მატრიცისთვის, პასუხზე დაყრდნობით მივიღებთ საბოლოო ამონახსნაც. დინამიური პროგრამირება ხომ სწორად ასეთი მეთოდია: დიდი ამოცანა იყოფა პატარა ქვეამოცანებად და მათი ამონახსნები საბოლოო პასუხის მისაღებად გამოიყენება.

კონკრეტულად, ჩვენი ამოცანა – ფრჩხილების ოპტიმალურად განაწილება A1,A2…. An მატრიცებს შორის შეგვიძლია გავყოთ ორ ქვეამოცანად: ფრჩხილების ოპტიმალურად განაწილება A1,A2,… Ak და Ak+1, Ak+2… An მიმდევრობებში; და შემდეგ გავაერთიანოთ პასუხი. სადაც 1<=k<n. ამ ორიდან თითოეული ასევე შეგვიძლია ორ ამოცანად გავყოთ და ა.შ. გავყვეთ ბოლომდე, სანამ არ მივალთ ტრივიალური, ერთ-მატრიციანი ამოცანის გადაჭრამდე. ერთი მატრიცის შემთხვევაში გადამრავლების ღირებულება ნოლის ტოლია.

შევადგინოთ რეკურენტული ფორმულა:
ამისთვის შემოვიღოთ ორგანზომილებიანი m მასივი, რომლის [i][j] უჯრაში შევინახავთ Ai,Ai+1… Aj მატრიცების მიმდევრობის გადამრავლებისთვის ოპტიმალურ პასუხს. მთლიანი ამოცანის შემთხვევაში A1..n მატრიცების გამრავლებისთვის საჭირო ოპერაციების რაოდენობა გვექნება m[1][n] უჯრაში.

როცა i=j, ცხადია ამ შემთხვევაში m[i][j]-ის მნიშვნელობა 0-ის ტოლი იქნება, ხოლო როცა i<j, იქიდან გამომდინარე რომ Ai..j მიმდევრობისთვის ოპტიმალური პასუხი არის Ai..k და Ak+1..j მატრიცების მიმდევრობებისთვის დათვლილი პასუხების ჯამი , დამატებული ამ ორი მატრიცის გამრავლების ღირებულება (Ai..k Ak+1..j => Pi-1PkPj). შესაბამისად m[i][j]-ის ექნება მნიშვნელობა m[i][k] + m[k+1][j] + Pi-1PkPj

აქ k არის ოპტიმალური გაყოფის ადგილი. მისი მნიშვნელობა ჯერ არ ვიცით. თუმცა შეგვიძლია ის გადავარჩიოთ i-დან j-მდე და ყველაზე ოპტიმალური ვარიანტი ავიღოთ. ამისთვის დამატებითი ციკლი დაგვჭირდება.

საბოლოო პასუხი არის არა შედეგად მიღებული მატრიცა ან ოპერაციების მინიმალური რაოდენობა, არამედ გადამრავლების ის თანმიმდევრობა, რაც პასუხის მისაღებად უნდა გამოვიყენოთ, ამიტომ შემოვიღოთ კიდევ ერთი ორგანზომილებიანი მასივი s, სადაც m[i][j]-ის გამოთვლის დროს s[i][j] უჯრაში შევინახავთ k-ს მნიშვნელობას (ანუ რა ადგილას გავყავით მატრიცების მიმდევრობა).

ეს არის Matrix-Chain-Order ფუნქციის ფსევდო კოდი, რომელიც m და s მასივების შეავსებს.
მას გადაეცემა მატრიცების განზომილებების მასივი p.

შეგვიძლია მივყვეთ ამ ფუნქციას მაგალითზე. ვთქვათ მოცემულია 6 მატრიცა.

შევავსოთ m და s მასივები.

ერთ ერთი იტერაციის ილუსტრაცია (აქ ხდება k-ს გადარჩევა და სამიდან მინიმალური ვარიანტის არჩევა):

საბოლოო ჯამში ყველა მატრიცის გადასამრავლებლად ოპერაციების მინიმალური რაოდენობა იქნება უჯრაში m[1][6], რომელიც ახლა 15,125-ის ტოლია.

შევაფასოთ ალგორითმის მუშაობა 😀
სამი ჩადგმული ციკლი გვაქვს და თითოეულში იტერაცია მაქსიმუმ n-1-ჯერ ხდება. ანუ ალგორითმი O(n3) დროში მუშაობს და n2 მეხსიერებას იყენებს (m და s მასივების შესანახად).

თუმცა ამოცანის პასუხი ოპერაციების რაოდენობა არ არის და მთავარია ის თანმიმდევრობა აღვადგინოთ, რის მიხედვითაც მატრიცების მიმდევრობები დაიყო. ამისთვის s მასივს გამოვიყენებთ. გავიხსენოთ, რომ s-ის თითეული [i][j] ელემენტი შეიცავს k-ს, ანუ ინფორმაციას, თუ მერამდენე ელემენტზე გაიყო Ai..j მატრიცების მიმდევრობა.

გამოდის ჩვენთვის ცნობილია, როგორ იყო მიღებული საბოლოო მატრიცა:
A1..n = A1..s[1,n] * As[1,n]+1 ..n
ხოლო ამ ორიდან პირველი მიიღება ისევ ორი მატრიცის მიმდევრობით, რომლიდანაც მეორე არის რიგით s[1,s[1,n]].
რაც შეეხება As[1,n]+1 ..n მიმდევრობის ნამრავლს, ისიც გაიყოფა ორად, და გაყოფის ადგილი იქნება s[s[1,n]+1,n] (უფრო სწორი იქნებოდა გამოთქმა რომ კი არ იყოფიან, არამედ ორი მატრიცის გაერთიანებით მიიღებიან).

როგორც ვხედავთ, შესაძლებელია რეკურსიული ფუნქციით მივყვეთ გზას და ფრჩხილები ისე დავბეჭდოთ. ქვევით მოცემულია ამ ფუნქციის ფსევდო კოდი:

ჩვენს მაგალითზე თუ გავუშვებთ ამ ფუნქციას, მივიღებთ მიმდევრობას:
((A1(A2A3))((A4A5)A6))

აქამდე აღწერილ მეთოდი “bottom-up” მიდგომით მუშაობს, რადგან ჩვენ პატარა სიგრძის მიმდევრობებიდან ვიწყებთ და მათზე დაყრდნობით ვაგებთ მატრიცათა შემდგომ მიმდევრობებს. ამოცანის ამოსახსნელად შეგვიძლია გამოვიყენოთ “top-down” მიდგომაც. ამ დროს ჩვენ უბრალოდ მატრიცების საბოლოო მიმდევრობიდან დავიწყებთ და რეკურსიულად ჩავყვებით სიღრმეში, მანამ სანამ ერთ მატრიციან მიმდევრობებზე არ დავალთ. თუმცა პირდაპირი რეკურსიის შემთხვევაში ჩვენ ისევ სრული გადარჩევა გამოგვივა, რაც, როგორც ზევით ვახსენეთ n-ის მიმართ ექსპონენციალურ დროში მუშაობს და არაეფექტურია.
ეს იმიტომ, რომ რეკურსიის დროს მისი სხვადასხვა განშტოებები ძალიან ბევრჯერ ერთსა და იმავე მიმდევრობას მიადგებიან და ყველა განშტოება ცალცალკე ამოხსნის ერთსა და იმავე მიმდევრობაზე პასუხს.

ასეთ შემთხვევაში შეგვიძლია ამოცანა მაინც ამოვხსნათ ”top-down” მიდგომით. უბრალოდ გზადაგზა უნდა დავიმახსოვროთ ამოხსნილი ქვეამოცანის პასუხები, და როდესაც იმავე ქვეამოცანასთან მივა ჩვენი რეკურსია, დამახსოვრებული პასუხი მივცეთ.
ამას Memoization ჰქვია.

რეკურსიული ფუნქციის ფსევდო კოდი ასე გამოიყურება:

ეს ალგორითმიც O(n3) დროში მუშაობს. თუ რატომ მუშაობს, შეგიძლიათ მოიფიქროთ :))

პასუხის დაბეჭდვისთვის შეგვიძლია იგივე ფუნქცია გამოვიყენოთ რაც ზედა მიდგომაში.

10 thoughts on “მატრიცათა მიმდევრობის გადამრავლების ამოცანა

  • 18 სექტემბერი, 2011 at 00:33
    Permalink

    კარგია! 🙂 მართლა ძალიან კარგია, კარგად გიწერია და კარგად გაქვს გაფორმებული :*

    შემდეგ პოსტს ველოდებით უდიდეს საერთო ქვემიმდევრობაზე 😛

    Reply
  • 18 სექტემბერი, 2011 at 00:43
    Permalink

    კონკურენტებს ეხმარები? 🙂
    ჯიბლას ვეთანხმები და ველოდები გაგრძელებას 🙂

    Reply
  • 18 სექტემბერი, 2011 at 03:12
    Permalink

    კონკურენტებს იშორებს პირიქით, ხო ხედავთ კოდები სურათებად ჩასვა რო ვერ გადააკოპირონ )))

    Reply
  • 18 სექტემბერი, 2011 at 11:06
    Permalink

    კაი ნაშრომია, კიდე რაებს გთხოვენ ჩასაბარებლად?
    ისე ბევრი შეცდომებია, როგორ შეიძლება A1 * A2 *A3 …..* A6 ს ნაკლები ოპერაცია ჭირდებებოდეს ვიდრე A1*A2 :დავაბნიოთმაგისტრანტები:
    😀
    წარმატებები

    Reply
  • 18 სექტემბერი, 2011 at 13:24
    Permalink

    ლოლ :))
    დიდი მადლობა ყველას. არ ველოდი ამდენს 😀

    შემდეგი ნამდვილად LCS იქნება.

    Reply
  • 20 სექტემბერი, 2011 at 02:22
    Permalink

    შეცდომა გაქვს Matrix_Chain_Order-ის ინიციალიზაციაში 🙂
    for i = 1 to n
    m[i][i] = 0
    უნდა გეწეროს 🙂

    Reply
  • 20 სექტემბერი, 2011 at 10:25
    Permalink

    აქამდე მაინც მენახა, ესე კარგად დაწერილი:D

    Reply
  • 20 სექტემბერი, 2011 at 12:24
    Permalink

    @Zuba
    მართალია 🙂 j არ არსებობს მანდ საერთოდ. მადლობა
    სახლში რომ მივალ გავასწორებ

    Reply
  • 21 სექტემბერი, 2011 at 10:53
    Permalink

    nice 🙂

    Reply
  • 09 სექტემბერი, 2013 at 21:25
    Permalink

    for i = 1 to n – 1 + 1 -_-

    Reply

კომენტარის დატოვება

თქვენი ელფოსტის მისამართი გამოქვეყნებული არ იყო. აუცილებელი ველები მონიშნულია *