如何编码/探索DAG的多个线性顺序

Question

考虑有向无圈图G(V，E)，其中和E={(1,2)，(1,3)，(1,4)，(2,5)，(3,5)，(4,6)，(5,7)，(6,7)}

​

​

这里的问题是探讨这个图的多个线性顺序。因此，如何对其进行编码/解码，使其始终能得到一个可行的线性序(拓扑序)？

Answer 1

探索DAG不同线性顺序的一种可能方法是定义一个V大小相同的字符串(染色体)，其中字符串的每个元素表示每个顶点的成本，即_i_th顶点的成本由字符串中的_i_th元素给出。

自定义横截图算法可用于解码。每一次访问顶点的次数超过其前辈访问的次数，算法都应该根据字符串提供的代价按升序进行访问。

对于上述DAG和成本字符串{0.6、0.8、0.5、0.1、0.5、0、3、0.9}，得到的线性顺序为{1、4、6、3、2、5、7}。