x***g
发帖数: 52 | 1 有一个集合 {a1, a2, a3 ... an}
其上定义有 >, <, <=, >=, ==, 这些关系均可传递
不符合以上条件的定义为 <>
例如在有限个复数集合上 1 < 2, 1+i < 2+i
但是我们只知道 3 <> 2 + i, 无法比较大小
希望找到该集合的所有满足以下条件的子集：
（1）子集内的元素不存在 <> 关系
（2）任意一个子集不属于另一个子集
实在想不出有效的算法，请各位大侠指教。
谢谢啦！ |
x***g
发帖数: 52 | |
x***g
发帖数: 52 | |
e***e
发帖数: 3872 | 4 构造一个图，任何有传递关系的node pair有边链接，O(n^2)复杂度。
构造graph laplacian，解最小特征值，0特征值对应的特征向量给出这些集合；假定集
合数量为m<=n，则复杂度为O(m*n^2)。
【在 x***g 的大作中提到】
: 有一个集合 {a1, a2, a3 ... an}
: 其上定义有 >, <, <=, >=, ==, 这些关系均可传递
: 不符合以上条件的定义为 <>
:
: 例如在有限个复数集合上 1 < 2, 1+i < 2+i
: 但是我们只知道 3 <> 2 + i, 无法比较大小
:
: 希望找到该集合的所有满足以下条件的子集：
: （1）子集内的元素不存在 <> 关系
: （2）任意一个子集不属于另一个子集
|
x***g
发帖数: 52 | 5 谢谢。
这是给出了connected component，但是我的问题好像还不是。例如：
1 < 2
1 < 1 + i
这样的话三个元素就都在一个集合里了，但是 2 <> 1 + i
应该跟directed graph的特性有关吧。
【在 e***e 的大作中提到】
: 构造一个图，任何有传递关系的node pair有边链接，O(n^2)复杂度。
: 构造graph laplacian，解最小特征值，0特征值对应的特征向量给出这些集合；假定集
: 合数量为m<=n，则复杂度为O(m*n^2)。
|
X****r
发帖数: 3557 | 6 随便想了一下，不一定对。
你引入两个元素和，分别大于和小于其他所有元素，然后把原来的有向图里可
以被传递律推导出来的边删掉，最后枚举一下和之间的路径，每一条就代表你
想要的一个子集。
【在 x***g 的大作中提到】
: 谢谢。
: 这是给出了connected component，但是我的问题好像还不是。例如：
: 1 < 2
: 1 < 1 + i
: 这样的话三个元素就都在一个集合里了，但是 2 <> 1 + i
: 应该跟directed graph的特性有关吧。
|
t****t
发帖数: 6806 | 7 听上去好象是对的...
【在 X****r 的大作中提到】
: 随便想了一下，不一定对。
: 你引入两个元素和，分别大于和小于其他所有元素，然后把原来的有向图里可
: 以被传递律推导出来的边删掉，最后枚举一下和之间的路径，每一条就代表你
: 想要的一个子集。
|
e***e
发帖数: 3872 | 8 哦，那用<>作为边，求（最大）独立子集，这样是指数复杂度（不过thrust模板库的例
子中有并行算法）。
你问题其实没有要求最大，所以如果是有限精度的复数，或有限维向量，可以逐个维度
排序，扫描组合等值项，保留非等值项进入下一维排序。这样会比独立子集算法有效。
不知道我理解对没，1+i<>2+2i？否则的话这样求出的集合数量比较多。
【在 x***g 的大作中提到】
: 谢谢。
: 这是给出了connected component，但是我的问题好像还不是。例如：
: 1 < 2
: 1 < 1 + i
: 这样的话三个元素就都在一个集合里了，但是 2 <> 1 + i
: 应该跟directed graph的特性有关吧。
|
r****y
发帖数: 26819 | 9 为何需要这两个元素呢？做成完全图不就可以了？
【在 X****r 的大作中提到】
: 随便想了一下，不一定对。
: 你引入两个元素和，分别大于和小于其他所有元素，然后把原来的有向图里可
: 以被传递律推导出来的边删掉，最后枚举一下和之间的路径，每一条就代表你
: 想要的一个子集。
|
l******6
发帖数: 340 | 10 1. 把 == 关系都元素合并到一个node。否则不能确定无环， 把相等元素归并到一个集
合也满足要求
2 以 < 和 <= 的关系建立有向图（想不到 a <= b <= c <= a 成环的例子 ， 如果能
成环只能取等， 会归到1里面吧）
3. topological sort
4. 按topological 的顺序做dfs， 访问的点归为一个子集并从图中删除或者标为不可
再访问。 |
x***g
发帖数: 52 | 11 谢谢啊，感觉好像是对的。
这句话不太理解，能否展开说说？
：然后把原来的有向图里可以被传递律推导出来的边删掉
有元素，然后把原来的有向图里可
65533;1之间的路径，每一条就代表你
【在 X****r 的大作中提到】
: 随便想了一下，不一定对。
: 你引入两个元素和，分别大于和小于其他所有元素，然后把原来的有向图里可
: 以被传递律推导出来的边删掉，最后枚举一下和之间的路径，每一条就代表你
: 想要的一个子集。
|
x***g
发帖数: 52 | 12 谢谢。第4点不太理解。
是说按3中排好的顺序取node，然后在图中DFS么？
这样的话以某个node为最小元素的集合就只有一个，
是我理解得有问题么？
【在 l******6 的大作中提到】
: 1. 把 == 关系都元素合并到一个node。否则不能确定无环， 把相等元素归并到一个集
: 合也满足要求
: 2 以 < 和 <= 的关系建立有向图（想不到 a <= b <= c <= a 成环的例子 ， 如果能
: 成环只能取等， 会归到1里面吧）
: 3. topological sort
: 4. 按topological 的顺序做dfs， 访问的点归为一个子集并从图中删除或者标为不可
: 再访问。
|
X****r
发帖数: 3557 | 13 对于所有节点a,b,c，如果a<=b且b<=c则把a和c之间的边去掉。
【在 x***g 的大作中提到】
: 谢谢啊，感觉好像是对的。
: 这句话不太理解，能否展开说说？
: ：然后把原来的有向图里可以被传递律推导出来的边删掉
:
: 有元素，然后把原来的有向图里可
: 65533;1之间的路径，每一条就代表你
|
X****r
发帖数: 3557 | 14 引入它们只是为了叙述简单，实际做的时候直接从没有更大（或更小）元素的元素们开
始找起也是一样的，也不影响算法复杂度。
完全图怎么做？
【在 r****y 的大作中提到】
: 为何需要这两个元素呢？做成完全图不就可以了？
|
