حل تشریحی سوال شماره 88 دروس تخصصی مشترک

مسئله مسیریابی از نقطه s به نقطه g در شکل زیر را در نظر بگیرید در هر مرحله فقط یک خانه در راستای عمودی یا افقی میتوان حرکت کرد حرکت به خانه های هاشورزده شده یا به خارج از صفحه مجاز نمی باشد. اگر از فاصله منهتن (مجموع فواصل افقی و عمودی دو نقطه به عنوان تابع اکتشافی heuristic استفاده شود و از گسترش گره های تکراری اجتناب گردد آنگاه روش جستجوی اول بهترین حریصانه (greedy best - first) چه تعداد گره را تا رسیدن به هدف گسترش میدهد؟ اولویت حرکتها به ترتیب بالا - چپ - راست و پایین است و در صورتی که نودهایی با مقدار مساوی تولید شوند به ترتیب زمان تولید گسترش می یابند.