مسئله‌ی Hamiltonian Path و Hamiltonian Cycle از مسائل کلاسیک نظریه گراف هستند و روی یک سؤال ساده اما مهم تمرکز دارند:

آیا می‌توان مسیری پیدا کرد که هر رأس گراف را دقیقاً یک بار بازدید کند؟

اگر چنین مسیری وجود داشته باشد به آن Hamiltonian Path می‌گوییم.

اگر علاوه بر این، آخرین رأس دوباره به رأس شروع متصل شود و مسیر یک دور بسته بسازد، یک Hamiltonian Cycle داریم.

این مسئله از نظر ظاهری شبیه بعضی مسائل مسیر‌یابی است، اما تفاوت مهمی با Shortest Path، Eulerian Path و Travelling Salesman Problem دارد. در این مقاله این تفاوت‌ها را از صفر بررسی می‌کنیم و بعد سراغ Backtracking، پیاده‌سازی JavaScript، پیچیدگی و کاربردهای واقعی می‌رویم.

تعریف ساده Hamiltonian Path

فرض کنید گراف زیر را داریم:

Code

A -- B -- C
|         |
D ------- E

یک Hamiltonian Path باید:

از یکی از رأس‌ها شروع کند.
هر رأس را دقیقاً یک بار ببیند.
بین هر دو رأس متوالی یک یال معتبر وجود داشته باشد.
لازم نیست به نقطه شروع برگردد.

مثلاً:

Code

D → A → B → C → E

اگر همه یال‌های این مسیر در گراف وجود داشته باشند، این یک Hamiltonian Path معتبر است.

Hamiltonian Cycle چیست؟

Hamiltonian Cycle همان Hamiltonian Path است، با یک شرط اضافه:

آخرین رأس باید به رأس شروع متصل باشد.

مثلاً:

Code

A → B → C → E → D → A

اگر تمام یال‌ها وجود داشته باشند، این مسیر یک Hamiltonian Cycle است.

بنابراین:

Code

Hamiltonian Path
=
بازدید همه رأس‌ها دقیقاً یک بار

Hamiltonian Cycle
=
Hamiltonian Path
+
بازگشت به رأس شروع

این مسئله دقیقاً چه چیزی را بررسی می‌کند؟

در این مسئله تمرکز روی Vertexها است.

یعنی هدف ما این است که تمام رأس‌ها را بدون تکرار پوشش دهیم.

این نکته بسیار مهم است، چون در Eulerian Path تمرکز روی Edgeها است.

تفاوت Hamiltonian Path با Eulerian Path

این یکی از مهم‌ترین تفاوت‌هایی است که باید بدانیم.

Hamiltonian Path

هدف:

Code

هر Vertex دقیقاً یک بار

Eulerian Path

هدف:

Code

هر Edge دقیقاً یک بار

مثلاً ممکن است در Hamiltonian Path بعضی یال‌ها اصلاً استفاده نشوند.

اما در Eulerian Path تمام یال‌ها باید استفاده شوند.

مثال برای درک تفاوت

فرض کنید:

Code

A ----- B
| \     |
|  \    |
D ----- C

در Hamiltonian Path شاید مسیر زیر کافی باشد:

Code

A → B → C → D

اما یال‌های دیگر مهم نیستند.

در Eulerian Path باید تمام Edgeها دقیقاً یک بار پیمایش شوند.

پس:

Code

Hamiltonian = Vertex-oriented
Eulerian = Edge-oriented

تفاوت Hamiltonian Cycle با TSP

Hamiltonian Cycle می‌پرسد:

آیا دوری وجود دارد که تمام رأس‌ها را دقیقاً یک بار ببیند؟

اما Travelling Salesman Problem می‌پرسد:

از بین تمام Hamiltonian Cycleهای ممکن، کدام‌یک کمترین هزینه را دارد؟

پس TSP در واقع یک نسخه‌ی وزن‌دار و Optimization از مفهوم Hamiltonian Cycle است.

در Hamiltonian Cycle ممکن است فقط وجود یک جواب مهم باشد.

در TSP بهترین جواب مهم است.

تفاوت با Shortest Path

Shortest Path مثل Dijkstra می‌پرسد:

Code

کوتاه‌ترین مسیر از A به B چیست؟

اما Hamiltonian Path می‌پرسد:

Code

آیا می‌توان مسیری ساخت که تمام رأس‌های گراف را دقیقاً یک بار ببیند؟

بنابراین این دو مسئله هدف کاملاً متفاوتی دارند.

چرا پیدا کردن Hamiltonian Path سخت است؟

در نگاه اول ممکن است فکر کنیم کافی است از DFS استفاده کنیم.

اما DFS معمولی فقط می‌خواهد گراف را Traverse کند و می‌تواند از مسیرهای مختلف عبور کند.

در Hamiltonian Path ترتیب رأس‌ها اهمیت زیادی دارد.

اگر انتخاب اشتباهی انجام دهیم ممکن است چند مرحله بعد به بن‌بست برسیم.

برای همین معمولاً از Backtracking استفاده می‌کنیم.

