У меня есть бинарная матрица смежности ориентированного графа. Теперь я хочу изменить порядок так, чтобы количество элементов над диагональю, а также их расстояние до диагонали было минимальным.
Чтобы дать вам справочную информацию: я работаю с матрицей структуры проекта на основе задач.
Например, у меня есть три задачи, A, B, C. Это означает, что у меня есть строки A, B, C и, соответственно, столбцы A, B, C. Теперь, если задача B требует Ввод от задачи A, элемент (b , а) равен единице, в противном случае он равен нулю.
Порядок задач показывает последовательность, в которой задачи выполняются.
Таким образом, если задание ввода A выполнено до того, как задание B потребуется для ввода, оно находится ниже диагонали. Если они находятся выше диагонали (например, если A зависит от ввода B), это означает, что в будущем будут сгенерированы входные данные, что плохо.
Чтобы оптимизировать последовательность задач, матрица должна представлять собой нижнюю двуугольную матрицу, чтобы входные данные генерировались до того, как они понадобятся. Поскольку это обычно невозможно, оптимальным является уменьшение числа из них над диагональю, а также уменьшение расстояния до диагонали.
При переупорядочении матрицы проблема состоит в том, что порядок строк и столбцов должен оставаться неизменным. Поэтому, если я переместу строку A на одну строку ниже, мне автоматически нужно переместить столбец A на один столбец влево.
Ну, я гуглил и нашел алгоритм Кутхилла-Макки, но он работает только для симметричных матриц, и, поскольку у меня есть ориентированный граф, моя матрица асимметрична с возможными симметричными элементами.
Кроме того, алгоритм Рейда-Скотта просто уменьшает общую ширину полосы и, следовательно, имеет ненужное ограничение более низкой полосы пропускания.
В основном я ищу алгоритм, просто минимизирующий верхнюю ширину полосы, так как все записи ниже диагонали не имеют значения.
Я надеюсь, что мог бы сформулировать свой вопрос всесторонне. Я не знаком с теорией графов и не изучал математику или информатику, поэтому дружеский совет был бы полезен.
Большое спасибо!