3
有一組9名學生和3所學校每所學校可以分配最多3名學生。每個學校和學生都有它的座標。現在我們必須以這樣的方式分配學生，使得距離所有學校到學校的學生應該是最低限度的。最小距離
我在接受採訪時被問到了這個問題。誰能爲此提出一個算法？
最初我嘗試了貪婪的方法，但沒有奏效。然後我嘗試應用動態編程方法，但無法提出最佳的子結構。
Q
最小距離
A
回答
4
每所學校有3個地方，全部3所學校有9個地方。你應該找到9個地方和9個學生之間的最佳匹配。
此作業問題可以用Hungarian algorithm解決。
1
由於問題規模足夠小，徹底搜索如何？
- 第一所學校選擇9名中的3名學生開始。
- 第二學校從剩餘的6箇中選擇3個學生。
- 最後一所學校被剩下的3名學生卡住了。
所以(9 choose 3) * (6 choose 3) = 1680
+0
我正在尋找一個有效的解決方案。 – Avinash
相關問題
- 1. 與最小距離
- 2. 的最小距離
- 3. 更改ViewPager最小距離
- 4. 找到最小距離
- 5. 最小海明距離
- 6. 最大 - 最小距離的計算
- 7. 找到最長距離的最小值
- 8. 找到距離地點最小總距離的點的算法
- 9. 距離（最短）
- 10. 確定最小漢明距離
- 11. 線性迴歸 - 最小化距離
- 12. 找到xyz之間的最小距離
- 13. 最小皮帶，已知距離
- 14. 使用for循環的最小距離
- 15. Matlab：幫助尋找最小距離
- 16. 最小化餘弦距離theano
- 17. NetLogo：海龜之間的最小距離
- 18. K-means - 如何計算最小距離
- 19. 矩形之間的最小距離
- 20. 設置ScatterViewItem最小拖動距離
- 21. Python中三維點之間的最小距離，平均距離和最大距離
- 22. 最近距離（分離集）
- 23. 在距離彼此最小距離的圓上隨機產生數量的GameObjects
- 24. 選擇距離特定LatLng對象最小距離的位置android
- 25. 查找離開路線集的最小距離
- 26. 如何設置分配器控制的最小/最大距離？
- 27. 尋找最短距離覆蓋最小單元數的算法
- 28. 通過最小化正交距離最合適的平面
- 29. 取K個元素並最大化最小距離
- 30. 最小，最大，各組/縣之間的平均點距離
手頭的問題被稱爲匹配 – RobAu
您能否提供關於二分圖匹配一些很好的閱讀材料二分圖。 – Avinash
這本書很好，但可能太理論了：[「MD匹配理論」，L.Lovász]（http://books.google.ru/books/about/Matching_Theory.html?id=mycZP-J344wC&redir_esc=y） 。 –