ایده‌ی Backtracking

Backtracking یعنی:

یک انتخاب انجام بده.
جلو برو.
اگر جواب ممکن بود ادامه بده.
اگر به بن‌بست رسیدی، انتخاب قبلی را Undo کن.
یک گزینه دیگر را امتحان کن.

مثلاً:

Code

A → B → C

اگر از C هیچ رأس استفاده‌نشده‌ای قابل دسترس نباشد ولی هنوز رأس‌های بازدیدنشده وجود داشته باشند:

Code

Backtrack

می‌کنیم و به:

Code

A → B

برمی‌گردیم.

بعد شاید مسیر دیگری مثل:

Code

A → B → D

را امتحان کنیم.

مراحل پیدا کردن Hamiltonian Path

فرض کنید گراف به صورت adjacency list داده شده است.

مرحله 1: انتخاب رأس شروع

می‌توانیم هر رأس را به عنوان شروع امتحان کنیم.

Code

start = A

مرحله 2: ثبت رأس در مسیر

Code

path = [A]
used = {A}

مرحله 3: بررسی همسایه‌ها

از میان همسایه‌های رأس فعلی، یک رأس انتخاب می‌کنیم که هنوز استفاده نشده باشد.

مرحله 4: ادامه‌ی بازگشتی

رأس جدید را به path اضافه می‌کنیم و recursion را ادامه می‌دهیم.

مرحله 5: اگر بن‌بست شد

رأس را از used و path حذف می‌کنیم.

این همان Backtracking است.

مرحله 6: شرط موفقیت

اگر:

Code

path.length === numberOfVertices

یعنی همه رأس‌ها دقیقاً یک بار دیده شده‌اند.

پس Hamiltonian Path پیدا شده است.

پیاده‌سازی Hamiltonian Path با JavaScript

JavaScript

function findHamiltonianPath(graph) {
  const nodes = Object.keys(graph);

  function search(current, path, used) {
    if (path.length === nodes.length) {
      return [...path];
    }

    for (const next of graph[current] ?? []) {
      if (used.has(next)) continue;

      used.add(next);
      path.push(next);

      const result = search(next, path, used);

      if (result) {
        return result;
      }

      path.pop();
      used.delete(next);
    }

    return null;
  }

  for (const start of nodes) {
    const used = new Set([start]);
    const path = [start];

    const result = search(start, path, used);

    if (result) {
      return result;
    }
  }

  return null;
}

مثال:

JavaScript

const graph = {
  A: ["B", "D"],
  B: ["A", "C", "D"],
  C: ["B", "D"],
  D: ["A", "B", "C"]
};

console.log(findHamiltonianPath(graph));

ممکن است خروجی چیزی شبیه این باشد:

Code

[A, B, C, D]

پیدا کردن Hamiltonian Cycle

برای Cycle فقط یک شرط اضافی داریم.

وقتی همه رأس‌ها استفاده شدند باید بررسی کنیم آیا آخرین رأس به رأس شروع متصل است یا نه.

JavaScript

function findHamiltonianCycle(graph) {
  const nodes = Object.keys(graph);

  function search(start, current, path, used) {
    if (path.length === nodes.length) {
      const canReturn =
        (graph[current] ?? []).includes(start);

      if (canReturn) {
        return [...path, start];
      }

      return null;
    }

    for (const next of graph[current] ?? []) {
      if (used.has(next)) continue;

      used.add(next);
      path.push(next);

      const result = search(
        start,
        next,
        path,
        used
      );

      if (result) {
        return result;
      }

      path.pop();
      used.delete(next);
    }

    return null;
  }

  for (const start of nodes) {
    const result = search(
      start,
      start,
      [start],
      new Set([start])
    );

    if (result) {
      return result;
    }
  }

  return null;
}

اگر خروجی:

Code

[A, B, C, D, A]

باشد، یعنی یک Hamiltonian Cycle پیدا شده است.

اجرای مرحله‌به‌مرحله روی یک مثال

گراف زیر را در نظر بگیرید:

Code

A: B, C
B: A, C, D
C: A, B, D
D: B, C

از A شروع می‌کنیم:

Code

Path = [A]

اول B را امتحان می‌کنیم:

Code

A → B

بعد C:

Code

A → B → C

بعد D:

Code

A → B → C → D

همه رأس‌ها دیده شدند.

پس:

Code

A → B → C → D

یک Hamiltonian Path است.

اما برای Cycle باید بررسی کنیم:

Code

D → A ?

اگر چنین یالی وجود نداشته باشد، این مسیر Hamiltonian Cycle نیست.

ممکن است الگوریتم Backtrack کند و ترتیب دیگری را امتحان کند.

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

در بدترین حالت الگوریتم باید تعداد بسیار زیادی ترتیب مختلف از رأس‌ها را امتحان کند.

برای V رأس، حالت ساده‌ی Backtracking تقریباً می‌تواند به:

Code

O(V!)

برسد.

یعنی:

Code

5! = 120
10! = 3,628,800
15! ≈ 1.3 × 10^12

بنابراین این روش برای گراف‌های بزرگ مناسب نیست.

