حل مساله کوتاهترین مسیر در گرافهای تصادفی در صورت همبستگی بین هزینه یالها با استفاده از بازی بین اتوماتاهای یادگیر
Publish place: 13th Annual Conference of Computer Society of Iran
Publish Year: 1386
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 1,610
This Paper With 8 Page And PDF Format Ready To Download
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ACCSI13_091
تاریخ نمایه سازی: 25 آبان 1386
Abstract:
در اکثر مطالعاتی که در زمینه پیدا کردن کوتاهترین مسیر در گرافهای تصادفی انجام شده است فرض می شود که هزینه یالها مستقل از همدیگر هستند که این فرض در بسیاری از موارد فرض
صحیحی نمی باشد چرا که ممکن است تغییر ترافیک در یک قسمت از شبکه ناشی از تغییر ترافیک در قسمتهای مجاور آن باشد. مساله پیدا کردن کوتاهترین مسیر احتمالی با یالهای همبسته در رایطی که توزیعهای احتمالی وزن یالها از قبل مشخص است برای اولین بار توسط بارتون ١ و پس از آن توسط والر ٢ و زیلیاسکوپولس ٣ و فن ٤ مورد بررسی قرار گرفت و الگوریتم هایی جهت حل آن پیشنهاد گردید. در این مقاله برای اولین بار الگوریتمی برای حل مساله کوتاهترین مسیر گرافهای تصادفی در شرایطی که همبستگی مابین هزینه یالها وجود دارد ٥(SSPCL) و همچنین توزیعهای احتمالی وزن یالها از قبل شناخته شده نیست پیشنهاد میگردد. در الگوریتم پیشنهادی از بازی بین اتوماتاهای یادگیر برای پیدا کردن کوتاهترین مسیر بین یک گره و دیگر گره های گراف استفاده میشود. الگوریتم پیشنهادی سعی میکند با حداقل تعداد نمونه گیری از یالهای گراف تصادفی درخت کوتاهترین مسیر را برای یک گره ریشه مشخص پیدا نماید.
Keywords:
Authors
اصغر قربانی
آزمایشگاه سیستمهای نرم افزاری، دانشکده مهندسی کامپیوتر و فناوری اطل
محمدرضا میبدی
آزمایشگاه سیستمهای نرم افزاری، دانشکده مهندسی کامپیوتر و فناوری اطل
مراجع و منابع این Paper:
لیست زیر مراجع و منابع استفاده شده در این Paper را نمایش می دهد. این مراجع به صورت کاملا ماشینی و بر اساس هوش مصنوعی استخراج شده اند و لذا ممکن است دارای اشکالاتی باشند که به مرور زمان دقت استخراج این محتوا افزایش می یابد. مراجعی که مقالات مربوط به آنها در سیویلیکا نمایه شده و پیدا شده اند، به خود Paper لینک شده اند :