Задача такая:
Задана система двусторонних дорог. Найти замкнутый путь длиной не более T,
проходящий через каждую дорогу ровно один раз.
Вопрос: подойдет ли здесь волновой алгоритм, который применяется для
каждой вершины и в котором эта вершина является начальной и конечной.
Или же существует более подходящий алгоритм.
Алгоритм, опубликованный здесь Кодтом, уже был мною найден.
Здравствуйте, northwind, Вы писали:
N>Задача такая:
N>Задана система двусторонних дорог. Найти замкнутый путь длиной не более T,
N>проходящий через каждую дорогу ровно один раз.
Ограничение "не более T" лишнее — длина эйлерова цикла равна суммарной длине все ребер (т.е. константа для данного графа).
N>Вопрос: подойдет ли здесь волновой алгоритм, который применяется для
N>каждой вершины и в котором эта вершина является начальной и конечной.
N>Или же существует более подходящий алгоритм.
N>Алгоритм, опубликованный здесь Кодтом, уже был мною найден.
Волновой арлгоритм не подойдет (он никак не учитывает требования пройти по каждому ребру).
Нужен такой алгоритм: выходим из произвольной вершины и движемся, стирая за собой ребра. При этом по мосту (ребру, при удалении которого нарушается связность графа) движемся только в том случае, когда других вариантов нет.
Если в конце концов удалили все ребра — значит, нашли эйлеров цикл.
Здравствуйте, northwind, Вы писали:
N>Задана система двусторонних дорог. Найти замкнутый путь длиной не более T,
Почему не более Т, если ищем Эйлеров цикл?!
N>Или же существует более подходящий алгоритм.
Посмотреть можно на любом сайте олимпиадчиков.
... << Rsdn@Home 1.1.4 beta 1>>
Перекуём баги на фичи!