پیچیدگی فضایی

برای recursion، path و visited معمولاً تقریباً:

Code

O(V)

فضای مستقیم نیاز داریم.

البته اگر تعداد زیادی state ذخیره کنیم یا از DP استفاده کنیم، حافظه می‌تواند بیشتر شود.

آیا Hamiltonian Path مسئله NP-Complete است؟

بله.

نسخه تصمیمی مسئله Hamiltonian Path و Hamiltonian Cycle از مسائل معروف NP-Complete هستند.

یعنی:

اگر یک جواب داشته باشیم می‌توانیم سریع صحت آن را بررسی کنیم.
اما الگوریتم Polynomial-Time عمومی شناخته‌شده‌ای برای پیدا کردن جواب در هر گراف نداریم.

این دلیل اصلی گران بودن حل exact در گراف‌های بزرگ است.

آیا می‌توان با Dynamic Programming بهتر کرد؟

بله، برای بعضی ورودی‌ها می‌توان از Subset DP یا Bitmask DP استفاده کرد.

مثلاً State:

Code

dp[mask][v]

می‌تواند مشخص کند:

آیا مسیری وجود دارد که دقیقاً رأس‌های داخل mask را استفاده کند و در v تمام شود؟

این روش معمولاً پیچیدگی‌ای در حدود:

Code

O(V² × 2^V)

دارد.

که نسبت به O(V!) بهتر است، اما همچنان exponential است.

نمونه‌ی Bitmask DP

ایده:

Code

dp[mask][v] = true

اگر Hamiltonian Path جزئی‌ای وجود داشته باشد که:

رأس‌های mask را بازدید کرده باشد.
در رأس v تمام شود.

Transition:

اگر:

Code

dp[mask][u] = true

و یال:

Code

u → v

وجود داشته باشد و v هنوز در mask نباشد:

Code

dp[mask | (1 << v)][v] = true

وقتی:

Code

mask = (1 << V) - 1

باشد، همه رأس‌ها استفاده شده‌اند.

شرایط لازم و کافی ساده وجود دارد؟

برای Eulerian Path قوانین بسیار تمیزی بر اساس Degree داریم.

مثلاً در گراف بدون جهت:

تعداد رأس‌های Odd Degree اهمیت دارد.

اما برای Hamiltonian Path چنین قانون ساده و عمومی‌ای نداریم.

با این حال قضیه‌هایی مثل Dirac's Theorem و Ore's Theorem می‌توانند در بعضی گراف‌ها وجود Hamiltonian Cycle را تضمین کنند.

قضیه Dirac

برای گراف ساده با n ≥ 3 رأس، اگر Degree هر رأس حداقل:

Code

n / 2

باشد، گراف Hamiltonian Cycle دارد.

این شرط کافی است، ولی لازم نیست.

یعنی ممکن است گراف Hamiltonian باشد ولی شرط Dirac را نداشته باشد.

کاربردهای واقعی

Hamiltonian Path در دنیای واقعی معمولاً به صورت مستقیم یا به عنوان ساختار پایه‌ی مسائل بزرگ‌تر دیده می‌شود.

1. برنامه‌ریزی بازدید بدون تکرار

فرض کنید باید مجموعه‌ای از نقاط را طوری بازدید کنیم که هیچ نقطه‌ای دوبار دیده نشود.

اگر فقط امکان وجود چنین ترتیب مهم باشد، مدل Hamiltonian مناسب است.

2. Route Sequencing

در بعضی سیستم‌ها ترتیب عبور از مجموعه‌ای از ایستگاه‌ها اهمیت دارد.

اگر شرط اصلی «هر ایستگاه دقیقاً یک بار» باشد، Hamiltonian Path می‌تواند مدل اولیه‌ی مسئله باشد.

3. Graph Puzzle

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

Code

از همه خانه‌ها یا نقاط دقیقاً یک بار عبور کن

4. مبنای ساختاری TSP

TSP را می‌توان Hamiltonian Cycle وزن‌دار دانست که هدف آن کمینه کردن هزینه است.

5. طراحی توالی عملیات

گاهی مجموعه‌ای از Taskها داریم که بین آن‌ها Transitionهای مجاز تعریف شده‌اند.

اگر بخواهیم هر Task دقیقاً یک بار در یک توالی معتبر اجرا شود، مدل مسئله می‌تواند به Hamiltonian Path نزدیک شود.

6. مسائل Bioinformatics

بعضی مسائل توالی‌سازی یا Assembly را می‌توان با ساختارهای گرافی مرتبط با Hamiltonian Path مدل کرد، هرچند در بسیاری از کاربردهای مدرن مدل Eulerian مناسب‌تر است.

Directed Graph و Undirected Graph

Hamiltonian Path می‌تواند در هر دو نوع گراف مطرح شود.

Undirected

اگر:

Code

A -- B

باشد، عبور در هر دو جهت ممکن است.

Directed

اگر:

Code

A → B

باشد، فقط جهت مشخص‌شده معتبر است.

در گراف جهت‌دار باید دقیقاً Direction یال‌ها را رعایت کنیم.

