الگوریتم های مسیریابی – بخش دوم (الگوریتم *A)

الگوریتم مسیریابی *A:

یکی از مشکلات الگوریتم دیکسترا این بود که برای یافتن کوتاه ترین مسیر تمامی ریوس در تمامی جهات را بررسی کرده و پس از طی این روند طولانی به راس مقصد می رسید . برای حل این مشکل الگوریتم A* ارایه شد.

برای آشنایی با روند این الگوریتم به مثال زیر توجه کنید:

فرض کنید شخصی از نقطه ی A می خواهد به نقطه ی B برود و مانعی بین این دو نقطه قرار گرفته است. در شکل 2 این وضعیت نشان داده شده است، که خانه ی سبز نقطه ی A ، خانه ی قرمز نقطه ی B و خانه های آبی نشان دهنده ی مانع می باشند.

2 thumb الگوریتم های مسیریابی   بخش دوم (الگوریتم *A)

 

باید توجه نمود که در این مثال، منطقه ی مورد جستجو به صورت گرید در آمده. این کار منطقه ی مورد نظر را به صورت یک آرایه ی دو بعدی نمایش می دهد. هر عضو این آرایه نماینده ی یک مربع در شبکه بوده و وضعیت آن آرایه به صورت قابل عبور یا غیر قابل عبور بودن آن مشخص می شود. کوتاه ترین مسیر، با تعیین آرایه هایی که باید از مبدا به مقصد طی شوند، به دست می آید. وقتی که مسیر یافت شد، شخص مورد نظر با گذر از نقطه ی میانی هر مربع ( راس ) به مقصد می رسد.

در مرحله ی بعد، با شروع از نقطه ی A ، نقاط مجاور را کنترل کرده تا به مقصد برسیم. جستجو را به صورت زیر آغاز می کنیم:

1- نقطه ی A را وارد لیست باز می کنیم. این لیست شامل نقاطی است که باید وضعیت آنها مورد بررسی قرار بگیرد.

2- از نقاط مجاور A ، آن هایی که وضعیت قابل عبور دارند را در لیست باز قرار داده و راس A را به عنوان راس پدر آن ها منظور می کنیم.

3- نقطه ی A را از لیست باز به لیست بسته می بریم. لیست بسته شامل نقاطی است که بررسی آن ها انجام شده.

سپس یکی از نقاط لیست باز را به صورت زیر انتخاب می کنیم:

تابع F = G + H را درنظر میگیریم .

G : مسافت از راس مبدا به راس جاری

H : برآورد مسافت از راس جاری به راس مبدا

کوتاه ترین مسیر با مراجعه به لیست باز و انتخاب راس با کوچک ترین F و تکرار این عملیات به دست خواهد آمد.

همان طور که در بالا توضیح داده شده است، G مسافت از راس مبدا به راس جاری می باشد. در این مثال ، مسافت طی مسیر افقی و عمودی بین دو راس مجاور 10 و مسافت طی مسیر قطری 14 در نظر گرفته شده است. برای محاسبه ی G هر راس در طول مسیر بایدمسافت طی شده به مقدار G راس پدر آن اضافه شده و به عنوان G راس جدید در نظر گرفته شود.

مقدار H به روش های مختلفی، می تواند برآورد شود. در این مثال از متد منهتن ( Manhattan ) استفاده شده است که مسافت از راس جاری تا راس مبدا را تنها با حرکات افقی و عمودی و بدون در نظر گرفتن موانع محاسبه می کند.

با جمع نمودن مقادیر G و H مقدار F محاسبه می شود. نتیجه ی اولین جستجو در شکل زیر نشان داده شده است. مقدارF بالا سمت چپ، G پایین سمت چپ و H پایین سمت راست نمایش داده شده است:

 

3 thumb الگوریتم های مسیریابی   بخش دوم (الگوریتم *A)

در ادامه ی جستجو از بین نقاط در لیست باز، نقطه ای با کوچکترین F انتخاب شده و موارد زیر را دنبال می کنیم :

1- این نقطه را از لیست باز به لیست بسته منتقل می کنیم.

2- نقاط مجاور را کنترل کرده و نقاط جدید را وارد لیست باز نموده و راس قبلی را به عنوان راس پدر آن ها در نظر میگیریم.

3- اگر راس مجاور از قبل در لیست باز بود ، مسیر با G کمتر را انتخاب می کنیم.

موارد بالا در شکل زیر نمایش داده شده است:

4 thumb الگوریتم های مسیریابی   بخش دوم (الگوریتم *A)

 

این روند را ادامه داده تا راس مقصد وارد لیست بسته شود. با چندین مرتبه تکرار، منطقه ی مورد جستجو به صورت شکل زیر در می آید.

 

5 thumb الگوریتم های مسیریابی   بخش دوم (الگوریتم *A)

اکنون برای پیدا کردن مسیر، از راس مقصد شروع به حرکت نموده و راس پدر هر نقطه را علامت گذاری می کنیم. با ادامه ی این روند به راس مبدا رسیده و کوتاه ترین مسیر از مبدا به مقصد مطابق شکل زیر یافت شده است.

 

6 thumb الگوریتم های مسیریابی   بخش دوم (الگوریتم *A)

بدین ترتیب در روش A* ، تنها نقاطی از گراف که بین راس مبدا و مقصد واقع شده اند، بررسی شده و با پایان یافتن الگوریتم، کوتاه ترین مسیر به مقصد یافت می شود.

Требуется вовлечение настоящих специалистов, которые будут прорабатывать тексты с учетом их маркетинговой составляющей и не в ущерб релевантности, веб-мастера, которые доведут верстку и код сайта до идеала, а так же множество других нюансов по продвижению сайта TopOdin – надежное продвижение | создание сайтов, поисковая оптимизация: Продвижение в Google – раскрутка сайта Обратите внимание на некоторые особенности, которые присущи раскрутке и продвижению сайта в Google

مطالب مرتبط

2 نظر

  1. جواد

    با سلام
    از اینکه مطالب را مثل سایر سایت ها با رمز و … و عضویت و … نگذاشته اید و همه می توانند از آن استفاده نمایند جای تشکر و قدردانی دارد .
    امیدوارم که بتوانید لایه های اطلاعاتی مربوط به کشور خودمان را نیز در سایت قراردهید .

    پاسخ

نظر بدهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *