الگوریتم مسئله مکانیابی p- میانه روی چرخ گراف ها
Publish place: International Conference on Technology and Innovation in Science, Engineering and Technology
Publish Year: 1398
نوع سند: مقاله کنفرانسی
زبان: Persian
View: 417
- Certificate
- من نویسنده این مقاله هستم
استخراج به نرم افزارهای پژوهشی:
شناسه ملی سند علمی:
TIET02_009
تاریخ نمایه سازی: 24 شهریور 1398
Abstract:
در این مقاله به مطالعه و بررسی مسائل p- میانه روی چرخ گراف ها می پردازیم. فرض کنید G=(V,E) یک گراف با تابع طول +l:E⟶R و وزن های راسی نامنفی باشد. هدف مسائل p- میانه، تعیین مکان p سرویس دهنده روی یال ها یا راس های G می باشد بطوری که مجموع کوتاه ترین فواصل وزن دار از هر راس به نزدیک ترین سرویس دهنده مینیمم گردد. در اینجا برای مسئله مکان یابی 1- میانه روی چرخ گراف ها یک الگوریتم خطی پیشنهاد می گردد که با استفاده از این الگوریتم خطی می توان مقدار تابع هدف تمام رئوس در دور را بدست آورد و مقادیر تابع هدف v_0 و رئوس دور را مقایسه کرده و جواب بهینه را بدست آورد. در نتیجه پیچیدگی زمانی مسئله 1- میانه روی چرخ O(n) است که در آن n تعداد رئوس گراف می باشد. در نهایت با یک مثال به طور کامل کاربرد الگوریتم پیشنهادی را تشریح می کنیم.
Keywords:
Authors
رویا نعمتی
کارشناسی ارشد، گروه آموزشی ریاضی، دانشگاه تبریز،