Edge Caseهای مهم

گراف تک‌رأسی

یک رأس به تنهایی می‌تواند Hamiltonian Path باشد.

برای Hamiltonian Cycle تعریف دقیق ممکن است به Convention بستگی داشته باشد.

گراف Disconnected

در گراف بدون جهت اگر گراف disconnected باشد، Hamiltonian Path نمی‌تواند تمام رأس‌ها را پوشش دهد.

رأس ایزوله

اگر گراف بیش از یک رأس داشته باشد و یک رأس Degree صفر داشته باشد، Hamiltonian Path وجود ندارد.

Degree پایین

وجود رأس‌های Degree پایین می‌تواند محدودیت زیادی ایجاد کند.

مثلاً در Hamiltonian Cycle هر رأس باید حداقل بتواند به دو بخش از Cycle متصل شود.

بهینه‌سازی Backtracking

در پروژه‌های واقعی می‌توان Search را بهتر کرد.

1. انتخاب رأس محدودتر

اول گزینه‌هایی را امتحان کنیم که Degree کمتر دارند.

این کار می‌تواند زودتر بن‌بست‌ها را آشکار کند.

2. Pruning

اگر در یک State بفهمیم تکمیل مسیر غیرممکن است، ادامه ندهیم.

3. Memoization

بعضی Stateها را می‌توان ذخیره کرد تا دوباره بررسی نشوند.

4. Bitmask

برای گراف‌های کوچک تا متوسط، استفاده از Bitmask می‌تواند State Management را سریع‌تر کند.

مقایسه‌ی مهم

مسئله	چه چیزی باید دقیقاً یک بار دیده شود؟	بازگشت به شروع	Optimization
Hamiltonian Path	Vertex	نه	نه
Hamiltonian Cycle	Vertex	بله	نه
Eulerian Path	Edge	نه	نه
Eulerian Cycle	Edge	بله	نه
TSP	Vertex	بله	بله، کمترین هزینه

این جدول یکی از مهم‌ترین بخش‌های درک این مسائل است.

چه زمانی از Hamiltonian Path استفاده کنیم؟

وقتی:

همه رأس‌ها باید بازدید شوند.
هر رأس باید دقیقاً یک بار استفاده شود.
ترتیب عبور اهمیت دارد.
فقط وجود یا پیدا کردن یک ترتیب معتبر مهم است.

چه زمانی مناسب نیست؟

اگر هدف شما کمترین هزینه است، احتمالاً وارد TSP یا مسائل Optimization شده‌اید.

اگر هدف استفاده از تمام یال‌هاست، Eulerian Path مناسب‌تر است.

اگر فقط می‌خواهید همه رأس‌ها را Traverse کنید و تکرار مهم نیست، DFS یا BFS کافی است.

اگر فقط کوتاه‌ترین مسیر بین دو نقطه مهم است، Dijkstra یا A* مناسب‌تر است.

جمع‌بندی

Hamiltonian Path مسیری است که تمام رأس‌های گراف را دقیقاً یک بار بازدید می‌کند.

Hamiltonian Cycle همین شرط را دارد، با این تفاوت که در پایان به رأس شروع برمی‌گردد.

مهم‌ترین نکته این است که Hamiltonian روی Vertex تمرکز دارد، در حالی که Eulerian روی Edge تمرکز می‌کند.

حل عمومی Hamiltonian Path و Cycle ساده نیست و نسخه تصمیمی آن‌ها NP-Complete است. Backtracking برای گراف‌های کوچک مناسب است و Bitmask DP می‌تواند پیچیدگی را از حالت Factorial به حدود O(V²2^V) کاهش دهد، اما همچنان برای گراف‌های بسیار بزرگ گران است.

از دید مهندسی، مهم‌تر از حفظ کردن کد این است که بتوانیم تشخیص دهیم مسئله‌ی واقعی ما Hamiltonian است، Eulerian است، Shortest Path است یا نسخه‌ای Optimization مانند TSP.

مسئله‌ی Hamiltonian Path و Hamiltonian Cycle از مسائل کلاسیک نظریه گراف هستند و روی یک سؤال ساده اما مهم تمرکز دارند:

آیا می‌توان مسیری پیدا کرد که هر رأس گراف را دقیقاً یک بار بازدید کند؟

اگر چنین مسیری وجود داشته باشد به آن Hamiltonian Path می‌گوییم.

اگر علاوه بر این، آخرین رأس دوباره به رأس شروع متصل شود و مسیر یک دور بسته بسازد، یک Hamiltonian Cycle داریم.

تعریف ساده Hamiltonian Path

فرض کنید گراف زیر را داریم:

Code

A -- B -- C
|         |
D ------- E

یک Hamiltonian Path باید:

از یکی از رأس‌ها شروع کند.
هر رأس را دقیقاً یک بار ببیند.
بین هر دو رأس متوالی یک یال معتبر وجود داشته باشد.
لازم نیست به نقطه شروع برگردد.

مثلاً:

Code

D → A → B → C → E

