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 的大作中提到】 : 为何需要这两个元素呢?做成完全图不就可以了?
|