الگوریتم جستجوی عمق اول

پیمایش گراف و پیمایش درخت
هرس آلفا بتا A* B* Beam الگوریتم بلمن–فورد Best-first Bidirectional الگوریتم جستجوی اول سطح D* الگوریتم جستجوی عمق اول Depth-limited الگوریتم دیکسترا الگوریتم فلوید-وارشال الگوریتم تپه‌نوردی جستجوی عمق اول عمیق‌کننده تکراری الگوریتم جانسون Lexicographic breadth-first Uniform-cost رده:الگوریتم‌های جستجو
جستار وابسته
برنامه‌ریزی پویا Search games

ترتیب پیمایش رئوس در جستجوی عمق اول

در نظریه‌ٔ گراف، جستجوی عمق اول (به انگلیسی: Depth-first Search، به‌اختصار DFS) یک الگوریتم پیمایش گراف است که برای پیمایش یا جستجوی یک درخت یا یک گراف به کار می‌رود.

استراتژی جستجوی عمق اول برای پیمایش گراف، همانطور که از نامش پیداست "جستجوی عمیق‌تر در گراف تا زمانی که امکان دارد" است.

چگونه کار می‌کند؟

الگوریتم از ریشه شروع می‌کند (در گراف‌ها و یا درخت‌های بدون ریشه راس دلخواهی به عنوان ریشه انتخاب می‌شود) و در هر مرحله همسایه‌های رأس جاری را از طریق یال‌های خروجی رأس جاری به ترتیب بررسی کرده و به محض روبه‌رو شدن با همسایه‌ای که قبلاً دیده نشده باشد، به صورت بازگشتی برای آن رأس به عنوان رأس جاری اجرا می‌شود. در صورتی که همهٔ همسایه‌ها قبلاً دیده شده باشند، الگوریتم عقب‌گرد می‌کند و اجرای الگوریتم برای رأسی که از آن به رأس جاری رسیده‌ایم، ادامه می‌یابد. به عبارتی الگوریتم تا آنجا که ممکن است، به عمق بیشتر و بیشتر می‌رود و در مواجهه با بن بست عقب‌گرد می‌کند. این فرایند تامادامیکه همهٔ رأس‌های قابل دستیابی از ریشه دیده شوند ادامه می‌یابد.

همچنین در مسائلی که حالات مختلف متناظر با رئوس یک گراف‌اند و حل مسئله مستلزم یافتن رأس هدف با خصوصیات مشخصی است، جستجوی عمق اول به صورت غیرخلاق عمل می‌کند. بدین‌ترتیب که هر دفعه الگوریتم به اولین همسایهٔ یک رأس در گراف جستجو و در نتیجه هر دفعه به عمق بیشتر و بیشتر در گراف می‌رود تا به رأسی برسد که همهٔ همسایگانش دیده شده‌اند که در حالت اخیر، الگوریتم به اولین رأسی بر می‌گردد که همسایهٔ داشته باشد که هنوز دیده نشده باشد. این روند تا جایی ادامه می‌یابد که رأس هدف پیدا شود و یا احتمالاً همهٔ گراف پیمایش شود. البته پیاده‌سازی هوشمندانهٔ الگوریتم با انتخاب ترتیب مناسب برای بررسی همسایه‌های دیده نشدهٔ رأس جاری به صورتی که ابتدا الگوریتم به بررسی همسایه‌ای بپردازد که به صورت موضعی و با انتخابی حریصانه به رأس هدف نزدیک‌تر است، امکان‌پذیر خواهد بود که معمولاً در کاهش زمان اجرا مؤثر است.

از نقطه نظر عملی، برای اجرای الگوریتم، از یک پشته (stack) استفاده می‌شود. بدین ترتیب که هر بار با ورود به یک رأس دیده نشده، آن رأس را در پشته قرار می‌دهیم و هنگام عقب‌گرد رأس را از پشته حذف می‌کنیم. بنابراین در تمام طول الگوریتم اولین عنصر پشته رأس در حال بررسی است. جزئیات پیاده‌سازی در ادامه خواهد آمد.

وقتی در گراف‌های بزرگی جستجو می‌کنیم که امکان ذخیرهٔ کامل آنها به علت محدودیت حافظه وجود ندارد، در صورتی که طول مسیر پیمایش شده توسط الگوریتم که از ریشه شروع شده، خیلی بزرگ شود، الگوریتم با مشکل مواجه خواهد شد. در واقع این راه‌حل ساده که "رئوسی را که تا به حال دیده‌ایم ذخیره کنیم" همیشه کار نمی‌کند. چراکه ممکن است حافظهٔ کافی برای این کار نداشته باشیم. البته این مشکل با محدود کردن عمق جستجو در هر بار اجرای الگوریتم حل می‌شود که در نهایت به الگوریتم تعمیق تکراری (Iterative Deepening) خواهد انجامید.

الگوریتم

