Уважаемые!

Прошу помочь в такой проблеме:
Имеется ориентированный граф, в котором возможны циклы. В нем необходимо найти длиннейший (критический) путь из начальной вершины в конечную. Все дуги однонаправленны. Путь 100% существует (особенность графа).
Граф представлен в виде матрицы m x m типа(как пример):

{
{-Inf, 0,-Inf, -Inf, 0, -Inf, -Inf, 0, -Inf, -Inf, -Inf},
{-Inf, -Inf,10, -Inf, -Inf, -Inf, -Inf, -Inf,10, -Inf, -Inf},
{-Inf, -Inf,-Inf, 8,8, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf},
{-Inf, -Inf,-Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, 4, 4},
{-Inf, -Inf,-Inf, -Inf, -Inf, 5, -Inf, -Inf, -Inf, -Inf, -Inf},
{-Inf, -Inf,-Inf, -Inf, -Inf, -Inf, 5, -Inf, -Inf, -Inf, -Inf},
{-Inf,6,-Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, 6},
{-Inf, -Inf,4, -Inf, -Inf, -Inf, -Inf, -Inf, 4, -Inf, -Inf},
{-Inf, -Inf,-Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, 7, -Inf},
{-Inf, -Inf,-Inf, -Inf, -Inf,3, -Inf, -Inf, -Inf, -Inf, 3},
{-Inf, -Inf,-Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf, -Inf}}

Вышеприведенный пример представляет собой ориентированный граф, внутри которого есть циклы (цикл путь: 2-3-5-6-7-2). Поэтому стандартный алгоритм нахождения критического пути не работает(также как и топологическая сортировка). Необходимо сделать так чтобы он искал длиннейший путь, при это не заходя в уже посещенные вершины. Вот как выглядит данный граф:

Здравствуйте, Darsufa, Вы писали:

Задача NP-трудная. Можно поискать по ключевым словам: longest directed path problem.

Ничего не нашел..именно в такой постановке задачи..

Mab>Здравствуйте, Darsufa, Вы писали:

Mab>Задача NP-трудная. Можно поискать по ключевым словам: longest directed path problem.

Здравствуйте, Darsufa, Вы писали:

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

Само по себе наличие контуров в графе ещё не говорит о том, что стандартные алгоритмы не работают. Вообще, там можно сделать коорекцию весов дуг, так что стандартные алгоритмы будут работать. Как я не очень в курсе... но это стандартно

Можно попробовать такой алгоритм

Функция(Вершина)
Для всех связанных вершин
Если в этой вершине стоит отметка о длине пути из начальной вершины в связанную и путь больше — ничего не делать (continue)
Если в этой вершине отметке сопоставлена та же дуга, что и просматриваемая — continue
Если в этой вершине нет отметки или она меньше — проставить новую отметку, равную отметке в Вершина + длина дуги просматриваемой связи. В отметке так же ставится указание на связь, по которой пришёл алгоритм.
Для вершин с изменённой отметкой (или установленной в первый раз) — вызвать Функция(Связанная вершина)

Здравствуйте, FDSC, Вы писали:

Алгоритм, который я привёл может не работать, нужно сделать примерно так

Для начальной вершины вызывается Функция(Начальная вершина, null)

FDS>Функция(Вершина, Путь)
FDS>Для всех связанных вершин
FDS> Если связанная вершина уже есть в пути — ничего не делать
FDS> Если в этой вершине стоит отметка о длине пути из начальной вершины в связанную и путь длиннее — ничего не делать (continue)
FDS> Если в этой вершине нет отметки или она меньше — проставить новую отметку, равную отметке в Вершина + длина дуги просматриваемой связи
FDS> Для вершин с изменённой отметкой (или установленной в первый раз) — вызвать Функция(Связанная вершина, Путь+Связанная Вершина)

или

FDS>Функция(Вершина)
FDS>Для всех связанных вершин
FDS> Если связанная вершина уже есть в пути, сопоставленном вершине — ontinue
FDS> Если в этой вершине стоит отметка о длине пути из начальной вершины в связанную и путь длиннее — ничего не делать (continue)
FDS> Если в этой вершине нет отметки или она меньше — проставить новую отметку, равную отметке в Вершина + длина дуги просматриваемой связи. Записать в связанную вершину путь = путь, сопоставленный Вершине + Вершина
FDS> Для вершин с изменённой отметкой (или установленной в первый раз) — вызвать Функция(Связанная вершина)

