這裏是情況。 假設我們有x個學生編號爲1,2 ... x，生活在城市的固定地點。 有y個考試中心編號爲1,2,3，y，每個 的容量分別爲'i-can-hold [y]'。 學生我到考試中心j的距離是'我必須走路[i] [j]'算法處理考生中心座位的學生
你能提出一個算法，確保總距離 旅行是最小的？ （即每個學生距考試中心的距離之和）
很顯然，我可以持有[1] + i-can-hold [2] + ... + i-can-hold [y]> x
我正在考慮創建這樣一個程序，該程序可以使至少 麻煩進行考試。 在googlemap的幫助下，可以實施實施。
一般來說，對距離和容量沒有任何限制，這是一個最小成本最大流問題。
i-can-hold容量的水槽，耗費0i-have-to-walk。Ford-Fulkerson算法可用於查找最大流量，但不考慮成本。儘管通過更簡單的例子來了解流量網絡，但它可能有助於學習。
有很多不同的算法用於最小化成本。一個是「連續最短路徑」。這個想法是反覆在剩餘網絡中找到從源到匯的最小代價路徑，並沿着這條路徑添加一條流，直到找不到更多路徑。
例如：
a）一個流網絡，其中每個頂點被標記爲（成本，容量）。包含連接到2箇中心列的3名學生列。 b）沿着最短路徑（可以在Bellman-Ford中找到）在剩餘網絡中添加流量。剩餘網絡是根據可用容量（容量減去每個方向的流量）創建的圖表。
c）沿另一路徑增加更多流量。
d）最佳流程。已經沿着一條改變已經添加的流程的路徑添加了流程。這是允許的，因爲剩餘網絡具有與流量相反方向的容量。
參見：
我會閱讀這些維基。 我沒有看到任何按鈕感謝。 – user1371666
你能給我看一張圖嗎，因爲這些維基已經超過了我的頭。非常複雜。你能提供一個上述算法的簡單說明嗎？ – user1371666
我把它的算法的結果是學生對考試中心的分配。 – fgb
重複/相關/類似：[算法 - 匹配學生考試中心]（http://stackoverflow.com/questions/12507361/algorithm-matching-student-examination-centers）（不投票結束，只是指出相似性，我認爲這個問題之間存在一些差異，因爲另一個問題只是要找出是否有最佳解決方案，每個學生被分配到最近的考試中心） – amit
如果你真的在做一些真正的事情，考慮公共交通瓶頸，例如橋樑在鐵路軌道上，學生們不得不在公共汽車或電車內塞滿鐵路，甚至是非常短的距離。仍然在公共交通工具上，也要考慮轉換線路。 「距離」最終應該在時間（分鐘）內測量，而不是米。不應該太難計算所有的路線，接近旅行的分鐘，然後使用任何算法，人們會提供你作爲答案（即使最初的目的是爲了距離）。 –