作者saladim (殺拉頂)
看板Math
標題[其他] SMAWK algorithm中的monotone定義
時間Wed Oct 30 00:57:56 2024
大家好 最近在看SMAWK algorithm, 其中定義了monotone matrix跟
totally monotone matrix. 在原始定義中, montone matrix的定義是:
假設 i 為row index, 令J(i)為row i的leftmost minimum value的column index
則monotone matrix是指有 J(i1) <= J(i2), if i1 < i2特性的matrix
問題來了 我看到一個網頁:
https://medium.com/@shahh8138/smawk-algorithm-242fa751baab
這個網頁裡面用的定義不大一樣: 摘錄如下
Monotone : Formally, an (n x n) matrix M is said to be a monotone
matrix if for every pair of indices i1 i2 and j1 j2 such that,
1 <= i1 < i2 <= n and 1 <= j1 < j2 <= n, the following conditions hold:
1. m(i1, j1) <= m(i1, j2) and m(i2, j1) <= m(i2, j2)
(non-decreasing columns)
2. m(i1, j1) <= m(i2, j1) and m(i1, j2) <= m(i2, j2)
(non-increasing rows)
那我的想法是 是否上面兩個性質可以推得原始定義的性質 但嘗試了一下發現好像
找不出證明路徑, 所以想在此請教大家要怎麼證明呢? 若是跟原始定義不等價,
是否有相似的條件可以推得原始定義的性質?
我是感覺上面兩個條件其中一個寫錯了 第二個條件是不是要變成大於?
也有可能我誤解了整個東西 思路完全錯誤 也請大家幫忙指正 ORZ
謝謝大家
(真的好好奇是為什麼得出上面兩個條件的.........)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.164.96.239 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1730221080.A.3C0.html
1F：→ aaaaajack : 照他英文寫的是要變大於 但就算這樣monge也沒辦法推 10/30 03:23
2F：→ aaaaajack : 到他寫的條件 所以建議是不用理他 實際條件就只是當 10/30 03:23
3F：→ aaaaajack : 你看任意2x2時不能同時左上>右上跟右下>左下 10/30 03:23
4F：→ saladim : 若找不到方式就可能忽略它吧 可能寫錯了 其實嘗試了 10/31 00:50
5F：→ saladim : 一下 這兩個條件應該不是精確的需要改寫.... 10/31 00:52
6F：→ saladim : 另外Monge可以推導出monotone性質, 所以一開始我是 10/31 00:53
7F：→ saladim : 想要嘛從網頁上的兩個條件推導出原始monotone定義 10/31 00:53
8F：→ saladim : 而且我記得Monge matrix不用到網頁上的性質就證明有 10/31 00:57
9F：→ saladim : 原始的montone定義的性質了..anyway只能先這樣 看未 10/31 00:58
10F：→ saladim : 來有沒有人可以幫忙改正這兩個條件一下 XD 10/31 00:58