4696

الگوريتمهاي مسيريابي در كاربردهاي داخل ساختمان

۹۶-۹۷

دكتر سعيد عبادالهي

پيشرفت و رشد تكنولوژي‌هاي كامپيوتري و گوشي‌هاي هوشمند بر هيچ‌كس پوشيده نيست امروزه بازي‌ها و نرم‌افزارهاي بسيار زيادي را مي‌توان يافت كه نياز به يافتن مسيري بين دو نقطه دارند مسيري كه داراي ويژگي‌هاي خاصي ازجمله كوتاه‌ترين يا سريع‌ترين مسير بودن باشد. به همين منظور از قرن 19 تاكنون الگوريتم‌هاي زيادي براي حل اين‌گونه مسائل مطرح شده‌اند. در يك دسته‌بندي كلي اين الگوريتم‌ها را مي‌توان به دو بخش آگاهانه و ناآگاهانه دسته‌بندي كرد. تفاوت اصلي بين اين دو الگوريتم در ميزان اطلاعاتي است كه الگوريتم از مسئله در اختيار دارد. در مبحث الگوريتم‌هاي ناآگاهانه، الگوريتم‌هايي مانند اول عمق، اول سطح، هزينه يكسان، ديكسترا، اول عمق محدود، اول عمق محدود تكراري موردبررسي قرار مي‌گيرند كه در اين ميان الگوريتم ديكسترا بهترين عملكرد را دارد و در مبحث الگوريتم‌هاي آگاهانه، الگوريتم‌هايي مانند A* ،اول بهترين حريصانه، اول بهترين تكراري،SMA* ، IDA*، Jump Point Search، فلويد وارشال و بلمن- فورد مورد برسي قرار مي‌گيرند كه در اين ميان الگوريتم Jump Point Search بهترين عملكرد را ميان ساير الگوريتم‌ها دارد. مقايسه بين الگوريتم‌هاي آگاهانه و ناآگاهانه بر اساس چهار معيار اصلي كامل بودن(يافتن پاسخ)، بهينه بودن الگوريتم، ميزان پيچيدگي زماني و ميزان پيچيدگي فضايي(حافظه‌ي لازم براي ذخيره گره‌هاي پيمايش شده) انجام‌شده است.

5/16/2018 12:00:00 AM

53537

1397/03/26