Re: [問題] 人生成就問題
※ 引述《ECZEMA (加油!)》之銘言：
: (我知道如果只考慮小學 國中，是 bipartite matching 或說是 指派問題，因為沒有
: 提供兩個階段的人生成就分數，不能用 bipartite matching 兩階段兩階段串聯來解，
: 人生成就分數只有四個階段一起考慮才有)
: 若各階段學校數目為 1000 所時，還能用嗎? 告訴我可以參考哪一種演算法就好了…
: 給我幾個明確的關鍵字…謝謝大家… 希望聽到 「這不就是典型的 _____ 問題嗎？」
: XD
把圖建成4分圖，就是分成小學、國中、高中、大學四部分，同一部分之中互不相連。
然後加上一個s點連向小學，大學連向t點。
要找出5個人都沒有當過同學，就等於是判斷這個圖是不是5-vectex-connected。
利用Network Flow算法就可以判斷了。
但是現在還有一個目標函數，是希望人生成就的總和最高。如果人生成就
可以只要看兩個階段之間，那麼只要把邊加上權重，用Minimum Cost Maximum Flow
演算法來解，我想應該就可以找到解答了。
但是現在人生成就卻需要4個階段一起考量，我就不知道該怎麼用Network Flow了。
這個問題可以用數學規劃表示成這樣
Objective function: Σ f(x, y, z, w)
f是人生成就的函數
Constraints: 總共有m個人，針對第i個人有xi, yi, zi, wi四個變數
xi, yi, zi, wi 是 1 ~ n 之間的整數，n是學校數目
且對於i != j, xi != xj, yi != yj, zi != zj, wi != wj
本問題本身就是Interger Programming，如果f函數有特殊性質，像是Convex，
那應該可以用Convex Optimization的技巧來尋找解答。
當然，如果f有更強烈的性質可以使用，可能就不用那麼麻煩了..
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50
推
04/21 11:42, , 1F
04/21 11:42, 1F
→
04/21 11:43, , 2F
04/21 11:43, 2F
→
04/21 11:47, , 3F
04/21 11:47, 3F
→
04/21 11:57, , 4F
04/21 11:57, 4F
→
04/21 12:00, , 5F
04/21 12:00, 5F
推
04/21 12:23, , 6F
04/21 12:23, 6F
→
04/21 12:51, , 7F
04/21 12:51, 7F
→
04/21 12:51, , 8F
04/21 12:51, 8F
討論串 (同標題文章)