algorithm - 一个poset的一个元素的概率是最大的？

Question

给定一个部分有序的集合（poset），假设所有线性扩展的可能性相同，估计一个元素在线性扩展中最高的概率的算法是什么？

Answer 1

近似计数似乎比近似采样慢，因此您的算法应该简单地基于拒绝采样：从所有线性扩展的集合中重复选择（近似）随机样本，并直接计算您的元素最高的那些比例。

挑选每个随机样本当然可以在 O(n^3 log n) 中完成，因此根据您需要的准确度，它最终会比您引用的 O(n^6) 更快。

Answer 2

For each item in the poset:
    Remove the item from the poset
    Count the number of linear extensions of the remaining items
Normalize the counts
You have the distribution!

但是，计算线性扩展的数量是#P-complete，所以这非常慢。最后，只有计数的比例很重要，所以也许有更有效的算法？

有用于计算可以插入的线性扩展的近似算法，但我想知道是否有更具体的算法可以得到正确的答案。