AlgoVerse

الگوریتم مجارستانی (تخصیص بهینه)

هر کارگر را به یک کار متفاوت با کمترین هزینه‌ی کل می‌دهد: تطابق را فقط روی خانه‌های صفرِ ماتریس کاهش‌یافته می‌سازد و هر جا گیر کرد، صفر تازه می‌سازد.

مسئله‌ی تخصیص: n کارگر و n کار با ماتریس هزینه؛ هر کارگر دقیقاً یک کار و هر کار دقیقاً یک کارگر، با کمترین هزینه‌ی کل.

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

سه کارگر و سه کار؛ کمترین هزینه‌ی کل ۵ است (۱ + ۲ + ۲).

  1. def hungarian(cost):
  2. # Assign each row (worker) to a different column (job) with the least total cost.
  3. n = len(cost)
  4. u = [min(row) for row in cost] # row potentials
  5. v = [0] * n # column potentials
  6. match = [-1] * n # match[c] is the row assigned to column c
  7. for i in range(n):
  8. while True:
  9. # Reduced costs: the zeros are the pairs that may be matched.
  10. reduced = [[cost[r][c] - u[r] - v[c] for c in range(n)] for r in range(n)]
  11. seen_rows, seen_cols = set(), set()
  12. if augment(i, reduced, match, seen_rows, seen_cols):
  13. break
  14. # No path of zeros: lower the reduced costs just enough to make a new zero.
  15. delta = min(reduced[r][c] for r in seen_rows for c in range(n) if c not in seen_cols)
  16. for r in seen_rows:
  17. u[r] = u[r] + delta
  18. for c in seen_cols:
  19. v[c] = v[c] - delta
  20. total = sum(cost[match[c]][c] for c in range(n))
  21. return total
  24. def augment(r, reduced, match, seen_rows, seen_cols):
  25. seen_rows.add(r)
  26. for c in range(len(reduced)):
  27. if c in seen_cols or reduced[r][c] != 0:
  28. continue
  29. seen_cols.add(c)
  30. if match[c] == -1:
  31. match[c] = r
  32. return True
  33. if augment(match[c], reduced, match, seen_rows, seen_cols):
  34. match[c] = r
  35. return True
  36. return False

ناوردا: هیچ هزینه‌ی کاهش‌یافته‌ای منفی نیست و هر جفت تطابق‌شده هزینه‌ی کاهش‌یافته‌ی صفر دارد؛ پس هزینه‌ی تطابق کامل برابر Σu + Σv است و از هر تخصیص دیگری بیشتر نیست.

شروع اجرا

u—
v—
match—

cost

413
205
322

reduced

جدول هنوز خالی است.

درخت فراخوانی‌های بازگشتی

نارنجی پر = فراخوانی در حال اجرا · حاشیه‌ی نارنجی = هنوز روی پشته · خاکستری = تمام شده

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

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

cost list

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

Call stack

  1. hungarian()خط 1
گام ۱ از ۱۰۰
خط سیاه = assigned · خط نارنجی = گام کلیدیlook: 0/4 · take: 0/3 · assigned: 0/3 · relabel: 0/1 · total: 0/1
    توضیح

    ایده

    مسئله‌ی تخصیص: n کارگر و n کار با ماتریس هزینه؛ هر کارگر دقیقاً یک کار و هر کار دقیقاً یک کارگر، با کمترین هزینه‌ی کل.

    پتانسیل‌ها

    به هر سطر عدد u و به هر ستون عدد v می‌دهیم طوری که هزینه‌ی کاهش‌یافته cost − u − v هیچ‌جا منفی نباشد. اگر بتوانیم تطابقی کامل فقط از خانه‌های صفر بسازیم، هزینه‌اش Σu + Σv است و هیچ تخصیصی ارزان‌تر نیست؛ پس بهینه است.

    الگوریتم

    1. برای هر سطر، روی خانه‌های صفر یک مسیر افزایشی پیدا کن (درست مثل تطابق دوبخشی).
    2. اگر پیدا نشد، کوچک‌ترین هزینه‌ی کاهش‌یافته δ را بین سطرهای دیده‌شده و ستون‌های ندیده پیدا کن، به u سطرهای دیده‌شده δ اضافه و از v ستون‌های دیده‌شده δ کم کن. صفرهای قبلی می‌مانند و دست‌کم یک صفر تازه پیدا می‌شود.

    در trace به چه چیزی نگاه کنی

    • جدول reduced را ببین: صفرهایش یال‌های مجاز تطابق‌اند و با هر تغییر پتانسیل صفر تازه‌ای ظاهر می‌شود. match[c] سطرِ ستون c است.