Здравствуйте, FDSC, Вы писали:


FDS>Само по себе наличие контуров в графе ещё не говорит о том, что стандартные алгоритмы не работают. Вообще, там можно сделать коорекцию весов дуг, так что стандартные алгоритмы будут работать. Как я не очень в курсе... но это стандартно
И чего же, после этого мы научимся решать NP-трудную задачу?

Здравствуйте, Mab, Вы писали:


FDS>>Само по себе наличие контуров в графе ещё не говорит о том, что стандартные алгоритмы не работают. Вообще, там можно сделать коорекцию весов дуг, так что стандартные алгоритмы будут работать. Как я не очень в курсе... но это стандартно
Mab>И чего же, после этого мы научимся решать NP-трудную задачу?
А что, NP — трудные задачи уже неразрешимы?

Здравствуйте, vvotan, Вы писали:

V>Здравствуйте, Mab, Вы писали:


FDS>>>Само по себе наличие контуров в графе ещё не говорит о том, что стандартные алгоритмы не работают. Вообще, там можно сделать коорекцию весов дуг, так что стандартные алгоритмы будут работать. Как я не очень в курсе... но это стандартно
Mab>>И чего же, после этого мы научимся решать NP-трудную задачу?
V>А что, NP — трудные задачи уже неразрешимы?
Разрешимы-то разрешимы, да вот только загадочные "стандартные алгоритмы" работают за полином (или какие тогда имеются в виду? backtracking?). Или может у тебя редукция неполиномиальная?

Здравствуйте, Mab, Вы писали:

Mab>Здравствуйте, vvotan, Вы писали:

V>>Здравствуйте, Mab, Вы писали:


FDS>>>>Само по себе наличие контуров в графе ещё не говорит о том, что стандартные алгоритмы не работают. Вообще, там можно сделать коорекцию весов дуг, так что стандартные алгоритмы будут работать. Как я не очень в курсе... но это стандартно
Mab>>>И чего же, после этого мы научимся решать NP-трудную задачу?
V>>А что, NP — трудные задачи уже неразрешимы?
Mab>Разрешимы-то разрешимы, да вот только загадочные "стандартные алгоритмы" работают за полином (или какие тогда имеются в виду? backtracking?). Или может у тебя редукция неполиномиальная?

Простите, и чем вам не нравится, что она NP-полная? Это ещё не значит, что её нельзя решить за полиномиальное время. А это не так долго.

Здравствуйте, FDSC, Вы писали:

FDS>Простите, и чем вам не нравится, что она NP-полная? Это ещё не значит, что её нельзя решить за полиномиальное время.
Вообще-то математики верят, что как раз значит. А что, уже есть контрпример?

Здравствуйте, Mab, Вы писали:

Mab>Здравствуйте, FDSC, Вы писали:

FDS>>Простите, и чем вам не нравится, что она NP-полная? Это ещё не значит, что её нельзя решить за полиномиальное время.
Mab>Вообще-то математики верят, что как раз значит. А что, уже есть контрпример?
Да, в смысле, я чушь сказал... Если бы был контрпример — было бы круто.

А с чего вы взяли, что она NP-полная?

Здравствуйте, FDSC, Вы писали:

FDS>А с чего вы взяли, что она NP-полная?
Ну вроде сразу ясно. Например, к ней гамильтонов путь сводится.

Здравствуйте, Mab, Вы писали:

Mab>Здравствуйте, FDSC, Вы писали:

FDS>>А с чего вы взяли, что она NP-полная?
Mab>Ну вроде сразу ясно. Например, к ней гамильтонов путь сводится.

Прошу помочь в такой проблеме:
Имеется ориентированный граф, в котором возможны циклы. В нем необходимо найти длиннейший (критический) путь из начальной вершины в конечную. Все дуги однонаправленны. Путь 100% существует (особенность графа).

Длиннейший путь сводится к задаче нахождения кратчайшего пути. Необходимо найти самый длинный из возможных путей от a к b, но он может быть и не Гамильтонов, насколько я понимаю, так что задача P-полная

Здравствуйте, FDSC, Вы писали:

