Алгоритм Christofides для ориентированного графа
Можно ли реализовать алгоритм Christofides для ориентированного графа?
Предположим, у вас есть неориентированный граф, в котором каждая вершина имеет ребра в обоих направлениях относительно друг друга в графе (не в себе). Но веса ребер не обязательно должны быть одинаковыми в обоих отношениях (несимметрично).
Например, вы думаете о карте улиц, в которой много улиц с односторонним движением.
Теперь мы хотим найти приближение для путешествия коммивояжера по всем вершинам.
Прежде всего, алгоритм Christoffides не определен для такого TSP, потому что Минимальное связующее дерево не определено для ориентированного графа.
Но все же мы начинаем алгоритм, находя оптимальное ветвление с алгоритмом Эдмондса до начальной точки тура как корня.
Затем мы находим минимальное идеальное соответствие для ветвления, так что оно становится эйлеровым графом. Это произойдет с венгерским алгоритмом, который найдет минимальное совпадение, чтобы каждая вершина в ветвлении имела послесловия с одинаковым количеством ребер, входящих в выход.
На последнем этапе мы находим тур Эйлера и оптимизируем его, используя ярлыки.
У меня есть вопросы:
- Это способ, которым я хочу реализовать алгоритм правильно, или я сделал ошибку, и он не может работать
- Если это работает, это все еще ограничено в 1,5 оптимального решения для чайной ложки?