به توان رساندن ماتریس‌ها و کاربرد‌هایش

یکی از مسائلی که بسیاری از مواقع با آن روبرو می‌شویم، مسئله‌ی به توان رساندن یک عدد یا یک ماتریس است. با روش تقسیم و حل می‌توان یک عدد یا مشابه آن یک ماتریس را به توان رساند و زمان این کار را کم کرد.

فرض کنید عدد یا ماتریس $A$ به شما داده شده است. همچنین عدد $B$ نیز در اختیار شما قرار گرفته‌است. شما می‌خواهید حاصل $A^B$ را محاسبه کنید.

می‌خواهیم از روش تقسیم و حل برای این سؤال استفاده کنیم. فرض کنید $B$ زوج باشد و مقدار $$x = A^{\frac{B}{2}}$$ را در اختیار شما گذاشته باشیم. شما با یک ضرب ساده به صورت $x \times x$ مقدار $A^B$ را می‌توانید محاسبه کنید. حال اگر $B$ فرد باشد و داشته باشیم: $$x = A^{\frac{B - 1}{2}}$$ اگر مقدار $x \times x \times A$ را محاسبه کنید، $A^B$ به دست می‌آید. بنابراین کافی است $B$ را نصف کرده، سؤال را حل کنید و از روی جواب این زیرمسئله، مقدار جواب نهایی مورد نظر خود را محاسبه کنید.

فرض کنید ضرب‌ها را در زمان $O(T)$ انجام بدهید، در این صورت می‌توان کل الگوریتم را در زمان $O(T \times lgB)$ به پایان رسانید. $$F(B) = F(\frac{B}{2}) + O(T)$$ $$F(B) = O(T \times lgB)$$

power.cpp

#include <iostream>
using namespace std;
int power(int A, int B) // you can imagine that A is matrix, but don't forget to write a function to multiply! 
{
    if(B == 0)
        return 1;
 
    int x = power(A, B / 2);
    x *= x;
    if(B % 2 == 1)
        x *= A;
 
    return x;
}
int main() {
    int A, B;
    cout << power(A, B) << endl;
}

توان رساندن ماتریس‌ها می‌تواند کاربردهای زیادی داشته باشد. اما ما یکی از کاربرد‌های معروف را بیان می‌کنیم:
اگر شما ماتریس مجاورت یک گراف را به توان $A$ برسانید، در درایه‌ی $(i, j)$ این ماتریس، تعداد گشت‌ها از $i$ به $j$ به طول $A$ نوشته شده است. برای اثبات این قضیه می‌توانید از استقرا کمک بگیرید.
کاربرد مسئله‌ی بالا در برخی روابط بازگشتی و برنامه‌نویسی پویا است. می‌توان برخی از مسائلی را که راه حل پویا دارند، به گراف تبدیل کرد، سپس با به توان رساندن ماتریس مجاورت گراف متناظر با مسئله، می‌توان جواب سؤال را در زمان بهتری پیدا کرد. برای مثال در صورتی که ماتریسی که درایه‌های آن به صورت زیر هستند: $$A[0][0] = 1$$ $$A[0][1] = 1$$ $$A[1][0] = 1$$ $$A[1][1] = 0$$ را به توان $n$ برسانید، می‌توانید $n$ امین عدد فیبوناچی را به دست آورید.