С учетом partially-ordered set (poset), что такое алгоритм оценки вероятности того, что элемент является самым большим в линейном расширении, если предположить, что все линейные расширения одинаково вероятны?Вероятность того, что элемент poset является максимальным?
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, поэтому это очень медленно. В конце концов, имеет значение только доля отсчетов, так что, возможно, существует более эффективный алгоритм?
Есть алгоритмы аппроксимации для подсчета линейных расширений, которые могут быть подключены, но мне интересно, существует ли более конкретный алгоритм для получения права на ответ.
Если память служит, это проблема с # P-hard. Ваш позит не будет серийно-параллельным, не так ли? –
К сожалению, нет, хотя я рассматриваю способы сделать это так. :) Согласно моим исследованиям до сих пор, говорить что-нибудь полезное о целом или о конкретном элементе является # P-hard, а приближения, как правило, O (n^6) и изменения, но мне было любопытно, может ли эта проблема что-либо дать лучше. – alltom