Как кодировать / исследовать несколько линейных порядков DAG

Question

Рассмотрим направленный ациклический граф G (V, E) , где V = {1,2,3,4,5,6,7} и E = {(1,2), (1,3), (1,4), (2,5), (3,5), (4,6), (5,7), (6,7)}

Задача здесь состоит в том, чтобы исследовать множественные линейные упорядочения графа. Следовательно, как кодировать / декодировать его так, чтобы оно всегда приводило к выполнимому линейному упорядочению графа (топологическому порядку)?

Answer 1

Одним из возможных способов изучения различных линейных порядков DAG может быть определение строки (хромосомы) с одинаковым размером V , где каждый элемент строки обозначает стоимость для каждой вершины, т.е. стоимость i -ой вершины задается i -ым элементом в строке.

Для декодирования можно использовать собственный алгоритм трансверсального графа. Каждый раз, когда можно найти больше, чем на вершине со всеми посещенными предшественниками, алгоритм должен затем посещать в порядке возрастания, основываясь на стоимости, указанной в строке.

Для приведенной выше DAG и строки затрат {0,6, 0,8, 0,5, 0,1, 0,5, 0,3, 0,9} полученный линейный порядок будет равен {1, 4, 6, 3, 2, 5, 7 }.