پیمایش با انتخاب رأس $r$ به عنوان ریشه آغاز می‌شود. $r$ به عنوان یک رأس دیده شده برچسب می‌خورد. رأس دلخواه $r_1$ از همسایگان $r$ انتخاب شده و الگوریتم به صورت بازگشتی از $r_1$ به عنوان ریشه ادامه می‌یابد.از این پس در هر مرحله وقتی در رأسی مانند $v$ قرار گرفتیم که همهٔ همسایگانش دیده شده‌اند، اجرای الگوریتم را برای آن رأس خاتمه می‌دهیم. حال اگر بعد از اجرای الگوریتم با ریشهٔ $r_1$ همهٔ همسایگان $r$ برچسب خورده باشند، الگوریتم پایان می‌یابد. در غیر این صورت رأس دلخواه $r_2$ از همسایگان $r$ را که هنوز برچسب نخورده انتخاب می‌کنیم و جستجو را به صورت بازگشتی از $r_2$ به عنوان ریشه ادامه می‌دهیم. این روند تامادامیکه همهٔ همسایگان $r$ برچسب نخورده‌اند ادامه می‌یابد.

البته پیمایش گراف برای تأمین هدفی صورت می‌گیرد. بر این اساس برای انعطاف پذیر ساختن الگوریتم در قبال کاربردهای مختلف، دو نوع عملیات preWORK و postWORK را به همراهِ بازدید از هر رأس یا یال انجام می‌دهیم، که preWORK در زمان برچسب خوردنِ رأسِ در حال بازدید، و postWORK بعد از بررسی هر یالِ خروجی از رأسِ در حال بازدید انجام خواهد شد. هر دوی این عملیات وابسته به هدفِ استفاده از الگوریتم، مشخص خواهند شد.

پیاده‌سازی

یک نسخهٔ بازگشتی الگوریتم به این قرار است:

 1  Algorithm DFS(G,v)
 2  Input : G=(V,E), v(a vetex of G)
 3  Output : depends on the application
 4  begin
 5      mark v
 6      perform preWORK on v
 7      for all edge (v,w) do
 8          if w is unmarked then
 9              DFS(G,w)
10          perform postWORK on (v,w)
11  end

و یک نسخهٔ غیر بازگشتی الگوریتم به این قرار است:

 1  Algorithm DFS(G,v)
 2  Input : G=(V,E), v(a vetex of G)
 3  Output : depends on the application
 4  begin
 5      mark v
 6      perform preWORK on v
 7      Edge = v.First
 8      push v and Edge on the top of the stack
 9      Parent = v
10      while the stack is not empty do
11          remove Edge from the top of the stack
12          while Edge is not nil do
13              Child = Edge->Vertex
14              if Child is unmarked then
15                  mark Child
16                  perform preWORK on Child
17                  push Edge->Next to the top of the stack
18                  Edge = Child.First  
19                  Parent = Child
20                  push Parebtto the top of the stack
21              else
22                  perform postWORK on (Parent,Child)
23                  Edge = Edge->Next
24          remove Child from the top of the stack
25          if the stack is not empty then
26              let Edge and Parent be at the top of the stack
27              perform postWORK on (Parent,Child) 
28  end

که v.First به معنی اولین یال متصل به v و Edge->Vertex به معنی رأس انتهای Edge و Edge->Next به معنی یال بعدی متصل به ابتدای Edge است.

پیچیدگی زمانی

مشخص است که الگوریتم، هر یال در گراف بدون جهت رادقیقاً دوبار (یک بار به بهنگام بررسی هر یک از دو انتها) و هر یال در گراف جهت‌دار را دقیقاً یک بار پیمایش می‌کند. همچنین هر رأس قابل دسترسی از ریشه دقیقاً یک بار بازدید خواهد شد. پس با فرض همبند بودن گراف و اینکه preWORK و postWORK در (1)O انجام شوند، پیچیدگی زمانی جستجوی عمق اول (|O(|V|+|E خواهد بود.

کاربردها

• پیدا کردن مؤلفه‌های همبندی
• مرتب‌سازی موضعی (Topological Sort)
• پیدا کردن مؤلفه‌های قویاً همبند گراف جهت‌دار
• پیدا کردن مؤلفه‌های دوهمبند یالی و رأسی
• حل کردن معماهایی همچون ماز و آنهایی که نیاز به بررسی همه یا بخش بزرگی از حالات ممکن دارند.

پیوند به بیرون

در ویکی‌انبار پرونده‌هایی دربارهٔ الگوریتم جستجوی عمق اول موجود است.

• توضیح و مثال‌هایی از جستجوی عمق اول
• انیمیشن جستجوی عمق اول برای گراف‌های جهت‌دار
• توضیح و پیاده‌سازی جستجوی عمق اول و جستجوی سطح اول
• Dfs Applet

مراجع

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7.
• Udi Manber. Introduction to Algorithms — A Creative Approach. MIT Press and Addison-Wesley, 1989. ISBN 0-201-12037-2.
• Donald E. Knuth. The Art Of Computer Programming Vol 1., Third Edition. Addison-Wesley, 1997. ISBN 0-201-89683-4.
• Douglas B. West. Introduction to Graph Theory, Second Edition. Prentice Hall, 2001. ISBN 0-13-014400-2.