Re: [問題] 人生成就問題

[FRAXIS (喔喔)]

※ 引述《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
推 ECZEMA:你得到我了! 如果可以知道兩點連線間的權重且線性可加，我
→ ECZEMA:找得到類似題，但人生成就分數是統計多個同樣升學管道學生
→ ECZEMA:所決定的 我就卡關了…可是 flow 的例子又很像這題目
→ ECZEMA:如果 分數可以用 函數 f(x,y,z,w) 擬合出來，就又變成要討
→ ECZEMA:論不同函數問題有沒有精確解… 我先去了解一下 convex...
推 ECZEMA:ILP 這關鍵字很有用耶! 不過看到是 NP-hard 心涼了一半~
→ FRAXIS:就算是NP-Hard還是可以解 只是看速度夠不夠而已..
→ FRAXIS:不然你就把f換成一個比較容易算的函數.. 找近似