مسئلهٔ تخصیصِ یک‌به‌یک می‌پرسد چگونه چند کار را میان همان تعداد عامل تقسیم کنیم که هر عامل دقیقاً یک کار بگیرد، هیچ کار تکرار نشود و مجموع هزینه کمینه باشد. انتخاب ارزان‌ترین گزینهٔ هر ردیف لزوماً این هدف را تأمین نمی‌کند؛ چون انتخاب امروز یک گزینه را از ردیف‌های بعد می‌گیرد. اینجا یک جدول سه‌درسهٔ ساختگی را با برنامه‌ریزی پویا حل و با تمام شش جایگشت مستقل کنترل می‌کنیم.
اول قیدِ یک‌به‌یک را بخوانیم
ردیف‌ها عامل‌های A، B و C و ستون‌ها کارهای ۰، ۱ و ۲ هستند. عددها فقط هزینهٔ آموزشی‌اند؛ واحد پول، زمان واقعی، مهارت یا عملکرد کارکنان نیستند. انتخاب باید در هر ردیف و هر ستون دقیقاً یک خانه داشته باشد. اگر یک عامل بتواند چند کار بگیرد، یا بعضی کارها انجام نشوند، مدل این صفحه عیناً همان مسئله نیست.
| عامل | کار۰ | کار۱ | کار۲ |
|---|---|---|---|
| A | ۱ | ۲ | ۳ |
| B | ۱ | ۱۰۰ | ۱۰۰ |
| C | ۱۰۰ | ۲ | ۱ |
انتخاب محلی چگونه به هزینهٔ ۱۰۲ می‌رسد؟
قاعدهٔ حریصانهٔ ما ردیف‌ها را به ترتیب A، B، C می‌خواند و ارزان‌ترین ستونِ هنوز آزاد را برمی‌دارد؛ در تساوی، شمارهٔ کوچک‌تر انتخاب می‌شود. A کار۰ را با هزینهٔ۱ می‌گیرد. B از دو گزینهٔ۱۰۰، کار۱ را می‌گیرد و برای C کار۲ با هزینهٔ۱ می‌ماند. مجموع ۱+۱۰۰+۱=۱۰۲ است.
این فقط شکست همین قاعده روی همین ورودی است؛ نمی‌گوییم هر روش حریصانه در هر مسئله بد است. اگر A با هزینهٔ۲ کار۱ را بگیرد، B می‌تواند کار۰ با هزینهٔ۱ و C کار۲ با هزینهٔ۱ بگیرد؛ مجموع۴ می‌شود. یک واحد صرفه‌جوییِ محلیِ A، اینجا هزینهٔ بزرگی به انتخاب بعدی تحمیل کرد.
زیرمسئله: کدام ستون‌ها قبلاً مصرف شده‌اند؟
هر زیرمجموعهٔ ستون‌ها را با mask ثبت می‌کنیم؛ بیتِ j برابر۱ یعنی کارِ j قبلاً واگذار شده است. تعداد بیت‌های۱ مشخص می‌کند چند ردیف اول تخصیص گرفته‌اند. پس dp[mask] کمترین هزینه برای همان ردیف‌های اول با دقیقاً همان ستون‌های مصرف‌شده است. فقط تعداد ستون‌ها کافی نیست؛ آزادبودن کار۰ با آزادبودن کار۱ اثر یکسان ندارد.
i = number_of_set_bits(mask) next_mask = mask | (1 << j) # j must be free candidate = dp[mask] + cost[i][j]
کد برای هر ستون آزاد، نامزد را می‌سازد و فقط اگر کمتر باشد مقدار و والد را عوض می‌کند. از mask=۰ با هزینهٔ۰ شروع می‌شود. در پایان mask=۷ یعنی هر سه ستون مصرف شده‌اند؛ دنبال‌کردن والدها از آخر به اول، ستون‌های [۱،۰،۲] را برای A، B و C بازمی‌سازد. جمع هزینهٔ همین انتخاب دوباره کنترل می‌شود؛ تنها عددِ کمینه را بدون انتخابِ سازگار تحویل نمی‌دهیم.
از کجا بدانیم جواب۴ درست است؟
تابع مستقل، هر شش جایگشت ستون‌ها را بدون استفاده از جدول dp می‌سازد و هزینهٔ کامل هر کدام را جمع می‌کند. کمترین مقدار۴ است و با نتیجهٔ dp برابر می‌شود. دفتر JSON همهٔ جایگشت‌ها، مقدار هر mask و هر نامزدِ انتقال را نگه می‌دارد. این کنترلِ متناهی برای مثال سه‌ردیفی است؛ اثبات کارایی روی دادهٔ بزرگ محسوب نمی‌شود.
در مسئلهٔ مربعی با n ردیف، روش آموزشی تا ۲به‌توانn زیرمجموعه و برای هر کدام تا n انتخاب دارد؛ بنابراین برای مسئلهٔ بزرگ مناسب نیست. کد عمداً اندازهٔ۱ تا۹، جدول مربعی و هزینهٔ صحیح نامنفی را می‌پذیرد. یک جدولِ دارای تساوی هم آزموده شده است؛ هزینهٔ بهینه می‌تواند یکتا باشد یا نباشد و ترتیبِ شکستن تساوی الزاماً همهٔ جواب‌های بهینه را فهرست نمی‌کند.
این فایل، الگوریتم Hungarian یا سامانهٔ اعزام نیست
مستند SciPy تعریف مسئلهٔ تخصیص و تفاوت جدول مربعی با مستطیلی را روشن می‌کند؛ اما در این تمرین SciPy یا Hungarian اجرا نشده است. روش این فایل، dp زیرمجموعه و بررسی کاملِ نمونهٔ کوچک است. عددِ ارزان اگر گزینه از نظر مهارت، مجوز یا زمان ناممکن باشد، مجوز انتخاب آن گزینه نیست؛ چنین قیدهایی باید پیش از حل در مدل درست بیان شوند.
ماتریس مهارت کارشناس اعتبار گزینهٔ ارجاع را بررسی می‌کند و قواعد تقسیم سرنخ مالکیت و تحویل را؛ این صفحه فقط کمینه‌سازیِ هزینهٔ جدولِ ازپیش‌معتبر را حل کرد. برای پاسخ‌گویی و پیگیری، ابتدا تصمیم مجاز و دادهٔ لازم را در راهکارهای اپرا مشخص کنید؛ این مثال وجود بهینه‌ساز تخصیص در محصول را وعده نمی‌دهد.
فایل تمرین و منبع
کد کامل Python؛ بازتولید محاسبه و کنترل مستقل · دادهٔ آموزشی، مراحل محاسبه و نتیجهٔ کنترل مستقل
منابع در 2026-11-04 خوانده شدند؛ این تاریخ، تاریخ انتشار منبع نیست. مثال‌ها و فایل‌های این راهنما آموزشی و ساختهٔ تحریریه‌اند.