الگوریتم مسئله مکانیابی p- میانه روی چرخ گراف ها
Publish place: International Conference on Technology and Innovation in Science, Engineering and Technology
Publish Year: 1398
Type: Conference paper
Language: Persian
View: 460
- Certificate
- I'm the author of the paper
Export:
Document National Code:
TIET02_009
Index date: 15 September 2019
الگوریتم مسئله مکانیابی p- میانه روی چرخ گراف ها abstract
در این مقاله به مطالعه و بررسی مسائل p- میانه روی چرخ گراف ها می پردازیم. فرض کنید G=(V,E) یک گراف با تابع طول +l:E⟶R و وزن های راسی نامنفی باشد. هدف مسائل p- میانه، تعیین مکان p سرویس دهنده روی یال ها یا راس های G می باشد بطوری که مجموع کوتاه ترین فواصل وزن دار از هر راس به نزدیک ترین سرویس دهنده مینیمم گردد. در اینجا برای مسئله مکان یابی 1- میانه روی چرخ گراف ها یک الگوریتم خطی پیشنهاد می گردد که با استفاده از این الگوریتم خطی می توان مقدار تابع هدف تمام رئوس در دور را بدست آورد و مقادیر تابع هدف v_0 و رئوس دور را مقایسه کرده و جواب بهینه را بدست آورد. در نتیجه پیچیدگی زمانی مسئله 1- میانه روی چرخ O(n) است که در آن n تعداد رئوس گراف می باشد. در نهایت با یک مثال به طور کامل کاربرد الگوریتم پیشنهادی را تشریح می کنیم.
الگوریتم مسئله مکانیابی p- میانه روی چرخ گراف ها Keywords:
الگوریتم مسئله مکانیابی p- میانه روی چرخ گراف ها authors
رویا نعمتی
کارشناسی ارشد، گروه آموزشی ریاضی، دانشگاه تبریز،