PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

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

看板Prob_Solve (計算數學 Problem Solving)作者FRAXIS (喔喔)時間14年前 (2010/04/21 09:37)推噓2(2推 0噓 6→)

留言8則, 2人參與討論串2/3 (看更多)

※ 引述《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