اگر همه یال‌های این مسیر در گراف وجود داشته باشند، این یک Hamiltonian Path معتبر است.

Hamiltonian Cycle چیست؟

Hamiltonian Cycle همان Hamiltonian Path است، با یک شرط اضافه:

آخرین رأس باید به رأس شروع متصل باشد.

مثلاً:

Code

A → B → C → E → D → A

اگر تمام یال‌ها وجود داشته باشند، این مسیر یک Hamiltonian Cycle است.

بنابراین:

Code

Hamiltonian Path
=
بازدید همه رأس‌ها دقیقاً یک بار

Hamiltonian Cycle
=
Hamiltonian Path
+
بازگشت به رأس شروع

این مسئله دقیقاً چه چیزی را بررسی می‌کند؟

در این مسئله تمرکز روی Vertexها است.

یعنی هدف ما این است که تمام رأس‌ها را بدون تکرار پوشش دهیم.

این نکته بسیار مهم است، چون در Eulerian Path تمرکز روی Edgeها است.

تفاوت Hamiltonian Path با Eulerian Path

این یکی از مهم‌ترین تفاوت‌هایی است که باید بدانیم.

Hamiltonian Path

هدف:

Code

هر Vertex دقیقاً یک بار

Eulerian Path

هدف:

Code

هر Edge دقیقاً یک بار

مثلاً ممکن است در Hamiltonian Path بعضی یال‌ها اصلاً استفاده نشوند.

اما در Eulerian Path تمام یال‌ها باید استفاده شوند.

مثال برای درک تفاوت

فرض کنید:

Code

A ----- B
| \     |
|  \    |
D ----- C

در Hamiltonian Path شاید مسیر زیر کافی باشد:

Code

A → B → C → D

اما یال‌های دیگر مهم نیستند.

در Eulerian Path باید تمام Edgeها دقیقاً یک بار پیمایش شوند.

پس:

Code

Hamiltonian = Vertex-oriented
Eulerian = Edge-oriented

تفاوت Hamiltonian Cycle با TSP

Hamiltonian Cycle می‌پرسد:

آیا دوری وجود دارد که تمام رأس‌ها را دقیقاً یک بار ببیند؟

اما Travelling Salesman Problem می‌پرسد:

از بین تمام Hamiltonian Cycleهای ممکن، کدام‌یک کمترین هزینه را دارد؟

پس TSP در واقع یک نسخه‌ی وزن‌دار و Optimization از مفهوم Hamiltonian Cycle است.

در Hamiltonian Cycle ممکن است فقط وجود یک جواب مهم باشد.

در TSP بهترین جواب مهم است.

تفاوت با Shortest Path

Shortest Path مثل Dijkstra می‌پرسد:

Code

کوتاه‌ترین مسیر از A به B چیست؟

اما Hamiltonian Path می‌پرسد:

Code

آیا می‌توان مسیری ساخت که تمام رأس‌های گراف را دقیقاً یک بار ببیند؟

بنابراین این دو مسئله هدف کاملاً متفاوتی دارند.

چرا پیدا کردن Hamiltonian Path سخت است؟

در نگاه اول ممکن است فکر کنیم کافی است از DFS استفاده کنیم.

اما DFS معمولی فقط می‌خواهد گراف را Traverse کند و می‌تواند از مسیرهای مختلف عبور کند.

در Hamiltonian Path ترتیب رأس‌ها اهمیت زیادی دارد.

اگر انتخاب اشتباهی انجام دهیم ممکن است چند مرحله بعد به بن‌بست برسیم.

برای همین معمولاً از Backtracking استفاده می‌کنیم.

ایده‌ی Backtracking

Backtracking یعنی:

یک انتخاب انجام بده.
جلو برو.
اگر جواب ممکن بود ادامه بده.
اگر به بن‌بست رسیدی، انتخاب قبلی را Undo کن.
یک گزینه دیگر را امتحان کن.

مثلاً:

Code

A → B → C

اگر از C هیچ رأس استفاده‌نشده‌ای قابل دسترس نباشد ولی هنوز رأس‌های بازدیدنشده وجود داشته باشند:

Code

Backtrack

می‌کنیم و به:

Code

A → B

برمی‌گردیم.

بعد شاید مسیر دیگری مثل:

Code

A → B → D

را امتحان کنیم.

مراحل پیدا کردن Hamiltonian Path

فرض کنید گراف به صورت adjacency list داده شده است.

مرحله 1: انتخاب رأس شروع

می‌توانیم هر رأس را به عنوان شروع امتحان کنیم.

Code

start = A

مرحله 2: ثبت رأس در مسیر

Code

path = [A]
used = {A}

مرحله 3: بررسی همسایه‌ها

از میان همسایه‌های رأس فعلی، یک رأس انتخاب می‌کنیم که هنوز استفاده نشده باشد.

مرحله 4: ادامه‌ی بازگشتی

رأس جدید را به path اضافه می‌کنیم و recursion را ادامه می‌دهیم.

مرحله 5: اگر بن‌بست شد

رأس را از used و path حذف می‌کنیم.

این همان Backtracking است.

