问题标签 [poset]

我在尝试分类算法时遇到了以下算法问题。元素被分类为多层次结构，我理解为具有单个根的poset。我必须解决以下问题，这看起来很像set cover problem。

我在这里上传了我的乳胶问题描述。

设计一个满足 1 和 2 的近似算法非常容易，只需从 G 的顶点开始并“向上”或从根开始并“向下”。假设您从根开始，迭代地扩展顶点，然后删除不必要的顶点，直到您至少有 k 个子格。近似界取决于顶点的子节点数，这对我的应用程序来说是可以的。

有谁知道这个问题是否有正确的名称，或者问题的树版本？我很想知道这个问题是否是 NP 难的，也许有人对一个好的 NP 难问题有想法来减少或有一个多项式算法来解决这个问题。如果你有两个收集你的百万美元的价格。;)

那里有大量的排序算法，但它们中的大多数只适用于完全有序的集合，因为它们假设任何两个元素都是可比的。但是，有没有什么好的算法可以对一些元素进行排序，其中一些元素是无法比较的？也就是说，给定一组 S 元素从一个偏序中抽取，如果 x _i ≤ x _{j ， i ≤ j，输出一个排序 x 1} , x ₂ , ..., x _n的最佳方法是什么？

我有一些元素数量可变的列表。每个列表都已排序，但排序算法未知。我想将列表合并成一个大列表，其中包含所有列表的顺序相同，没有重复。

示例输入：

1. XS,M,L,XL
2. S,M,XXL
3. XXS,XS,S,L

预期结果：

• XXS,XS,S,M,L,XL,XXL

预期的结果是通过匹配输入序列来获得一个合并的结果，该结果包含每个输入序列的元素以正确的顺序排列，如下所示：

如果存在位置不明确的元素，该函数应通知。在这里，它将是 XXL（它可以留在 M、L 或 XL 之后），我需要在 XL 之后手动指定它的位置（因为在这里我知道排序算法并且可以提供帮助）。我考虑过定义每两个元素的对，每对按原始列表中的顺序排列。从这个可以建立完整的列表。

归纳证明。非空有限集上的每个偏序至少有一个最小元素。

我该如何 解决这个问题？

我正在根据 SQLAlchemy 实现一个具有Partially Ordered Set数学特征的结构，我需要能够一次添加和删除一个边。

在我目前最好的设计中，我使用了两个邻接列表，一个是分配列表（大约是哈斯图中的边），因为我需要保留哪些节点对被显式设置为有序，另一个邻接列表是传递的关闭第一个，以便我可以有效地查询一个节点是否相对于另一个节点排序。现在，每次在分配邻接列表中添加或删除边时，我都会重新计算传递闭包。

它看起来像这样：

其中floyd_warshall()是同名算法的实现。

这导致我遇到两个问题。首先是它似乎效率不高，但我不确定我可以使用哪种算法。

第二个更多是关于Node.recompute_ancestry()每次分配发生时必须显式调用的实用性，并且只有在分配被刷新到会话中并且具有正确的连接之后。如果我想看到 ORM 中反映的更改，我必须再次刷新会话。我想，如果我能用 orm 来表达重新计算祖先的操作，那会容易得多。

我正在寻找在java中模拟一个名为x的poset，其大小为2n，形式为a_1 < a_2 < ... < a_n，并且b_1 < b_2 < ... < b_n。

我想运行一次迭代以获得随机线性扩展，从而比较每个对象的“大小”，如果可以切换两个相邻的位置，我会这样做，如果不能，那么我坚持，以新的顺序结束。例如 x[i] = a_k 和 x[i+1] = b_k 我切换它们，但是如果 x[i] = a_k 和 x[i+1] = a_(k+1) 我不会。（本质上这是 Karzanov Khachiyan 链）。

我最初想使用一个数组数组，其中 x[][] = {a_1[], ..., b_1[], ... }，比如 a_1 = {a,1}，我可以在其中比较值并轻松进行切换。现在我正在尝试考虑其他方法来做到这一点，因为从我之前的问题中我可以看出这不会是一种特别有效或优雅的方式。有没有人有什么建议？

我把这个作为算法决赛的最后一个问题（现已完成）：

给定一组 (x,y) 点P，让M(P)是给定 P 上的以下偏序的最大点集：

因此：

给出计算 M(P) 的算法，时间复杂度为 O(nh)、O(n log n) 和 O(n log h)（其中 n = |P| 和 h=|M(P)|）

我的 O(nh) 算法：

我的 O(n log n) 算法：

什么是 O(n log h) 算法？
我的直觉是它是对第一个算法的修改，但使用了一些不需要扫描每个点的巧妙数据结构（可能是对二叉树的修改）。

有没有这样的算法用于一般的poset？
这将在给定顶点列表和恒定时间查找两个给定顶点之间是否存在有向路径的情况下找到任何有向树的叶子。

我正在创建一个偏序集作为 java 中的抽象数据类型，我必须制作数字集的迭代器版本，以及关系的迭代器。现在对于元素，我使用了整数的 HashSet，对于关系，我使用了对的 ArrayList（对是我创建的一个类，它采用 2 个整数作为参数，基本上类似于 (x, y)）。我需要创建 2 个迭代器，一个用于 s，一个用于 r，但它们必须遵循一定的顺序，1. 如果 (x, y) 属于R，那么 s 的迭代器应该在返回 y 之前返回 x 2. 如果(x, y) 和 (y, z) 属于R，那么 r 的迭代器应该在返回 (y, z) 之前返回 (x, y)

我做了一个辅助方法，首先检查集合中的元素 n 是否是一对中的第一个元素，然后返回它，但我似乎无法检查它是否是第二个元素，我该如何检查第一个元素如果它被退回或没有？

这是我的代码：

我真的很感激任何形式的帮助，或在这段代码中提示。谢谢

编辑：

好的，在添加一个包含返回元素的新集合后，我已经编写了代码，这就是我写的：

这段代码正确吗？另外，eclipse似乎给了我一个错误，告诉我我需要在循环外返回一个值，但是我已经在每种情况下都返回了内部，为什么还需要更多？感谢帮助

我编写了一个自定义迭代器类，它迭代在 PoSet 中找到的一组数字，这是我的代码：

问题是在返回一个数字时，我应该遵守偏序规则，即： 1. 如果 (x, y) 属于R，那么 x 应该在 y 之前返回

但是，上面的代码似乎遵循该顺序，但它正在创建重复项，如何修复我的代码以不允许它？

注意：在我的代码中，S 是 PoSet 中的一组数字，它是一个 HashSet，R 是一个配对数组列表（配对：我创建的一个以 2 个整数作为参数的类）来保存 PoSet 中的关系。

有没有办法解决这个问题？谢谢

问题如下：给定一个poset的子集S，找到S的最大元素。

例如，考虑http://ndp.jct.ac.il/tutorials/Discrete/node34.html中的poset 的哈斯图。给定它的一个子集，例如：{12, 2, 8}，最大元素是 12 和 8。

我不知道我是否准确地描述了这个问题。我认为这个问题可能涉及传递闭包的一些排序或计算，但我有点困惑。

你能给我一些快速算法的方法吗？我想把它保存在 O(n^2)

谢谢。

一点澄清。我的应用程序正在使用 RDF 图。如果存在表示 < 关系的特定边，则两个节点是可比较的。如果存在这样的显式关系或隐式传递关系，则两个节点可能是可比较的。

所以假设哈斯图正是我的RDF图。如果我从 2 开始进行深度优先搜索，我怎么知道 8 和 12 不可比较？它们可能不是显式的，但可能是隐式的。