الگوریتم جواب بهین برای مسائل کوتاهترین مسیر اصلاحی روی برخی شبکه های خاص تحت فاصله همینگ
سال انتشار: 1399
نوع سند: مقاله کنفرانسی
زبان: فارسی
مشاهده: 720
فایل این مقاله در 7 صفحه با فرمت PDF قابل دریافت می باشد
- صدور گواهی نمایه سازی
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
ICIORS13_013
تاریخ نمایه سازی: 6 آذر 1399
چکیده مقاله:
مسائل کوتاهترین مسیر، نقش بسیار مهمی در زمینه علوم مختلف از جمله علم کامپیوتر، شبکه های ارتباطی و شبکه های حمل ونقل دارند. در مساله کوتاه ترین مسیر اصلاح شده تحت فاصله همینگ، یک شبکه وزن دار با مجموعه ای از جفت مبدأ مقصدها داده می شود. هدف این است که طول یال ها را با صرف کمترین هزینه تحت فاصله همینگ تغییر دهیم تا این که فاصله های اصلاح شده میان مبداها و مقصدها از مقادیر مفروض کمتر شوند. با توجه به این نکته که مساله کوتاهترین مسیر اصلاح شده تحت فاصله همینگ روی شبکه های کلی NPسخت است، در این مقاله مساله مذکور را روی برخی شبکه های خاص از جمله شبکه های زنجیری و درختهای ریشه دار مورد مطالعه قرار داده و برای آنها الگوریتم حل ارائه می کنیم.
کلیدواژه ها:
نویسندگان
مهدیه امیرپور
دانشجوی کارشناسی ارشد، گروه ریاضی کاربردی، دانشگاه صنعتی سهند
بهروز علی زاده
عضو هیات علمی گروه ریاضی کاربردی، دانشگاه صنعتی سهند
رقیه اعتماد
محقق پسا دکتری، گروه ریاضی کاربردی، دانشگاه صنعتی سهند