مرحله 6: شرط موفقیت

اگر:

Code

path.length === numberOfVertices

یعنی همه رأس‌ها دقیقاً یک بار دیده شده‌اند.

پس Hamiltonian Path پیدا شده است.

پیاده‌سازی Hamiltonian Path با JavaScript

JavaScript

function findHamiltonianPath(graph) {
  const nodes = Object.keys(graph);

  function search(current, path, used) {
    if (path.length === nodes.length) {
      return [...path];
    }

    for (const next of graph[current] ?? []) {
      if (used.has(next)) continue;

      used.add(next);
      path.push(next);

      const result = search(next, path, used);

      if (result) {
        return result;
      }

      path.pop();
      used.delete(next);
    }

    return null;
  }

  for (const start of nodes) {
    const used = new Set([start]);
    const path = [start];

    const result = search(start, path, used);

    if (result) {
      return result;
    }
  }

  return null;
}

مثال:

JavaScript

const graph = {
  A: ["B", "D"],
  B: ["A", "C", "D"],
  C: ["B", "D"],
  D: ["A", "B", "C"]
};

console.log(findHamiltonianPath(graph));

ممکن است خروجی چیزی شبیه این باشد:

Code

[A, B, C, D]

پیدا کردن Hamiltonian Cycle

برای Cycle فقط یک شرط اضافی داریم.

وقتی همه رأس‌ها استفاده شدند باید بررسی کنیم آیا آخرین رأس به رأس شروع متصل است یا نه.

JavaScript

function findHamiltonianCycle(graph) {
  const nodes = Object.keys(graph);

  function search(start, current, path, used) {
    if (path.length === nodes.length) {
      const canReturn =
        (graph[current] ?? []).includes(start);

      if (canReturn) {
        return [...path, start];
      }

      return null;
    }

    for (const next of graph[current] ?? []) {
      if (used.has(next)) continue;

      used.add(next);
      path.push(next);

      const result = search(
        start,
        next,
        path,
        used
      );

      if (result) {
        return result;
      }

      path.pop();
      used.delete(next);
    }

    return null;
  }

  for (const start of nodes) {
    const result = search(
      start,
      start,
      [start],
      new Set([start])
    );

    if (result) {
      return result;
    }
  }

  return null;
}

اگر خروجی:

Code

[A, B, C, D, A]

باشد، یعنی یک Hamiltonian Cycle پیدا شده است.

اجرای مرحله‌به‌مرحله روی یک مثال

گراف زیر را در نظر بگیرید:

Code

A: B, C
B: A, C, D
C: A, B, D
D: B, C

از A شروع می‌کنیم:

Code

Path = [A]

اول B را امتحان می‌کنیم:

Code

A → B

بعد C:

Code

A → B → C

بعد D:

Code

A → B → C → D

همه رأس‌ها دیده شدند.

پس:

Code

A → B → C → D

یک Hamiltonian Path است.

اما برای Cycle باید بررسی کنیم:

Code

D → A ?

اگر چنین یالی وجود نداشته باشد، این مسیر Hamiltonian Cycle نیست.

ممکن است الگوریتم Backtrack کند و ترتیب دیگری را امتحان کند.

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

در بدترین حالت الگوریتم باید تعداد بسیار زیادی ترتیب مختلف از رأس‌ها را امتحان کند.

برای V رأس، حالت ساده‌ی Backtracking تقریباً می‌تواند به:

Code

O(V!)

برسد.

یعنی:

Code

5! = 120
10! = 3,628,800
15! ≈ 1.3 × 10^12

بنابراین این روش برای گراف‌های بزرگ مناسب نیست.

پیچیدگی فضایی

برای recursion، path و visited معمولاً تقریباً:

Code

O(V)

فضای مستقیم نیاز داریم.

البته اگر تعداد زیادی state ذخیره کنیم یا از DP استفاده کنیم، حافظه می‌تواند بیشتر شود.

آیا Hamiltonian Path مسئله NP-Complete است؟

بله.

نسخه تصمیمی مسئله Hamiltonian Path و Hamiltonian Cycle از مسائل معروف NP-Complete هستند.

یعنی:

اگر یک جواب داشته باشیم می‌توانیم سریع صحت آن را بررسی کنیم.
اما الگوریتم Polynomial-Time عمومی شناخته‌شده‌ای برای پیدا کردن جواب در هر گراف نداریم.

این دلیل اصلی گران بودن حل exact در گراف‌های بزرگ است.

آیا می‌توان با Dynamic Programming بهتر کرد؟

بله، برای بعضی ورودی‌ها می‌توان از Subset DP یا Bitmask DP استفاده کرد.

مثلاً State:

Code

dp[mask][v]

می‌تواند مشخص کند:

آیا مسیری وجود دارد که دقیقاً رأس‌های داخل mask را استفاده کند و در v تمام شود؟

این روش معمولاً پیچیدگی‌ای در حدود:

Code

O(V² × 2^V)

دارد.

که نسبت به O(V!) بهتر است، اما همچنان exponential است.

نمونه‌ی Bitmask DP

