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

გადავწყვიტე წელს უნივერსიტეტში დავბრუნდე მაგისტრანტის სახით, მაგრამ ამისთვის ჯერ გამოცდა უნდა ჩავაბარო რამდენიმე დღეში. საკითხების სიაში დინამიური პროგრამირების კლასიკური ამოცანებიც შედის, რომელთაგან ერთ-ერთი ”მატრიცათა მიმდევრობის გადამრავლების” ამოცანაა (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. იმის მიხედვით, თუ რა თანმიმდევრობით გავამრავლებთ მატრიცებს, სხვადასხვა რაოდენობის ოპერაცია დაგვჭირდება, თუმცა ასოციაციურობის გამო საბოლოო შედეგი ყოველთვის ერთი და იგივე მატრიცა იქნება. მაგალითად:


Continue reading