AlgoVerse

قیدهای تفاضلی

دستگاهی از نامعادله‌های x_j − x_i ≤ b را به گرافی تبدیل می‌کند و با بلمن–فورد حل می‌کند: فاصله‌های کوتاه‌ترین مسیر یک جواب‌اند، و دور منفی یعنی دستگاه جواب ندارد.

دستگاهی از نامعادله‌ها به شکل x_j − x_i ≤ b داریم (مثلاً در زمان‌بندی: «کار j حداکثر b واحد بعد از کار i»). می‌خواهیم مقادیری برای x پیدا کنیم که همه برقرار باشند، یا بفهمیم ممکن نیست.

ادامه‌ی توضیح ↓
ورودی:
C 8×3خروجی PDF

هشت قید روی پنج متغیر (مثال CLRS)؛ یک جواب: x = (−۵، −۳، ۰، −۱، −۴).

  1. def difference_constraints(C):
  2. # Each row [j, i, b] means x_j - x_i <= b: an edge i -> j of weight b. Vertex 0 is a source with 0-edges to all.
  3. n = 0
  4. for j, i, b in C:
  5. n = max(n, i, j)
  6. edges = []
  7. for v in range(1, n + 1):
  8. edges.append([0, v, 0])
  9. for j, i, b in C:
  10. edges.append([i, j, b])
  11. x = [0] + [float("inf")] * n
  12. for rnd in range(1, n + 1):
  13. changed = False
  14. for u, v, w in edges:
  15. if x[u] + w < x[v]:
  16. x[v] = x[u] + w
  17. changed = True
  18. if not changed:
  19. break
  20. for u, v, w in edges:
  21. if x[u] + w < x[v]:
  22. return None
  23. solution = x[1:]
  24. return solution

ناوردا: بعد از دور k، x[v] حداکثر طول کوتاه‌ترین مسیر با حداکثر k یال از 0 تا v است.

شروع اجرا

x—
solution—

متغیرهای محلی

نارنجی = در همین گام عوض شد

C list

[1, 2, 0][1, 5, -1][2, 5, 1][3, 1, 5][4, 1, 4][4, 3, -1][5, 3, -3][5, 4, -3]

Call stack

  1. difference_constraints()خط 1
گام ۱ از ۱۹۱
خط سیاه = settled · خط نارنجی = گام کلیدیgraph: 0/1 · relax: 0/11 · settled: 0/1 · solution: 0/1
    توضیح

    مسئله

    دستگاهی از نامعادله‌ها به شکل x_j − x_i ≤ b داریم (مثلاً در زمان‌بندی: «کار j حداکثر b واحد بعد از کار i»). می‌خواهیم مقادیری برای x پیدا کنیم که همه برقرار باشند، یا بفهمیم ممکن نیست.

    تبدیل به کوتاه‌ترین مسیر

    هر قید x_j − x_i ≤ b یک یال i → j با وزن b است؛ این دقیقاً شرط کوتاه‌ترین مسیر است: d(j) ≤ d(i) + w(i, j). یک رأس منبع 0 اضافه می‌کنیم که با وزن ۰ به همه وصل است. حالا:

    • اگر گراف دور منفی ندارد، x_i = δ(0, i) یک جواب است.
    • اگر دور منفی دارد، جمع قیدهای روی دور به 0 ≤ عدد منفی می‌رسد: جوابی نیست.

    بلمن–فورد هر دو را تشخیص می‌دهد: O(n·m).

    نکته

    اگر x جواب باشد، x + c هم جواب است؛ این الگوریتم جوابی می‌دهد که همه‌ی x_i ≤ 0 و جمعشان بیشینه است.

    ورودی

    هر سطر [j, i, b] یعنی x_j − x_i ≤ b؛ متغیرها از ۱ شماره‌گذاری شده‌اند.