ایده:

Code

dp[mask][v] = true

اگر Hamiltonian Path جزئی‌ای وجود داشته باشد که:

رأس‌های mask را بازدید کرده باشد.
در رأس v تمام شود.

Transition:

اگر:

Code

dp[mask][u] = true

و یال:

Code

u → v

وجود داشته باشد و v هنوز در mask نباشد:

Code

dp[mask | (1 << v)][v] = true

وقتی:

Code

mask = (1 << V) - 1

باشد، همه رأس‌ها استفاده شده‌اند.

شرایط لازم و کافی ساده وجود دارد؟

برای Eulerian Path قوانین بسیار تمیزی بر اساس Degree داریم.

مثلاً در گراف بدون جهت:

تعداد رأس‌های Odd Degree اهمیت دارد.

اما برای Hamiltonian Path چنین قانون ساده و عمومی‌ای نداریم.

با این حال قضیه‌هایی مثل Dirac's Theorem و Ore's Theorem می‌توانند در بعضی گراف‌ها وجود Hamiltonian Cycle را تضمین کنند.

قضیه Dirac

برای گراف ساده با n ≥ 3 رأس، اگر Degree هر رأس حداقل:

Code

n / 2

باشد، گراف Hamiltonian Cycle دارد.

این شرط کافی است، ولی لازم نیست.

یعنی ممکن است گراف Hamiltonian باشد ولی شرط Dirac را نداشته باشد.

کاربردهای واقعی

Hamiltonian Path در دنیای واقعی معمولاً به صورت مستقیم یا به عنوان ساختار پایه‌ی مسائل بزرگ‌تر دیده می‌شود.

1. برنامه‌ریزی بازدید بدون تکرار

فرض کنید باید مجموعه‌ای از نقاط را طوری بازدید کنیم که هیچ نقطه‌ای دوبار دیده نشود.

اگر فقط امکان وجود چنین ترتیب مهم باشد، مدل Hamiltonian مناسب است.

2. Route Sequencing

در بعضی سیستم‌ها ترتیب عبور از مجموعه‌ای از ایستگاه‌ها اهمیت دارد.

اگر شرط اصلی «هر ایستگاه دقیقاً یک بار» باشد، Hamiltonian Path می‌تواند مدل اولیه‌ی مسئله باشد.

3. Graph Puzzle

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

Code

از همه خانه‌ها یا نقاط دقیقاً یک بار عبور کن

4. مبنای ساختاری TSP

TSP را می‌توان Hamiltonian Cycle وزن‌دار دانست که هدف آن کمینه کردن هزینه است.

5. طراحی توالی عملیات

گاهی مجموعه‌ای از Taskها داریم که بین آن‌ها Transitionهای مجاز تعریف شده‌اند.

اگر بخواهیم هر Task دقیقاً یک بار در یک توالی معتبر اجرا شود، مدل مسئله می‌تواند به Hamiltonian Path نزدیک شود.

6. مسائل Bioinformatics

Directed Graph و Undirected Graph

Hamiltonian Path می‌تواند در هر دو نوع گراف مطرح شود.

Undirected

اگر:

Code

A -- B

باشد، عبور در هر دو جهت ممکن است.

Directed

اگر:

Code

A → B

باشد، فقط جهت مشخص‌شده معتبر است.

در گراف جهت‌دار باید دقیقاً Direction یال‌ها را رعایت کنیم.

Edge Caseهای مهم

گراف تک‌رأسی

یک رأس به تنهایی می‌تواند Hamiltonian Path باشد.

برای Hamiltonian Cycle تعریف دقیق ممکن است به Convention بستگی داشته باشد.

گراف Disconnected

در گراف بدون جهت اگر گراف disconnected باشد، Hamiltonian Path نمی‌تواند تمام رأس‌ها را پوشش دهد.

رأس ایزوله

اگر گراف بیش از یک رأس داشته باشد و یک رأس Degree صفر داشته باشد، Hamiltonian Path وجود ندارد.

Degree پایین

وجود رأس‌های Degree پایین می‌تواند محدودیت زیادی ایجاد کند.

مثلاً در Hamiltonian Cycle هر رأس باید حداقل بتواند به دو بخش از Cycle متصل شود.

بهینه‌سازی Backtracking

در پروژه‌های واقعی می‌توان Search را بهتر کرد.

1. انتخاب رأس محدودتر

اول گزینه‌هایی را امتحان کنیم که Degree کمتر دارند.

این کار می‌تواند زودتر بن‌بست‌ها را آشکار کند.

2. Pruning

اگر در یک State بفهمیم تکمیل مسیر غیرممکن است، ادامه ندهیم.

3. Memoization

بعضی Stateها را می‌توان ذخیره کرد تا دوباره بررسی نشوند.

4. Bitmask

برای گراف‌های کوچک تا متوسط، استفاده از Bitmask می‌تواند State Management را سریع‌تر کند.

مقایسه‌ی مهم

