AlgoVerse

الگوریتم گیل–شپلی (ازدواج پایدار)

مردان به ترتیب علاقه خواستگاری می‌کنند و زنان همیشه بهترین پیشنهاد تا آن لحظه را نگه می‌دارند؛ نتیجه یک جورسازی پایدار است: هیچ دو نفری نیستند که همدیگر را به همسرشان ترجیح دهند. حداکثر n² خواستگاری.

n مرد و n زن داریم و هر کدام همه‌ی افراد طرف مقابل را به ترتیب علاقه رتبه داده‌اند. یک جورسازی ناپایدار است اگر مرد m و زن w باشند که همدیگر را به همسر فعلی‌شان ترجیح دهند (یک «جفت سرکش»). می‌خواهیم جورسازی پایدار پیدا کنیم. همین مسئله در تخصیص دستیاران پزشکی به بیمارستان‌ها به کار می‌رود.

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

سه مرد و سه زن. زن ۰ مرد ۰ را به خاطر مرد ۱ رها می‌کند و زن ۱ مرد ۲ را به خاطر مرد ۰؛ نتیجه: (۰، ۱)، (۱، ۰)، (۲، ۲). هر سطر M فهرست زن‌ها به ترتیب علاقه‌ی یک مرد است و هر سطر W فهرست مردها برای یک زن.

  1. def gale_shapley(M, W):
  2. # M[m]: man m's list of women, best first; W[w]: woman w's list of men, best first. People are numbered from 0.
  3. n = len(M)
  4. for prefs in M + W:
  5. if sorted(prefs) != list(range(n)):
  6. return None
  7. rank = [[0] * n for _ in range(n)]
  8. for w in range(n):
  9. for i in range(n):
  10. rank[w][W[w][i]] = i
  11. wife = ["·"] * n
  12. husband = ["·"] * n
  13. nxt = [0] * n # the next woman on each man's list
  14. free = list(range(n))
  15. rejections = 0
  16. while free:
  17. m = free[0]
  18. w = M[m][nxt[m]]
  19. nxt[m] = nxt[m] + 1
  20. if husband[w] == "·":
  21. husband[w] = m
  22. wife[m] = w
  23. free.pop(0)
  24. elif rank[w][m] < rank[w][husband[w]]:
  25. old = husband[w]
  26. husband[w] = m
  27. wife[m] = w
  28. wife[old] = "·"
  29. free.pop(0)
  30. free.append(old)
  31. else:
  32. rejections = rejections + 1
  33. return wife

ناوردا: هر زن از وقتی اولین پیشنهاد را گرفت نامزد می‌ماند و نامزدش فقط بهتر می‌شود؛ هر مرد به زن‌ها به ترتیب فهرستش پیشنهاد می‌دهد.

شروع اجرا

free—
wife—
husband—
nxt—

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

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

M list

[0, 1, 2][0, 2, 1][1, 0, 2]

W list

[1, 0, 2][0, 1, 2][0, 1, 2]

Call stack

  1. gale_shapley()خط 1
گام ۱ از ۱۰۳
خط سیاه = propose · خط نارنجی = گام کلیدیpropose: 0/6 · engaged: 0/3 · switch: 0/2 · reject: 0/1
    توضیح

    مسئله

    n مرد و n زن داریم و هر کدام همه‌ی افراد طرف مقابل را به ترتیب علاقه رتبه داده‌اند. یک جورسازی ناپایدار است اگر مرد m و زن w باشند که همدیگر را به همسر فعلی‌شان ترجیح دهند (یک «جفت سرکش»). می‌خواهیم جورسازی پایدار پیدا کنیم. همین مسئله در تخصیص دستیاران پزشکی به بیمارستان‌ها به کار می‌رود.

    الگوریتم (Gale و Shapley، ۱۹۶۲)

    تا وقتی مرد آزادی هست، او به بهترین زنی که هنوز به او پیشنهاد نداده پیشنهاد می‌دهد. زن اگر آزاد است می‌پذیرد؛ اگر نامزد دارد، بهتر را نگه می‌دارد و دیگری آزاد می‌شود.

    چرا درست است

    • پایان: هر مرد به هر زن حداکثر یک بار پیشنهاد می‌دهد: حداکثر n² گام.
    • همه جفت می‌شوند: زنی که پیشنهاد گرفت دیگر آزاد نمی‌شود؛ اگر مردی همه را امتحان کرده و آزاد مانده بود، همه‌ی زن‌ها نامزد بودند، که با برابر بودن تعداد ممکن نیست.
    • پایداری: اگر m زن w را به همسرش ترجیح دهد، قبلاً به w پیشنهاد داده و w او را به خاطر کسی بهتر رد کرده است.

    نتیجه برای پیشنهاددهندگان بهترین جورسازی پایدار ممکن است.

    ورودی

    سطر m از M فهرست زن‌ها به ترتیب علاقه‌ی مرد m است و سطر w از W فهرست مردها برای زن w؛ افراد از ۰ شماره‌گذاری شده‌اند.