我們有一個問題，我們想找到在全國范圍內交換員工位置的最佳路徑。
假設，一家公司允許員工請求搬到另一個城市，前提是該城市有空缺，并且有人愿意接受他們即將出現的空缺職位。檢查示例：
- 目前在洛杉磯作業的員工 A 想搬到波士頓。
- 目前在波士頓作業的員工 B 想搬到紐約。
- 目前在紐約作業的員工 C 想搬到洛杉磯。
在上面的三角形中，我們可以授予所有三個員工搬家的權限，因為一旦他們搬家，就不會有任何空缺。但在以下情況下情況會變得更加復雜：
- 多名員工正在爭奪同一地點。我們可以通過某種假設的分數來解決這個問題，比如為公司作業的年限優先。
- 我們有更多的城市需要考慮。（以百計）
- 我們有更多的員工需要考慮。（數十萬）
最終目標是授予最多數量的移動權限，而不會導致系統出現任何空缺。
我們目前正在探索模擬所有交換路徑的想法，然后選擇產生最多移動數的路徑。
但是我感覺這個問題以前在野外也存在過，就是不知道要找什么關鍵詞才能得到更多的洞見。有任何想法嗎？我們應該研究什么演算法？
uj5u.com熱心網友回復：
洗掉不可能的移動請求，像這樣
A,B are specific cities. n is amy city
RAB is a request to move from A to B
RAn is a request to move from A
RnA is a reuest to move to A
CAn is the number of requests to move from A
CnA is the number of requests to move to A
set flag TRUE
WHILE ( flag == TRUE )
set flag = FALSE
LOOP A over all cities
IF CAn > CnA then not all RAn can be permitted.
Remove lower scoring requests until CAn == CnA.
set flag TRUE
一旦這些“不可能”的移動被移除，所有剩余的移動請求都是“不平衡的”。也就是說，對一個城市的所有移動請求與來自一個城市的所有移動請求相同。從那時起，您選擇實施哪個周期不再重要：一旦實施它們，剩余的請求仍然處于平衡狀態。并且無論它們在哪個移動周期和哪個順序中執行，它都會保持平衡，直到所有剩余請求都為零，并且無論它們如何執行，移動的總數都將完全相同。（這個解釋是由于https://stackoverflow.com/users/109122/rbarryyoung）
這是實作這個的 C 代碼
void removeForbidden()
{
bool flag = true;
while (flag)
{
flag = false;
for (auto &city : sCity)
{
auto vFrom = RequestCountFrom(city);
auto vTo = RequestCountTo(city);
if (vFrom.size() > vTo.size())
{
for (int k = vTo.size(); k < vFrom.size(); k )
{
vFrom[k]->allowed = false;
}
flag = true;
}
}
}
std::cout << "Permitted moves:\n";
for (auto &R : vRequest)
{
if (R.allowed)
std::cout << R.text();
}
}
完整的應用程式代碼位于https://gist.github.com/JamesBremner/5f49beaca59a7a7043e356fbb35f0d09
輸入是一個空格分隔的文本檔案，有 4 列：員工姓名、員工分數、從城市到城市
這是基于您的示例的示例輸入，但添加了另一個不允許的請求
e1 1 a b
e2 1 b c
e3 1 c a
e4 0 a c
這個的輸出是
Permitted moves:
e1 1 a b
e2 1 b c
e3 1 c a
注意：我沒有實施評分。為簡單起見，我假設移動請求按分數降序輸入。因此，必要時丟棄的請求會根據您輸入它們的順序進行更改。我假設您將能夠實施您需要的任何評分系統。另請注意，除非您為來自城市的每個請求計算唯一分數，否則哪些請求被拒絕可能會因輸入順序而異。
uj5u.com熱心網友回復：
我正要在評論中發布這個，但它超過了實際允許的字符。
我不確定現有的可能解決此問題的高級演算法，但您可以自定義適合一些基本演算法：
- 想要從 city1 移動到某個 city2 的員工是從 city1 到 city2 的有向邊。確保如果 2 名員工想從 A 移動到 B，則為此添加 2 條有向邊，或者以某種方式保持數量的計數。
- 查找圖形的不相交分量。
- 在每個不相交的組件中，找到可能的最大圓。一個圓圈的意思
A -> B -> C -> A。 - 洗掉這些邊緣并記錄成功交換的數量。
- 重復直到在任何不相交的組件中都沒有圓圈。
這是一個貪心演算法。目前我仍然不太確定它是否會在每種情況下產生最佳解決方案。任何輸入表示贊賞。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/415943.html
標籤：