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

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

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

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

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

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

ამოცანა შემდეგში მდგომარეობს: მოცემული გვაქვს (A₁, A₂, A₃,… A_n) მატრიცათა მიმდევრობა, სადაც A_i მატრიცას გააჩნია განზომილებები P_i-1 x P_i (i = 1,2,3..n) და უნდა ვიპოვოთ გადამრავლების ისეთი მიმდევრობა (ფრჩხილები ისე გავანაწილოთ), რომ წრფივი გამრავლების ოპერაციების რაოდენობა მინიმალური იყოს.

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

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

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

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

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

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

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

აქ 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(n³) დროში მუშაობს და n² მეხსიერებას იყენებს (m და s მასივების შესანახად).

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

გამოდის ჩვენთვის ცნობილია, როგორ იყო მიღებული საბოლოო მატრიცა:
A_1..n = A_1..s[1,n] * A_{s[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(n³) დროში მუშაობს. თუ რატომ მუშაობს, შეგიძლიათ მოიფიქროთ :))

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

გამოხმაურება

comments