Hamiltonian Path هر رأس را دقیقاً یک بار بازدید میکند؛ اگر به شروع برگردد Cycle داریم. در این مقاله قرار نیست فقط چند خط کد ببینیم؛ ابتدا مسئله را شهودی میفهمیم، بعد مراحل، کاربردهای واقعی، هزینه اجرای الگوریتم و محدودیتهای آن را بررسی میکنیم.
این الگوریتم چه مسئلهای را حل میکند؟
Hamiltonian Path & Cycle زمانی ارزشمند است که ساختار مسئله را به صورت گراف ببینیم. قبل از کدنویسی باید بدانیم Vertexها چه چیزی هستند، Edgeها چه رابطهای را نشان میدهند و خروجی مورد انتظار دقیقاً چیست.
ایده اصلی به سادهترین شکل
با Backtracking یک ترتیب معتبر از رأسها میسازیم و در بنبست انتخاب قبلی را برمیگردانیم.
مراحل اجرا
- یک رأس شروع انتخاب میکنیم.
- یک همسایه استفادهنشده را امتحان میکنیم.
- در بنبست Backtrack میکنیم.
- اگر همه رأسها استفاده شدند مسیر پیدا شده است.
نمونه کد JavaScript
function hamiltonian(graph) {
const nodes = Object.keys(graph);
function search(path, used) {
if (path.length === nodes.length) return path;
for (const v of graph[path.at(-1)] ?? []) if (!used.has(v)) {
used.add(v);
const r = search([...path,v], used);
if (r) return r;
used.delete(v);
}
return null;
}
for (const s of nodes) { const r = search([s], new Set([s])); if (r) return r; }
return null;
}مثالهای واقعی و دنیای کار
- برنامهریزی بازدید بدون تکرار
- Graph Puzzle
- Route Sequencing
- مبنای ساختاری TSP
پیچیدگی زمانی و فضایی
در حالت ساده نمایی و حدود O(V!)
چه زمانی استفاده کنیم؟
وقتی هر رأس باید دقیقاً یک بار بازدید شود
چه زمانی مناسب نیست؟
برای گراف بزرگ brute force عملی نیست.
جمعبندی
Hamiltonian Path & Cycle را زمانی انتخاب کنید که نوع گراف و هدف مسئله با ویژگیهای آن همخوان باشد. مهمترین نکته این است که الگوریتم را به خاطر اسمش استفاده نکنیم؛ ابتدا مسئله را مدل کنیم و سپس ابزار مناسب را انتخاب کنیم.