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

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

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

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

حمید ضرابی زاده – دانشکده علوم کامپیوتر دانشگاه واترلو کانادا

چکیده:

دراین مقاله مساله ی یافتن کوتاهترین مسیر برفراز یک زمین چند وجهی مورد مطالعه قرار گرفته و دو الگوریتم تقریبی جدید برای مساله ارائه شده است الگوریتم اول در زمان (فرمول در متن مقاله ) یک مسیر تقریبی را که طول آن حداکثر ۱+e برابر طول کوتاه ترین مسیر L1 برفراز یک زمین چند وجهی است به دست می آورد n تعداد راسهای زمین و N حداکثر تعداد بیتهای مورد نیاز برای نمایش مختصات راس هاست الگوریتم دوم بر پایه ی الگوریتم قبل یک مسیر تقریبی را که طول آن حداکثر (فرمول در متن مقاله ) برابر طول کوتاه ترین مسیر اقلیدسی بر فراز یک زمین است در زمان (فرمول در متن مقاله ) محاسبه می کند حافظه ی مورد نیاز هر دو الگوریتم از مرتبه O(n است.