[其他] 離散一題

看板Math作者 (俊偉)時間3年前 (2020/09/09 18:28), 編輯推噓0(0推 0噓 24→)
留言24則, 1人參與, 3年前最新討論串6/15 (看更多)
題目: https://imgur.com/a/t2rJUCV 題目裡job/candidate都有n個 (a)部分不太懂該如何下手 也不清楚Hint裡引入imaginary entities的作用 (b)部分不清楚推的合不合理 Assume 2 stable matching T1, T2 Assume (j0, c0)∈T1, j0 unmatched in T2 c0 cannot be unmatched in T2 -> rogue couple (j0, c0) ->Assume (j1, c0)∈T2 j1 cannot be unmatched in T1 -> rogue couple (j1, c0) ->Assume (j1, c1)∈T1 -> (j2, c1)∈T2 -> ... ->(jn, cn)∈T1 cn cannot be unmatched in T2, and j0 is the only unmatched in T2 -> (j0, cn)∈T2 -> contradicts to j0 unmatched in T2 -> The statement is true -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.42.154.94 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1599647320.A.E9C.html
→
09/10 00:22, 3年前 , 1F
(a)部份 假設candidate/job為c1,c2,...,cn/j0,..,jn
09/10 00:22, 1F
→
09/10 00:24, 3年前 , 2F
就假設c0的喜好排序就是j1,j2,...,jn 並且jk以下就
09/10 00:24, 2F
→
09/10 00:27, 3年前 , 3F
不想應徵 而j1的喜好排序是c{j1},c{j2},...,c{jn}
09/10 00:27, 3F
→
09/10 00:31, 3年前 , 4F
為免符號混淆 j1的喜好排序改成c{i1},...,c{in} 並
09/10 00:31, 4F
→
09/10 00:32, 3年前 , 5F
且c{it}以下就不想應聘
09/10 00:32, 5F
→
09/10 00:34, 3年前 , 6F
現在引入imaginary candidate/job Nc1,Nc2,...,Ncn/
09/10 00:34, 6F
→
09/10 00:37, 3年前 , 7F
Nj1,Nj2,...,Njn 共2n個節點 對某個c而言 如果js排
09/10 00:37, 7F
→
09/10 00:38, 3年前 , 8F
在Njs後面 就代表其實c不想要js這份工作 而對於某個
09/10 00:38, 8F
→
09/10 00:40, 3年前 , 9F
j而言 如果cs排在Ncs後面就代表j其實不想用cs這個人
09/10 00:40, 9F
→
09/10 00:42, 3年前 , 10F
而我們可以改寫c1的喜好排序為
09/10 00:42, 10F
→
09/10 00:43, 3年前 , 11F
j1,j2,...,j{k-1},Nj1,Nj2,...,Njn,jk,j{k+1},..,jn
09/10 00:43, 11F
→
09/10 00:45, 3年前 , 12F
並改寫j1的喜好排序為c{j1},c{j2},...,c{j(t-1)},
09/10 00:45, 12F
→
09/10 00:46, 3年前 , 13F
Nc1,Nc2,...,Ncn,c{it},...,c{in}
09/10 00:46, 13F
→
09/10 00:49, 3年前 , 14F
其他entities的喜好排序也是依此邏輯修改
09/10 00:49, 14F
→
09/10 00:51, 3年前 , 15F
符號還是混亂了 很抱歉
09/10 00:51, 15F
→
09/10 00:53, 3年前 , 16F
再去證明按上面所述而排出來的stable matching的確
09/10 00:53, 16F
→
09/10 00:54, 3年前 , 17F
滿足原問題的五個條件 細節應該不難補完才對
09/10 00:54, 17F
→
09/10 01:15, 3年前 , 18F
(b)部份我也是這樣想的 只是中間點點點的部份總感覺
09/10 01:15, 18F
→
09/10 01:16, 3年前 , 19F
沒有達到數學上的嚴謹 不過這樣的證明一般還是可以
09/10 01:16, 19F
→
09/10 01:16, 3年前 , 20F
被接受的 XD
09/10 01:16, 20F
→
09/10 16:31, 3年前 , 21F
補充一下(a)部份 為避免某c比較偏好沒有工作時 所有
09/10 16:31, 21F
→
09/10 16:33, 3年前 , 22F
的Nj卻都跑去和Nc媒合 所以每一個Nj的喜好排序為
09/10 16:33, 22F
→
09/10 16:34, 3年前 , 23F
c1,c2,...,cn,Nc1,Nc2,...,Ncn 相同地 每個Nc都是
09/10 16:34, 23F
→
09/10 16:35, 3年前 , 24F
j1,j2,...,jn,Nj1,Nj2,...,Njn
09/10 16:35, 24F
‣ 更多 LiquidTLO 的文章
文章代碼(AID): #1VMAvOwS (Math)
討論串 (同標題文章)
完整討論串 (本文為第 6 之 15 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共15篇)
‣ 更多 LiquidTLO 的文章
文章代碼(AID): #1VMAvOwS (Math)