FDS>Прошу помочь в такой проблеме:
FDS>Имеется ориентированный граф, в котором возможны циклы. В нем необходимо найти длиннейший (критический) путь из начальной вершины в конечную. Все дуги однонаправленны. Путь 100% существует (о,собенность графа).
Там еще дальше написано:

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

Говоря русским языком -- мы ищем простой путь.

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

FDS>Необходимо найти самый длинный из возможных путей от a к b, но он может быть и не Гамильтонов
Конечно может и не быть. Но вот если длиннейший из простых a-b путей не гамильтонов (а значит не проходит через все вершины), то гамильтоновых путей в графе вовсе нет. Это, собственно, и есть сведение.

FDS>насколько я понимаю, так что задача P-полная
P-полная? Вообще любой нетривиальный язык из P является полным в смысле сводимости по Карпу, только это тривиально совсем

Здравствуйте, Darsufa, Вы писали:

D>Уважаемые!

D>Прошу помочь в такой проблеме:
D>Имеется ориентированный граф, в котором возможны циклы. В нем необходимо найти длиннейший (критический) путь из начальной вершины в конечную. Все дуги однонаправленны. Путь 100% существует (особенность графа).
А применика ты алгоритм Дейкстры, только вместо минимума вычисляй максимум...

Здравствуйте, Mab, Вы писали:

Mab>Здравствуйте, FDSC, Вы писали:

FDS>>Прошу помочь в такой проблеме:
FDS>>Имеется ориентированный граф, в котором возможны циклы. В нем необходимо найти длиннейший (критический) путь из начальной вершины в конечную. Все дуги однонаправленны. Путь 100% существует (о,собенность графа).
Mab>Там еще дальше написано:
Mab>
Mab>Необходимо сделать так чтобы он искал длиннейший путь, при это не заходя в уже посещенные вершины.
Mab>
Mab>Говоря русским языком -- мы ищем простой путь.

FDS>>Длиннейший путь сводится к задаче нахождения кратчайшего пути.
Mab>Ну да, только вот функция длин станет неконсервативной, а ищем-то мы простой путь. Так что не понимаю, кому и как поможет это соображение.

только вот функция длин станет неконсервативной

Это как, простите, и с какой стати?

Здравствуйте, LaptevVV, Вы писали:

LVV>Здравствуйте, Darsufa, Вы писали:

D>>Уважаемые!

D>>Прошу помочь в такой проблеме:
D>>Имеется ориентированный граф, в котором возможны циклы. В нем необходимо найти длиннейший (критический) путь из начальной вершины в конечную. Все дуги однонаправленны. Путь 100% существует (особенность графа).
LVV>А применика ты алгоритм Дейкстры, только вместо минимума вычисляй максимум...

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

Здравствуйте, FDSC, Вы писали:

FDS>только вот функция длин станет неконсервативной
Консервативность -- это по определению отсутствие отрицательных циклов. У нас задача про длиннейший путь, поэтому все длины равны -1. Так что любой цикл в графе для нас плох.

Здравствуйте, Mab, Вы писали:

Mab>Здравствуйте, FDSC, Вы писали:

FDS>>только вот функция длин станет неконсервативной
Mab>Консервативность -- это по определению отсутствие отрицательных циклов. У нас задача про длиннейший путь, поэтому все длины равны -1. Так что любой цикл в графе для нас плох.

Почему все длины равны -1? Если бы у нас был бесконтурный граф, мы бы могли найти соотв. путь за полиномиальное вермя, домножив все веса дуг на -1 и применив стандартный алгоритм нахождения кратчайшего пути.
Если он у нас с контурами — нужно в алгоритме просто ставить предохранитель против нахождения циклов и зацикливания

Здравствуйте, FDSC, Вы писали:

Честно говоря, надоело спорить, т.к. я уже не понимаю, о чем именно спор

FDS>Почему все длины равны -1?
Ну потому, что так мне кажется резонно сводить задачу о длиннейшем пути к задаче о кратчайшем. Есть другие варианты сведения?

FDS>Если он у нас с контурами — нужно в алгоритме просто ставить предохранитель против нахождения циклов и зацикливания
Не знаю, что тут имеется в виду под "предохранителем". Это будет разновидность backtracking-а такая?