سال انتشار: ۱۳۸۱

محل انتشار: هشتمین کنفرانس سالانه انجمن کامپیوتر ایران

تعداد صفحات: ۷

نویسنده(ها):

محمد قدسی – دانشکده مهندسی کامپیوتر دانشگاه صنعتی شریف
بهزاد زارع مویدی – دانشکده مهندسی کامپیوتر دانشگاه صنعتی شریف

چکیده:

این مقاله الگوریتمی ارائه خواهد شد که قید قابلیت رؤیت را بر مسألة کوتاهترین مسیر پیوندی ١ اعمال می کند. الگوریتم از طریق افراز چندضلعی رؤیت نقطة مستلزم رؤیت، به مجموعه هایی از نواحی که در آن هر ناحیه مجموع فاصله های پیوندی مشخصی از نقاط شروع و پایان دارد، نزدیکترین سکو(یا سکوها)ی مشاهده را می یابد و از این نقاط مسیرهایی کمینه به نقاط شروع و پایان را محاسبه می کند تا مسیر نهایی جواب بدست آید.مبنای کار این الگوریتم گزارش [ ۸] بعنوان مهمترین کار انجام شده در این زمینه می باشد و نکته قابل توجه در الگوریتم ما آنست که در پیچیدگی الگوریتم [ ۸] نمی افزاید