百科问答小站 logo
百科问答小站 font logo



如何统计拓扑排序的个数? 第1页

  

user avatar    网友的相关建议: 
      

DAG中的topological sort个数等价于统计一个partially ordered set上linear extension的个数,后面这个问题已知是#P-complete的,所以目前还没有polynomial-time的做法


user avatar   feng-kuang-shen-shi-92 网友的相关建议: 
      

看到本问题下面的一个非常惊艳的匿名回答。

好久没看到了。

DAG中的拓扑排序的个数等价于统计一个偏序集合上线性组合的个数。

而求这个线性组合的后面这个问题已经有人证明了是P完全问题。

NP问题就不解释了。

现在举例子来解释。

1、存在回路如何进行拓扑排序

跟书上说的不同,存在回路的连通有向图是可以排序的。方法就是缩点。即把回路当成一个要素(结点)来处理。

上面是缩点的示意,就不再解释。

2、对抗解释结构模型(AISM)

上面是文科生经常用到的一个研究方法。流程如下:

上面是另外一种计算方法。计算流程如下:

3、哈斯图与偏序与对抗层级拓扑图

最终求出的对抗层级拓扑图就是一种拓扑排序

上面就是哈斯图,又叫对抗哈斯图,也叫对抗层级拓扑图。

任何一边的图,从上到小一个个数下来就是一个拓扑序。

按理只数个数这不是一个P完全问题。

根据每一层的组合情况可以直接得出。

但是观察右边的F5,它可以跟F6同一层。

而且转化成线性列的时候,要去重,这就蛋疼了。

如果碰巧是刚性系统,即没有活动要素的时候。

只算个数就很容易。

比如上面这种没有跃迁要素的。

也就是两边是一样的。

那好办,直接算组合就出来了。是一个多项式的解。


user avatar   sd0061 网友的相关建议: 
      

应该只有指数级做法,状态压缩动态规划可以做到 O((n+m)2^n),n为总点数m为总边数。




  

相关话题

  从一读到一亿需要读多少个汉字? 
  在一段高速公路上,30分钟之内见到汽车经过的概率是95%,那么,在10分钟内见到汽车经过的概率是多少? 
  我发现设计模式一个很奇妙的情况,不知各位知友遇过没? 
  C++中开多个数组和用struct封装起来哪个速度更快? 
  要是往马斯克嵌在猪脑袋里面的芯片里写进去“猪的生命也是命”。猪会不会不让人类吃他们的肉了呢? ​​​? 
  带一堆指针的链式结构怎么写才好? 
  算法书如何选择? 
  感觉算法在程序员中快被吹上天了,如果只是搞编程的话,是不是没必要死磕算法? 
  五个囚犯先后从100颗绿豆中抓绿豆。抓得最多和最少的人将被处死,不能交流,可以摸出剩下绿豆的数量,谁的存活几率最大? 
  如何理解动态规划? 

前一个讨论
能解释下怎么从这个有向图生成如图的集合链?(数字电路并行全入度拓扑排序优化算法)?
下一个讨论
哪位大神能通俗的解释下拓扑不变量是什么?灰常感谢~





© 2024-11-21 - tinynew.org. All Rights Reserved.
© 2024-11-21 - tinynew.org. 保留所有权利