کوتاهترین مسیر برفراز یک زمین چند وجهی
- سال انتشار: 1383
- محل انتشار: دهمین کنفرانس سالانه انجمن کامپیوتر ایران
- کد COI اختصاصی: ACCSI10_101
- زبان مقاله: فارسی
- تعداد مشاهده: 852
نویسندگان
دانشکده علوم کامپیوتر دانشگاه واترلو کانادا
چکیده
دراین مقاله مساله ی یافتن کوتاهترین مسیر برفراز یک زمین چند وجهی مورد مطالعه قرار گرفته و دو الگوریتم تقریبی جدید برای مساله ارائه شده است الگوریتم اول در زمان (فرمول در متن مقاله ) یک مسیر تقریبی را که طول آن حداکثر 1+e برابر طول کوتاه ترین مسیر L1 برفراز یک زمین چند وجهی است به دست می آورد n تعداد راسهای زمین و N حداکثر تعداد بیتهای مورد نیاز برای نمایش مختصات راس هاست الگوریتم دوم بر پایه ی الگوریتم قبل یک مسیر تقریبی را که طول آن حداکثر (فرمول در متن مقاله ) برابر طول کوتاه ترین مسیر اقلیدسی بر فراز یک زمین است در زمان (فرمول در متن مقاله ) محاسبه می کند حافظه ی مورد نیاز هر دو الگوریتم از مرتبه O(n است.کلیدواژه ها
هندسه ی محاسباتی، الگوریتم تقریبی، کوتاه ترین مسیر، زمین چند وجهیمقالات مرتبط جدید
اطلاعات بیشتر در مورد COI
COI مخفف عبارت CIVILICA Object Identifier به معنی شناسه سیویلیکا برای اسناد است. COI کدی است که مطابق محل انتشار، به مقالات کنفرانسها و ژورنالهای داخل کشور به هنگام نمایه سازی بر روی پایگاه استنادی سیویلیکا اختصاص می یابد.
کد COI به مفهوم کد ملی اسناد نمایه شده در سیویلیکا است و کدی یکتا و ثابت است و به همین دلیل همواره قابلیت استناد و پیگیری دارد.