برنامه ضرب دو ماتریس به زبان پایتون ـ پیتون

برنامه ضرب دو ماتریس در هم

کد این برنامه که(قبلا شبه کدش را منتشر کرده بودم) به زبان پایتون نوشته شده است می تواند دو ماتریس را در هم ضرب کند ـ شما می‌توانید همین کد را با استفاده از حلقه فور بنویسید ـ

ـ program python code for multiplication two matrices – matrix ـ

 

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

با توجه به این که نمی تونستم خود کد پایتون رو برای رفقای گل ترم علوم کلمپیوتر دانشگاه قم بزارم شبه کد برنامه ضرب دو ماتریس رو براتون انتشار میدم.

شبه کد چیست؟

شبه‌کد(به انگلیسی: pseudocode) روشی سریع، فشرده و غیر رسمی برای توضیح یک الگوریتم کامپیوتری است که از ساختارهای معمول بعضی از زبانهای برنامه نویسی استفاده می‌کند که برای خوانده شدن توسط انسان و نه ماشین طراحی شده است.

شما می توانید با کمی تامل شبه کد زیر را به یک کد واقعی در زبان پایتون یا هر زبان برنامه نویسی دیگری تبدیل کنید.

 

در مورد پروژه توریست منهتن

مسئله توریست منهتن

چند نفر از دوستان ورودی ۱۳۹۳ علوم کامپیوتر دانشگاه قم از من در مورد پروژه درسی سوال کردن پس بعد از تشریح مسئله ایده حل را بیان می کنم:

شرح مسئله: فرض کنید یک ماتریس ان در ان مانند زیر داریم:

۷ ۲ ۳
۲ ۵ ۱
۹ ۸ ۱

با دو حرکت راست و پایین از عضو(۰,۰) به عضو(ان,ان) برسید به طوری که جمع اعداد اعضای مسیر کمترین شود.

برای مثال ما، راه بهینه «راست ـ پایین ـ راست ـ پایین» است: ۲۱ = ۹ + ۲ + ۵ + ۲ + ۳

نکته: برنامه حل این مسئله باید به زبان پایتون(پیتون) باشد و در کمتر از ۴ ثانیه جواب بدهد.

این مسئله مشابه مسئله ای است که به نام «مسئله توریست منهتن» Manhattan Tourist Problem شهرت دارد. که با جستجو داخل شبکه جهانی می‌توانید اطلاعات بیشتری به دست‌آورید.

دو راه حل نه چندان خوب: قطعا از هر مسیری که برویم «ان منهای یک» حرکت به سمت راست و «ان منهای یک» حرکت به سمت پایین خواهیم داشت اما ترتیب این راست و پایین رفتن است که راه بهینه را مشخص می کند.

آ ـ تعدادی از رفقا این راه را پیاده سازی کرده بودند که در طی مسیر گزینه های عضو راستی و پایینی را با هم مقایسه کنیم و هر کدام کمتر بود از آن مسیر استفاده کنیم. اما این راه حل الزاما بهینه ترین مسیر را مشخص نمی کند.

کافیست به مثال بالا توجه کنید، اگر از الگوریتم مقایسه عضو راستی و پایینی استفاده کنیم از مسیر پایین ـ پایین ـ راست ـ راست می‌رویم که نتیجه می‌شود:‌ ۲۲ = ۹ + ۸ + ۱ + ۱ + ۳

ب ـ اما راه حل دیگری که به ذهن می رسد این است که جمع کل مسیر ها را محاسبه کنیم و در آخر ببینیم کدام مسیر کمترین هزینه را دارد. اما این راه حل در ماتریس های بزرگ زمان زیادی را لازم دارد و ان فاکتوریل محاسبه باید انجام گیرد!

راه حل پیشنهادی من: راه حل من بهینه کردن راه حل ب با استفاده از راه حل آ است!

اولا ـ عدد اول و عدد آخر در همه ی محاسبات یکی است پس آن ها را  در محاسبات دخیل نمی‌کنیم.

دوما ـ یک بار الگوریتم آ را اجرا می کنیم تا عددی به دست آوریم سپس الگوریتم ب را اجرا می‌کنیم اما این بار در محاسبات هر گاه عدد به دست آمده از عدد به دست آمده از الگوریتم آ بیشتر بود محاسبات متوقف می شود(و هر راه دیگری که از آن اعداد بگذرد امتحان نمی شود!) و اگر کمتر بود عدد بهینه تر به دست می‌آید و همینطور تا انتها ادامه می دهیم.

سوما ـ برای بهینه تر شدن محاسبات می توانیم الگوریتم آ را یک بار با ابتدا راست و یک بار با ابتدا پایین اجرا کنیم و از این دو طریق دو عدد به دست آوریم و یک عدد نمونه از میان این دو عدد به دست آوریم.

حل یک مثال با راه حل پیشنهادی:

۷ ۵۷ ۲ ۹۰
۶۶ ۱۵ ۱ ۳۳
۹ ۶ ۱۴ ۵
۷۲ ۱۶ ۳ ۸

۱ ـ الگوریتم آ اجرا می شود و از راه «راست ـ پایین ـ پایین ـ پایین ـ راست ـ راست» عدد ۳۶ به عنوان کمینه به دست می‌آید:

۳۶ = ۱۶ + ۳ + ۱۴ + ۱ + ۲

۲ ـ الگوریتم ب با توجه به عدد ۳۶ اجرا می شود هر کجا جمع اعداد بیشتر از ۳۶ شود آن مسیر بسته می شود اما اگر کمتر بود کمینه عدد کمتر قرار می‌گیرد:

ـ ۵۷ + ۲ > ۳۶ تمام مسیر هایی که شامل «راست ـ راست ـ …» می‌شوند مسدود شد!

ـ ۶۶ + ۱۵ + ۱ + ۲ >‌ ۳۶ تمام مسیر هایی که شامل «راست ـ پایین ـ راست ـ راست ـ …» می‌شوند مسدود شد!

ـ ۹ + ۶ + ۱۵ + ۱ + ۲ < ۳۶ کمینه به ۳۳ تغییر پیدا می کند.

ـ ۱۶ + ۶ + ۱۵ + ۱ + ۲ > ۳۳ کمینه تغییر پیدا نمی کند.

ـ ۱۶ + ۳ + ۱۴ + ۱ + ۲ > ۳۳ کمینه تغییر پیدا نمی کند.

ـ ۱ + ۳۳ > ۳۳ تمام مسیر هایی که شامل «پایین ـ راست ـ …» می‌شوند مسدود شد!

ـ ۵ + ۳۳ > ۳۳ تمام مسیر هایی که شامل «پایین ـ پایین ـ …» می‌شوند مسدود شد!

پاسخ: کمترین حاصل جمع ۳۳ است که از مسیر «راست ـ پایین ـ راست ـ پایین ـ راست ـ پایین» به دست آمده است.

توجه کنید اگر می‌خواستیم از الگوریتم ب به تنهایی استفاده کنیم باید ۲۴ حاصل جمع را محاسبه می کردیم اما در این الگوریتم تنها ۸ حاصل جمع استفاده شد. البته این بهینگی نسبت به ماتریس سوال متفاوت خواهد بود.

نکته: الگوریتم بیان شده در این نوشته امتحان شده نیست! بنابراین ممکن است زمان حل بیشتر از حد انتظار شود!