مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

این صفحه فقط خواندنی است. شما می‌توانید متن صفحه را مشاهده کنید، اما نمی‌توانید آن را تغییر دهید. اگر فکر می‌کنید که مشکلی رخ داده است، مدیر ویکی را در جریان بگذارید.
====== پیمایش گراف ======
الگوریتم‌های پیمایش گراف برای پیمایش گراف ورودی مسأله یا گراف حالت‌های مسأله یا درون الگوریتم‌های دیگر به کار می‌روند. در ادامه در مورد این الگوریتم‌ها، کاربرد آنها و زمان اجرای آنها صبحت می‌کنیم.
===== پیمایش گراف =====
در این مسأله هدف دیدن تمامی رأسهای یک گراف است. اگر گراف همبند نباشد، این الگوریتم‌ها را روی هر کدام از مؤلفه‌های همبندی آن اجرا می‌کنیم. پایان این الگوریتم‌ها زمانی است که مطمئن شویم هیچ رأس دیده نشده‌ای وجود ندارد. با پیمایش گراف می‌توانیم مؤلفه‌های همبندی آن را هم پیدا کنیم؛ به این صورت که هر بار که همه‌ی رأسهای متصل به رأسهای فعلی را پیمایش کردیم (این رأسها متعلق به مؤلفه‌ی همبندی فعلی هستند)، اگر رأس دیده‌نشده‌ای در گراف بود، به این معنی است که در مؤلفه‌ی همبندی دیگری است.
=== پیمایش اول-عمقی ===
در پیمایش اول-عمقی، از یک رأس شروع می‌کنیم و به یکی از همسایه‌های آن می‌رویم و این کار را ادامه می‌دهیم تا به رأسی برسیم که همه‌ی رأسهای مجاور آن قبلاً دیده شده‌اند یا رأس مجاوری ندارد. سپس [[الگوریتم:جستجوی_کامل|پس‌گرد]] می‌کنیم و به رأس قبلی برمی‌گردیم. سه نوع علامت‌گذاری برای رأسها قایل می‌شویم: رأس در حال دیدن، رأس به بن بست رسیده، رأس دیده نشده. این علامت‌گذاری‌ها را در آرایه‌ای ذخیره می‌کنیم. ابتدای کار همه‌ی رأسها دیده نشده هستند و هر بار که به یک رأس دیده نشده می‌رویم این رأس را در حال دیدن می‌کنیم و تا زمانی که رأسی همسایه دیده نشده دارد، به بن‌بست نمی‌رسد. وقتی همه‌ی همسایه‌های یک رأس دیده شده باشند، آن را بن بست علامت‌گذاری می‌کنیم. پایان این الگوریتم زمانی است که همه‌ی رأسها بن‌بست علامت گذاری شده باشند و به رأس ابتدا برگشته باشیم.

این الگوریتم را می‌توان به دو صورت بازگشتی و با حلقه تکرار (و استفاده از یک پشته) پیاده‌سازی کرد.

کاربرد این الگوریتم برای بررسی تمام حالت‌های یک مسأله، حل شبکه شار و تطابق و پیمایش گراف است.

زمان اجرای این الگوریتم $O(|V|+|E|)$ است که $|V|$ تعداد رأسها و $|E|$ تعداد یالها است.

[[http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C_%D8%B9%D9%85%D9%82_%D8%A7%D9%88%D9%84|مطالب بیشتر در مورد جستجوی عمقی...]]
=== پیمایش اول-عرضی ===
در پیمایش اول-عرضی، ابتدا تمامی همسایه‌های یک رأس را می‌بینیم، سپس همسایه‌های این همسایه‌ها را می‌بینیم و این کار را ادامه می‌دهیم تا تمامی رأسها دیده شوند. برای پیاده‌سازی این الگوریتم از یک صف کمک می‌گیریم که در آن ابتدا رأس شروع را قرار می‌دهیم، سپس این رأس را بر می‌داریم و همسایه‌های آن را در صف قرار می‌دهیم. همین کار را ادامه می‌دهیم. باید رأسها را علامت بزنیم چون در غیر این صورت در حلقه می‌افتیم. مشابه جستجوی اول-عمقی، رأسها دیده نشده هستند تا وقتی که در صف قرار می‌گیرند و در حال دیدن می‌شوند. وقتی که از صف خارج می‌شوند هم کار آنها پایان یافته است. پایان این الگوریتم زمانی است که هر کدام از رأسها حداقل یک بار از صف خارج شده باشند و صف خالی باشد.

