作者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/cn.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