NP Hardest Longest Path Ациклический модифицированный

Я застрял с этой проблемой на целый день.

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

Итак, мы можем решить эту проблему благодаря топологической сортировке, которая может быть сделана только для ациклических графов. Таким образом, этот тип вопросов может быть решен только для ациклического графа.

введите описание изображения здесь

Итак, мы можем решить эту проблему благодаря топологической сортировке, которая может быть сделана только для ациклических графов. Таким образом, этот тип вопросов может быть решен только для ациклического графа.

Теперь, если я представлю другой случай. Что, если все ребра имеют одинаковый вес и мы не смотрим в цикл графа. Это разрешимо. Каждый раз, когда я думаю об этом, я не вижу никакого смысла в топологической сортировке, если мы можем выбрать любой источник, учитывая, что мы должны выбрать максимальное количество узлов (самый длинный путь).

Это тоже NP Hard или мы можем это решить?

PS: Я прошел через этот самый длинный ациклический путь в ориентированном невзвешенном графе но есть как раз алгоритм для решения задачи о самом длинном пути.


algorithm np np-hard np-complete
person Community    schedule 01.04.2015    source источник

Ответы (1)


arrow_upward
0
arrow_downward

Непонятно, что вы подразумеваете под «не смотреть в цикл», поэтому я предполагаю, что вы имеете в виду, что мы не рассматриваем переход между вершинами в цикле на нашем самом длинном пути. В этом случае вы можете сжать свои циклы в отдельные вершины и использовать описанный выше алгоритм.

person vrume21    schedule 01.04.2015
comment
Да, но в модифицированной версии я не думаю, что вышеуказанный алгоритм работает. Как и вершина, у которой нет входящего ребра. Нам просто нужно пройти через как можно больше вершин, так как все пути имеют одинаковый вес. Я думал о сведении к проблеме гамильтонова графа, но там мы должны выбрать все вершины, а здесь нам просто нужно проверить самый длинный путь, который не проходит принудительно через все вершины. Если хотите, я могу также привести пример по ссылке. - person ; 02.04.2015
comment
Решение динамического программирования для LPP всегда обрабатывает узлы без входящих ребер. Схема алгоритма следующая: для каждого узла n_1, для каждого узла n_2 меньше, чем n_1, рассмотрите пути, включающие n_2 и исключающие n_2. Если какой-то узел n_n не имеет входящих ребер, мы никогда не включим его в потенциально самый длинный путь из внутреннего цикла, но мы включим его во внешний. Это имеет смысл, потому что n_n всегда будет корнем любого пути, включая его. - person vrume21; 02.04.2015
comment
Проверьте эту ссылку. Здесь Адитья Дипак дал решение, я не пробовал, но он выглядит вполне осуществимым. Каково ваше мнение по этому поводу? quora.com/ - person ; 02.04.2015
comment
Это очень сложно читать и понимать. Воспользуйтесь этой ссылкой: cs.berkeley.edu/~vazirani/algorithms/chap6. pdf. Они решают вашу проблему и выдают псевдокод. - person vrume21; 02.04.2015