یافتن دور همیلتونی با الگوریتم پس گرد – به زبان ساده

«مسیر همیلتونی» (Hamiltonian Path) در یک گراف غیر جهت‌دار، مسیری است که در آن هر «راس» (Vertex) دقیقا یک‌بار مشاهده می‌شود. انواع مختلفی از دور در گراف وجود دارد. دور همیلتونی یکی از آن‌ها است. یک «دور همیلتونی» یا «مدار همیلتونی» (Hamiltonian Cycle | Hamiltonian Circuit)، یک مسیر همیلتونی است که در آن از آخرین راس به اولین راس یک «یال» (Edge) وجود دارد. در ادامه، روشی جهت بررسی اینکه آیا در یک گراف داده شده، دور همیلتونی وجود دارد یا خیر بررسی می‌شود. همچنین، در  صورت وجود دور، مسیر آن را چاپ می‌کند. در واقع، با استفاده از یک روش ساده و یک روش «پس‌گرد» (Backtracking)، بررسی می‌شود که آیا در یک گراف دور همیلتونی وجود دارد یا خیر و در صورت وجود، مسیر در خروجی چاپ می‌شود. ورودی و خروجی تابع لازم برای این کار به صورت زیر هستند.

یافتن دور همیلتونی در گراف

برای یافتن دور همیلتونی در گراف، به طور کلی به صورت زیر عمل می‌شود.

ورودی:

یک آرایه دوبُعدی [graph[V][V که در آن V تعداد راس‌ها در گراف و [graph[V][V «ماتریس همسایگی» (Adjacency Matrix) گراف است. مقدار [graph[i][j در صورت وجود یک یال مستقیم از راس i به راس j برابر با یک و در غیر این صورت، [graph[i][j برابر با صفر است.

خروجی:

یک آرایه [path[V باید حاوی یک مسیر همیلتونی باشد. [path[i باید راس i در مسیر همیلتونی را نمایش دهد. همچنین، کد باید مقدار false را در صورت عدم وجود دور همیلتونی در گراف، بازگرداند.

فیلم آموزش طراحی الگوریتم – جامع و با مفاهیم کلیدی در فرادرس

کلیک کنید

برای مثال، دور همیلتونی در گراف زیر به صورت {۰ ،۳ ،۴ ،۲ ،۱ ، ۰} است.

(0)--(1)--(2)
|    / \   |
|    / \   | 
|    / \   |
(3)-------(4)

گراف زیر حاوی هیچ دور همیلتونی نیست.

(0)--(1)--(2)
|    / \   |
|    / \   | 
|    / \   |
(3)       (4)

الگوریتم ساده (Naive Algorithm)

الگوریتم ساده‌ای که در زیر ارائه شده، همه پیکربندی‌های ممکن برای راس‌ها را ارائه می‌کند و پیکربندی که محدودیت های داده شده را ارضا می‌کند، باز می‌گرداند. به تعداد !n، پیکربندی ممکن وجود دارد.

یافتن دور همیلتونی با الگوریتم پس‌گرد (Backtracking Algorithm)

این الگوریتم یک آرایه مسیر خالی می‌سازد و راس ۰ را به آن اضافه می‌کند.

در ادامه، دیگر راس‌ها را با آغاز از راس ۱ به آرایه اضافه می‌کند؛ اما پیش از اضافه کردن یک راس، بررسی می‌کند که آیا با راس پیشین اضافه شده مجاور است یا خیر و همچنین، بررسی می‌کند که راس، پیش از این به آرایه اضافه نشده باشد. اگر چنین راسی پیدا شود، یال به عنوان بخشی از راهکار اضافه می‌شود. اگر راس پیدا نشود، مقدار false بازگردانده می‌شود.

پیاده‌سازی الگوریتم پس‌گرد برای مساله یافتن دور همیلتونی در گراف

در ادامه، پیاده‌سازی الگوریتم پس‌گرد برای مساله یافتن دور همیلتونی در گراف در زبان‌های برنامه‌نویسی گوناگون ارائه شده است.

++C

C

پایتون

جاوا

سی شارپ

خروجی:

Solution Exists: Following is one Hamiltonian Cycle
 0  1  2  4  3  0

Solution does not exist

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

افرادی که قصد تغییر دادن نقطه شروع را دارند، باید دو تغییر در کد بالا اعمال کنند. تغییر «;path[0] = 0» به «;path[0] = s» که در آن، s نقطه شروع جدید است. همچنین، باید حلقه «(++for (int v = 1; v < V; v» در ()hamCycleUtil، به «(++for (int v = 0; v < V; v» تغییر پیدا کند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌‌نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• زبان برنامه‌نویسی پایتون (Python) — از صفر تا صد
• آموزش ساختمان داده — مجموعه مقالات جامع وبلاگ فرادرس
• ساختمان داده (Data Structure) — راهنمای جامع و کاربردی

^^