حل مساله کوتاهترین مسیر در گرافهای تصادفی در صورت همبستگی بین هزینه یالها با استفاده از بازی بین اتوماتاهای یادگیر

در اکثر مطالعاتی که در زمینه پیدا کردن کوتاهترین مسیر در گرافهای تصادفی انجام شده است فرض می شود که هزینه یالها مستقل از همدیگر هستند که این فرض در بسیاری از موارد فرض صحیحی نمی باشد چرا که ممکن است تغییر ترافیک در یک قسمت از شبکه ناشی از تغییر ترافیک در قسمتهای مجاور آن باشد. مساله پیدا کردن کوتاهترین مسیر احتمالی با یالهای همبسته در رایطی که توزیعهای احتمالی وزن یالها از قبل مشخص است برای اولین بار توسط بارتون ١ و پس از آن توسط والر ٢ و زیلیاسکوپولس ٣ و فن ٤ مورد بررسی قرار گرفت و الگوریتم هایی جهت حل آن پیشنهاد گردید. در این مقاله برای اولین بار الگوریتمی برای حل مساله کوتاهترین مسیر گرافهای تصادفی در شرایطی که همبستگی مابین هزینه یالها وجود دارد ٥(SSPCL) و همچنین توزیعهای احتمالی وزن یالها از قبل شناخته شده نیست پیشنهاد میگردد. در الگوریتم پیشنهادی از بازی بین اتوماتاهای یادگیر برای پیدا کردن کوتاهترین مسیر بین یک گره و دیگر گره های گراف استفاده میشود. الگوریتم پیشنهادی سعی میکند با حداقل تعداد نمونه گیری از یالهای گراف تصادفی درخت کوتاهترین مسیر را برای یک گره ریشه مشخص پیدا نماید.

کلیدواژه ها:

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