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

Ну, я сталкиваюсь с проблемой с небольшой работой, которая у меня сейчас в руках …

Основная цель состоит в том, чтобы, имея заданный граф (без весов и направленный), я должен обнаружить группу путей (если возможно, только один путь, но их может быть больше) с минимальной общей длиной, охватывающей все ребра.
Другое «ограничение» заключается в том, что граф является DFA, поэтому пути должны начинаться в начальном состоянии и заканчиваться в состоянии принятия (они отмечены).

Изначально я обнаружил, что это похоже на проблему китайского почтальона, и на самом деле это так. Но в моем случае график направлен (я считаю, что это немного меняет дело), ​​и нет никаких проблем в обработке ребра более одного раза, поскольку результирующий путь остается самым коротким.

Я прочитал кое-что о путях Эйлера и T-Joins, и это, вероятно, решение моей проблемы. Если я правильно понял, что мне нужно сделать, это найти путь Эйлера в моем графе и, если его нет, создать его, дублировать Т-соединения или что-то в этом роде … У меня было много проблем понимая это, я даже не знаю, является ли это ответом на мою проблему … (самый короткий и понятный текст, который я нашел здесь: http://en.wikipedia.org/wiki/Route_inspection_problem)

Просто чтобы оставить короткий пример, учитывая этот график (1 является начальным и 5 является принятие):

1 -> 2;
2 -> 3;
2 -> 4;
4 -> 5;

Ответ на мою проблему должен быть: 1 -> 2 -> 4 -> 5 и 1 -> 2 -> 3.
(В этом случае мне также пришлось бы учитывать тот факт, что 3 не является состоянием принятия, но этот край должен был быть покрыт. Но я легко могу пройти через это, отметив все состояния без ребер для других узлов как состояния приема ).

Надеюсь, я все объяснил достаточно хорошо.

Заранее спасибо!

2

Решение

Задача ещё не решена.

Другие решения


По вопросам рекламы [email protected]