آموزش الگوریتم مورچگان از صفر تا صد

کوتاهترین مسیر در گراف و الگوریتم کلونی مورچگان

توی چند مطلب آینده قصد داریم یکی از مهمترین چالش های مربوط به الگوریتم کلونی مورچه ها در حل مسئله کوتاهترین مسیر در گراف رو بیان کنیم.

مسئله کوتاهترین مسیر در گراف : فرض کنید ما یک گراف داریم که شامل چندین گره است و مسیرهای نیز بین  این گره ها وجود دارد که آنها را یال می نامیم. هر یال در واقع فاصله بین دوتا گره است. در این گراف دو گره خاص وجود دارد ، گره مبدا (source ) و گره مقصد (destination). هدف مسئله این است که مسیری را از گره مبدا به گره مقصد پیدا کنیم که کمترین مسافت را داشته باشد. مسافت برابر است با مجموع طول یال های که از گره مبدا تا گره مقصد طی می کنیم. دقت داشته باشید ممکن است بین بعضی از گره ها در گراف مسیر (یالی) وجود نداشته باشد

فرض کنید ما گراف زیر رو داریم

توی گراف بالا گره مبدا، گره مقصد و کوتاه ترین مسیر از مبدا به مقصد مشخص شده است

اگر ما بخواهیم مسئله کوتاهترین مسیر در گراف رو با الگوریتم کلونی مورچگان حل کنیم، گره مبدا معادل لانه مورچه ها هستش و گره مقصد معادل غذا هستش. مورچه ها باید سعی کنن از بین مسیرهای زیادی که بین لانه تا غذا است کوتاهترین مسیر رو پیدا کنن.

مهمترین تفاوت این مسئله با مثال های که قبلا بیان کردیم این بوده که توی اونا ما دو تا مسیر کاملا مجزا از هم داشتیم و این مسیر ها غیر از دو نقطه یعنی منبع و مقصد هیچ نقطه مشترکی با هم نداشتن. به عبارت دیگر مسیرها کاملا از هم مجزا بودند.

همین تفاوت باعث میشه که یک سری چالش برای مورچه های که قصد دارن این مسئله رو حل کنن به وجود بیاد. مهمترین این چالش ها ایجاد حلقه است. یعنی ممکن است مورچه ها توی یک حلقه بیفتن ودور خودشون بچرخن.

توی این مطلب خواستیم نگاشتی بین آزمایش های مرتبط با الگوریتم کلونی مورچه ها که قبلا بیان کردیم (آزمایش 1 ، آزمایش2، آزمایش 3) و مسئله کوتاهترین مسیر در گراف ، ایجاد کنیم و نیز یک چالش مهم در حل مسئه که گیر افتادن توی حلقه است رو یک اشاره بهش کنیم. به نظر شما این مسئله چطوری باید حل بشه؟

منبع (اطلاعات بیشتر)

MrMining.ir