یکی از کاربردهای این الگوریتم پیدا کردن کوتاهترین مسیر از مبدأ در گراف بدون وزن است: کافی است آرایه‌ای بگیریم و در آن طول کوتاهترین مسیر تا هر رأس را نگه داریم و هر بار همسایه‌های هر رأس را در صورتی که فاصله‌ی از مبدأ تا این همسایه‌ها از فاصله مبدأ تا این رأس +۱ بیشتر بود، آن را به روز کنیم. این الگوریتم در بررسی حالت‌های مسأله، حل شبکه شار و پیمایش گراف کاربرد دارد.

زمان اجرای این الگوریتم $O(|V|+|E|)$ است که $|V|$ تعداد رأسها و $|E|$ تعداد یالها است.

[[http://fa.wikipedia.org/wiki/%D8%A7%D9%84%DA%AF%D9%88%D8%B1%DB%8C%D8%AA%D9%85_%D8%AC%D8%B3%D8%AA%D8%AC%D9%88%DB%8C_%D8%A7%D9%88%D9%84_%D8%B3%D8%B7%D8%AD|مطالب بیشتر در مورد جستجوی عرضی...]]

===== مسایل نمونه =====
۱- مورچه‌ای با شروع از لانه، در ۴ جهت اصلی روی یک نقشه جدولی شکل می‌تواند حرکت کند. این مورچه‌ حداکثر ۶۰ واحد طی می‌کند تا بالاخره به غذا برسد. بقیه مورچه‌ها می‌خواهند از لانه به سمت غذا بروند و فقط می‌توانند از مسیرهایی که این مورچه طی کرده بروند. طول کوتاه‌ترین مسیر تا غذا را پیدا کنید.

جواب: 
یک جدول ۱۲۱*۱۲۱ داریم (چون حداکثر ۶۰ واحد در هر جهت حرکت کرده است) که مرکز آن محل شروع حرکت مورچه است. هر رأس جدول را یک رأس گراف می‌گیریم و به ۴ رأس متناظر خانه‌های مجاور آن در جدول با یال وصل می‌کنیم. یک گراف بدون وزن به دست می‌آید و می‌توانیم با پیمایش عرضی از رأس محل شروع حرکت مورچه، تا رسیدن به رأس محل غذا، مسیر را پیدا کنیم. برای این کار لازم است به رأس شروع مقدار ۰ را نسبت بدهیم و هر بار که رأسی را از صف خارج می‌کنیم، اگر فاصله‌ی همسایه‌های رأس فعلی (که تا کنون دیده نشده‌اند) از طریق این رأس کمتر شد، آن را به روز کنیم.

۲-تعداد ۹ ساعت با حروف $A-I$ علامت‌گذاری شده‌اند و هر کدام روی یکی از اعداد $3,6,9,12$ تنظیم هستند. در کل ۹ حرکت داریم که هر حرف به معنی جلو کشیدن آن ساعت به میزان ۳ ساعت است:''ABDE, ABC, BCEF, ADG, BDEFH, CFI, DEGH, GHI, EFHI''. به ازای یک تنظیم دلخواه از ساعت‌ها، کوتاهترین دنباله‌ی حرکات تا رساندن همه‌ی ساعت‌ها به $12$ بیابید. اگر بیشتر از یک راه برای این کار وجود دارد، راهی را بنویسید که از نظر عددی کمتر است.

جواب: هر رأس متناظر یک وضعیت از مسأله، یعنی ۴ حالت برای ۹ ساعت، است. از هر رأس به ازای هر کدام از حرکت‌های مجاز به رأس دیگری می‌رویم. پس از ساعت گراف، از رأس متناظر حالت شروع داده شده در مسأله، تا رسیدن به رأس همه ۱۲ کوتاهترین مسیر را مشابه سوال قبل به دست می‌آوریم.

[[http://activities.tjhsst.edu/sct/lectures/1314/graph_searching_10_18_13.pdf|منبع سوالات]]
مسابقه‌ی بین‌المللی برنامه‌سازی دانش‌جویی

ابزار کاربر

ابزار سایت

ابزار صفحه
