نویسنده : mohammad
Sunday, April 19, 2009
0
comments
الگوریتم وارشال در ساختمانهای گسسته
با سلام
چندین نفر تا بحال هم از طریق ایمیل و هم از بخش نظرات اظهار داشتند که الگوریتم وارشال و ضرب بولی را در کلاس استاد انوری متوجه نشدند و درخواست توضیح از جانب من کرده بودند.
باید بگم که استاد انوری از نظر من این مبحث رو به بهترین شیوه توضیح دادند و من هم یه دانشجوی معمولی مثل بقیه شما هستم ولی چون خواستید یه شیوه که فهمش راحتتر هست و درواقع همون راه استاد انوری هست و فقط شیوه بیانش راحتتره رو براتون می گم:
بدست آوردن بستار متعدی یک رابطه با استفاده از الگوریتم وارشال:
برای این کار ابتدا ماتریس MR=W0 قرار می دهیم.
سپس سطر اول و ستون اول ماتریس W0 را در نظر گرفته و موقعیت هایی از سطر اول را که ارزش آنها یک(1) است را در qj و موقعیت هایی از ستون اول را که ارزش آنها یک(1) است را در pi ذخیره می کنیم.
حال با دو مجموعه pi و qj زوج های مرتبی می سازیم که اگر به صورت (a,b) باشند:
b متعلق به مجموعه qj
بدین ترتیب خانه هایی که زوج مرتب آنها از مرحله قبل به دست آمد را دارای ارزش یک(1) می کنیم.
بدین ترتیب ماتریس w1 حاصل می شود.مراحل را ادامه می دهیم تا به سط و ستون آخر برسیم.