مسئله	چه چیزی باید دقیقاً یک بار دیده شود؟	بازگشت به شروع	Optimization
Hamiltonian Path	Vertex	نه	نه
Hamiltonian Cycle	Vertex	بله	نه
Eulerian Path	Edge	نه	نه
Eulerian Cycle	Edge	بله	نه
TSP	Vertex	بله	بله، کمترین هزینه

این جدول یکی از مهم‌ترین بخش‌های درک این مسائل است.

چه زمانی از Hamiltonian Path استفاده کنیم؟

وقتی:

همه رأس‌ها باید بازدید شوند.
هر رأس باید دقیقاً یک بار استفاده شود.
ترتیب عبور اهمیت دارد.
فقط وجود یا پیدا کردن یک ترتیب معتبر مهم است.

چه زمانی مناسب نیست؟

اگر هدف شما کمترین هزینه است، احتمالاً وارد TSP یا مسائل Optimization شده‌اید.

اگر هدف استفاده از تمام یال‌هاست، Eulerian Path مناسب‌تر است.

اگر فقط می‌خواهید همه رأس‌ها را Traverse کنید و تکرار مهم نیست، DFS یا BFS کافی است.

اگر فقط کوتاه‌ترین مسیر بین دو نقطه مهم است، Dijkstra یا A* مناسب‌تر است.

جمع‌بندی

Hamiltonian Path مسیری است که تمام رأس‌های گراف را دقیقاً یک بار بازدید می‌کند.

Hamiltonian Cycle همین شرط را دارد، با این تفاوت که در پایان به رأس شروع برمی‌گردد.

مهم‌ترین نکته این است که Hamiltonian روی Vertex تمرکز دارد، در حالی که Eulerian روی Edge تمرکز می‌کند.

Hamiltonian Path و Cycle چیست؟ عبور از هر رأس دقیقاً یک‌بار

تعریف ساده Hamiltonian Path

Hamiltonian Cycle چیست؟

این مسئله دقیقاً چه چیزی را بررسی می‌کند؟

تفاوت Hamiltonian Path با Eulerian Path

Hamiltonian Path

Eulerian Path

مثال برای درک تفاوت

تفاوت Hamiltonian Cycle با TSP

تفاوت با Shortest Path

چرا پیدا کردن Hamiltonian Path سخت است؟

ایده‌ی Backtracking

مراحل پیدا کردن Hamiltonian Path

مرحله 1: انتخاب رأس شروع

مرحله 2: ثبت رأس در مسیر

مرحله 3: بررسی همسایه‌ها

مرحله 4: ادامه‌ی بازگشتی

مرحله 5: اگر بن‌بست شد

مرحله 6: شرط موفقیت

پیاده‌سازی Hamiltonian Path با JavaScript

پیدا کردن Hamiltonian Cycle

JavaScript

اجرای مرحله‌به‌مرحله روی یک مثال

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

پیچیدگی فضایی

آیا Hamiltonian Path مسئله NP-Complete است؟

آیا می‌توان با Dynamic Programming بهتر کرد؟

نمونه‌ی Bitmask DP

شرایط لازم و کافی ساده وجود دارد؟

قضیه Dirac

کاربردهای واقعی

1. برنامه‌ریزی بازدید بدون تکرار

2. Route Sequencing

3. Graph Puzzle

4. مبنای ساختاری TSP

5. طراحی توالی عملیات

6. مسائل Bioinformatics

Directed Graph و Undirected Graph

Undirected

Directed

Edge Caseهای مهم

گراف تک‌رأسی

گراف Disconnected

رأس ایزوله

Degree پایین

بهینه‌سازی Backtracking

1. انتخاب رأس محدودتر

2. Pruning

3. Memoization

4. Bitmask

مقایسه‌ی مهم

چه زمانی از Hamiltonian Path استفاده کنیم؟

چه زمانی مناسب نیست؟

جمع‌بندی

Eulerian Path و Circuit چیست؟ عبور از هر یال دقیقاً یک‌بار

مسئله فروشنده دوره‌گرد TSP چیست؟ از Brute Force تا Dynamic Programming

Hamiltonian Path و Cycle چیست؟ عبور از هر رأس دقیقاً یک‌بار

تعریف ساده Hamiltonian Path

Hamiltonian Cycle چیست؟

این مسئله دقیقاً چه چیزی را بررسی می‌کند؟

تفاوت Hamiltonian Path با Eulerian Path

Hamiltonian Path

Eulerian Path

مثال برای درک تفاوت

تفاوت Hamiltonian Cycle با TSP

تفاوت با Shortest Path

چرا پیدا کردن Hamiltonian Path سخت است؟

ایده‌ی Backtracking

مراحل پیدا کردن Hamiltonian Path

مرحله 1: انتخاب رأس شروع

مرحله 2: ثبت رأس در مسیر

مرحله 3: بررسی همسایه‌ها

مرحله 4: ادامه‌ی بازگشتی

مرحله 5: اگر بن‌بست شد

مرحله 6: شرط موفقیت

پیاده‌سازی Hamiltonian Path با JavaScript

پیدا کردن Hamiltonian Cycle

JavaScript

اجرای مرحله‌به‌مرحله روی یک مثال

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