Спасибо большое за ответы в предыдущем посте, но к сожалению, решение так и не найдено..а очень надо..
Поэтому выкладываю еще раз с некоторыми дополнительными комментариями, которые может быть могут помочь:
Прошу помочь в такой проблеме:
Имеется ориентированный граф, в котором возможны циклы. В нем необходимо найти длиннейший (критический) путь из начальной вершины в конечную. Все дуги однонаправленны. Путь 100% существует (особенность графа).
Граф представлен в виде матрицы m x m типа(как пример):
Вышеприведенный пример представляет собой ориентированный граф, внутри которого есть циклы (цикл путь: 2-3-5-6-7-2). Поэтому стандартный алгоритм нахождения критического пути не работает(также как и топологическая сортировка). Необходимо сделать так чтобы он искал длиннейший путь, при это не заходя в уже посещенные вершины. Вот как выглядит данный граф (дуги взвешенные и имеют разные значения!!):
Хочу немного уточнить про особенность графа:
Начальный граф всегда имеет такой вид:
Т.е. есть начальная вершина и есть m множеств путей(в данном примере 3, это пути 1-2-3-4-11, 1-5-6-7-11 и 1-8-9-10-11), которые состоят каждая из m вершин. В этом графе легко найти длиннейший путь — это длина длиннейшего пути (какогото из m).
Но в процессе работы начальный граф видоизменяется и, соответственно, принимает, к примеру, такой вид(все дуги взвешенные):
Изменения происходят следующие(причем в процессе работы разными способами делаются изменения в начальном графе и для каждого необходимо считать длиннейший путь из 1 в 11):
В каждом пути выбирается по одной вершине и между ними проводятся дуги, так что они образуют пути из m-1 дуг между собой(в данном примере это соответственно 9-2-7, 8-3-5, 4-10-6). После этих преобразований соответственно граф принимает вышеприведенный вид, что все-таки отличает его от произвольного ографа. Может это как-то может облегчить задачу нахождения длиннейшего пути из 1 в 11 вершину. Контуры возникают не всегда, но тем не менее могут возникать...
Спасибо за все предыдущие ответы! Но пока решения к сожалению не вижу
Вот код на C++, но он работает только для бесконтурных графов и использует топологическую сортировку(не работает с циклами) и алгоритм Флойда, адаптированный под нахождение длиннейшего пути..но повторюсь..код не работает с циклами...:
void Topological_Sort () //Процедура топологической сортировки
{
int Children[n];
int index=n-1;
{for (int v=0; v<n; v++) Children[v]=0;}
{for (int v=0; v<n; v++)
for (int v2=0; v2<n; v2++)
if (graph[v][v2]!=Inf && v2!=v) Children[v]++;}
bool found;
do {
found=false;
for (int v=0; v<n; v++)
if (!Children[v]) {
for (int p=0; p<n; p++) if (graph[p][v]!=Inf) Children[p]--;
Children[v]=1;
Order[index--]=v;
found=true;
break;
}
} while (found);
}
int dist(int s, int d) //Процедура для подсчета длины длиннейшего пути в графе
//Мы принимаем, что есть только одна начальная и одна конечная вершина, и нам необходимо найти длиннейший путь
{
//1 - Делаем топологическую сортировку множества вершин: V->Order[]
Topological_Sort();
//Первая будет все время в Order[0], тогда как последняя в Order[n-1]
//2 - Используем технику динамического программирования
// Rule: Dist[d]=max{Dist[v]+graph[v][d], (v,d) in E}
int Dist[n];
int v;
{for (int v=0; v<n; v++) Dist[v]=graph[s][v];}
Dist[s]=0;
for (int i=0; i<n; i++) {
v=Order[i];
for (int pred=0; pred<n; pred++) if (graph[pred][v]!=Inf)
if (Dist[pred]+graph[pred][v]>Dist[v]) Dist[v]=Dist[pred]+graph[pred][v];
}
return Dist[d]; //Возвращаем последнею величину v (=Order[n-1])
}
P.S. Мне очень нужен этот алгоритм! Помогите плиз!!!
......
D>P.S. Мне очень нужен этот алгоритм! Помогите плиз!!!
Не знаю, почему не ответили раньше, но все очень просто — для того, чтобы применять алгоритмы Флойда или Дийкстры для графов с циклами, достаточно эти циклы исключить. Цикл в ориентированном графе называется сильной компонентой, смысл предобработки заключается в том, чтобы собрать все узлы, входящие в сильные компоненты, в одну вершину, а при получении максимального (минимального) пути по агрегированному графу, сделать то же самое для конкретной сильной компоненты, через которую проходит путь.
Здравствуйте, Vintik_69, Вы писали:
V_>Здравствуйте, Grey2002, Вы писали:
G>>сделать то же самое для конкретной сильной компоненты, через которую проходит путь.
V_>Что тоже самое-то?
То же самое — это найти кратчайший путь между вершинами внутри сильной компоненты.
Это не так сложно — для таких вычислений можно виртуально разрывать цикл. Вообще есть куча алгоритмов на графах — смотрите alglib и algolist. Я делал подобную вещь когда-то по учебнику дискретки — ничего сложного зедсь нет. Хотя — если будут вопросы — отвечу.
Я давал там алгоритм, он должен работать (если ничего не найдёшь другого). Попробуй, если ничего другого не найдётся.
(Споры были только по тому, за сколько эту задачу можно решить.)
Здравствуйте, Grey2002, Вы писали:
G>Здравствуйте, Vintik_69, Вы писали:
V_>>Здравствуйте, Grey2002, Вы писали:
G>>>сделать то же самое для конкретной сильной компоненты, через которую проходит путь.
V_>>Что тоже самое-то?
G>То же самое — это найти кратчайший путь между вершинами внутри сильной компоненты. G>Это не так сложно — для таких вычислений можно виртуально разрывать цикл. Вообще есть куча алгоритмов на графах — смотрите alglib и algolist. Я делал подобную вещь когда-то по учебнику дискретки — ничего сложного зедсь нет. Хотя — если будут вопросы — отвечу.
Причем тут кратчайший? Для кратчайших путей алгоритмы Дийкстры, Флойда, Беллмана отработают на ура и с циклами и без. Пофигу (если циклы неотрицательные).
Человек же хочет _критический_ путь. Длиннейший. Это известная NP-полная задача. Она поддается аппроксимации, но предложенный приближенный алгоритм автора не заинтересовал. Как и другие предложения. А полиномиального точного алгоритма он не найдет (если не докажет что P=NP)
Здравствуйте, kl, Вы писали:
kl>Причем тут кратчайший? Для кратчайших путей алгоритмы Дийкстры, Флойда, Беллмана отработают на ура и с циклами и без. Пофигу (если циклы неотрицательные). kl>Человек же хочет _критический_ путь. Длиннейший. Это известная NP-полная задача. Она поддается аппроксимации, но предложенный приближенный алгоритм автора не заинтересовал. Как и другие предложения. А полиномиального точного алгоритма он не найдет (если не докажет что P=NP)
Да, действительно, извинямс, не подумавши, ляпнул. С другой стороны, если мы ищем любой экстремальный (максимальный или минимальный) путь по графу, то задачу можно записать, как оптимизационную, причем решаемую методами линейного (если опять нигде не напутал) программирования. Или нет?
Grey2002 wrote: > Да, действительно, извинямс, не подумавши, ляпнул. С другой стороны, > если мы ищем любой экстремальный (максимальный или минимальный) путь по > графу, то задачу можно записать, как оптимизационную, причем решаемую > методами линейного (если опять нигде не напутал) программирования. Или нет?
Целочисленность может дать экспоненциальное количество условий при
лобовом подходе.
Здравствуйте, kl, Вы писали:
kl>Здравствуйте, Grey2002, Вы писали:
G>>Здравствуйте, Vintik_69, Вы писали:
V_>>>Здравствуйте, Grey2002, Вы писали:
G>>>>сделать то же самое для конкретной сильной компоненты, через которую проходит путь.
V_>>>Что тоже самое-то?
G>>То же самое — это найти кратчайший путь между вершинами внутри сильной компоненты. G>>Это не так сложно — для таких вычислений можно виртуально разрывать цикл. Вообще есть куча алгоритмов на графах — смотрите alglib и algolist. Я делал подобную вещь когда-то по учебнику дискретки — ничего сложного зедсь нет. Хотя — если будут вопросы — отвечу.
kl>Причем тут кратчайший? Для кратчайших путей алгоритмы Дийкстры, Флойда, Беллмана отработают на ура и с циклами и без. Пофигу (если циклы неотрицательные). kl>Человек же хочет _критический_ путь. Длиннейший. Это известная NP-полная задача. Она поддается аппроксимации, но предложенный приближенный алгоритм автора не заинтересовал. Как и другие предложения. А полиномиального точного алгоритма он не найдет (если не докажет что P=NP)
Хм, вообще-то, вроде как что кратчайший, что длиннейший, по идее, без разницы: веса дуг домножить на -1 — будет длиннейший.
Здравствуйте, FDSC, Вы писали:
FDS>Здравствуйте, kl, Вы писали:
kl>>Причем тут кратчайший? Для кратчайших путей алгоритмы Дийкстры, Флойда, Беллмана отработают на ура и с циклами и без. Пофигу (если циклы неотрицательные). kl>>Человек же хочет _критический_ путь. Длиннейший. Это известная NP-полная задача. Она поддается аппроксимации, но предложенный приближенный алгоритм автора не заинтересовал. Как и другие предложения. А полиномиального точного алгоритма он не найдет (если не докажет что P=NP)
FDS>Хм, вообще-то, вроде как что кратчайший, что длиннейший, по идее, без разницы: веса дуг домножить на -1 — будет длиннейший.
Ну-ну
осталось доказать, что это верно для всех _циклических_ графов — и Turing Award — твой,ибо P=NP отсюда следует просто автоматом :) Возьмешься?
Здравствуйте, kl, Вы писали:
FDS>>Хм, вообще-то, вроде как что кратчайший, что длиннейший, по идее, без разницы: веса дуг домножить на -1 — будет длиннейший.
kl>Ну-ну kl>осталось доказать, что это верно для всех _циклических_ графов — и Turing Award — твой,ибо P=NP отсюда следует просто автоматом Возьмешься?
Не возьмусь . Всё, я покинул эту тему — явно ничего не соображаю, хоть и работаю с графами.
Здравствуйте, kl, Вы писали:
FDS>>Хм, вообще-то, вроде как что кратчайший, что длиннейший, по идее, без разницы: веса дуг домножить на -1 — будет длиннейший.
kl>Ну-ну kl>осталось доказать, что это верно для всех _циклических_ графов — и Turing Award — твой,ибо P=NP отсюда следует просто автоматом Возьмешься?
Нет, ну а что он сказал неправильно? Ведь разницы между задачами о минимальном и максимальном путями в общем случае нет. Другое дело, что минимальный путь можно решить за полином при отсутствии циклов отрицательной длины, а максимальный — при отсутствии циклов положительной длины.
Здравствуйте, FDSC, Вы писали:
FDS>Здравствуйте, Darsufa, Вы писали:
FDS>Я давал там алгоритм, он должен работать (если ничего не найдёшь другого). Попробуй, если ничего другого не найдётся. FDS>(Споры были только по тому, за сколько эту задачу можно решить.)
Ну тот алгоритм неверен. Если путь максимален, то это не означает, что пути от первой вершины до промежуточных вершин пути должны быть максимальными.
Здравствуйте, _DAle_, Вы писали:
_DA>Здравствуйте, FDSC, Вы писали:
FDS>>Здравствуйте, Darsufa, Вы писали:
FDS>>Я давал там алгоритм, он должен работать (если ничего не найдёшь другого). Попробуй, если ничего другого не найдётся. FDS>>(Споры были только по тому, за сколько эту задачу можно решить.)
_DA>Ну тот алгоритм неверен. Если путь максимален, то это не означает, что пути от первой вершины до промежуточных вершин пути должны быть максимальными.
Может ещё и пример приведёшь? Я конечно, покинул эту тему, но это явно не в ту степь.
Если у нас есть максимальный путь, то его можно разбить на два пути, выбрав промежуточную вершину.
Если один из путей не максимальной длинны, то его можно заменить более длинным путём и найти путь длиннее, чем путь максимальной длины в графе.
Так что, по идее, если некоторая вершина D принадлежит пути от A до B, то часть этого пути от A до D должна быть наибольшей из всех возможных путей, соединяющих A и D.
Здравствуйте, _DAle_, Вы писали:
_DA>Нет, ну а что он сказал неправильно? Ведь разницы между задачами о минимальном и максимальном путями в общем случае нет. Другое дело, что минимальный путь можно решить за полином при отсутствии циклов отрицательной длины, а максимальный — при отсутствии циклов положительной длины.
М-м-м. Не понял. Это шутка? По моему вы противоречите самому себе. Я чуствую, скоро мне придётся искать человека, который заново объяснит мне теорию графов. Или я просто перегрелся на солнце (глупый )
Здравствуйте, FDSC, Вы писали:
FDS>Здравствуйте, _DAle_, Вы писали:
_DA>>Здравствуйте, FDSC, Вы писали:
FDS>>>Здравствуйте, Darsufa, Вы писали:
FDS>>>Я давал там алгоритм, он должен работать (если ничего не найдёшь другого). Попробуй, если ничего другого не найдётся. FDS>>>(Споры были только по тому, за сколько эту задачу можно решить.)
_DA>>Ну тот алгоритм неверен. Если путь максимален, то это не означает, что пути от первой вершины до промежуточных вершин пути должны быть максимальными.
FDS>Может ещё и пример приведёшь? Я конечно, покинул эту тему, но это явно не в ту степь.
FDS>Если у нас есть максимальный путь, то его можно разбить на два пути, выбрав промежуточную вершину. FDS>Если один из путей не максимальной длинны, то его можно заменить более длинным путём и найти путь длиннее, чем путь максимальной длины в графе. FDS>Так что, по идее, если некоторая вершина D принадлежит пути от A до B, то часть этого пути от A до D должна быть наибольшей из всех возможных путей, соединяющих A и D.
Вопрос снят. Если маскимальный путь от A до D пересекается с путём от D до B, то ваше утверждение правильно.
FDSC wrote: > _DA>Нет, ну а что он сказал неправильно? Ведь разницы между задачами о > минимальном и максимальном путями в общем случае нет. Другое дело, что > минимальный путь можно решить за полином при отсутствии циклов > отрицательной длины, а максимальный — при отсутствии циклов > положительной длины. > > М-м-м. Не понял. Это шутка? По моему вы противоречите самому себе. Я > чуствую, скоро мне придётся искать человека, который заново объяснит мне > теорию графов. Или я просто перегрелся на солнце (глупый )
Почему шутка? Вы сказали, что есть сведение задач друг к другу, что
правда. Но просто стандартные ограничения в задачах при этом меняются
так, что типичная задача на минимальный путь решаема легко, а на
максимальный — как правило, нет.
Изменения происходят следующие(причем в процессе работы разными способами делаются изменения в начальном графе и для каждого необходимо считать длиннейший путь из 1 в 11):
В каждом пути выбирается по одной вершине и между ними проводятся дуги, так что они образуют пути из m-1 дуг между собой(в данном примере это соответственно 9-2-7, 8-3-5, 4-10-6). После этих преобразований соответственно граф принимает вышеприведенный вид, что все-таки отличает его от произвольного ографа. Может это как-то может облегчить задачу нахождения длиннейшего пути из 1 в 11 вершину. Контуры возникают не всегда, но тем не менее могут возникать...
Вот этого я не очень понял. Зачем это делается (какова цель алгоритма) и как выбираются вершины. Сколько путей в начале: всегда 3 или может быть больше?
Потом, если только три пути, то и пути, связывающие три вершины длины не m-1, а 3, а m всегда равно 4. Или нет?
Впопросы, которые немешало бы решить:
Может ли возникнуть не просто конутр, а гамильтонов контур в графе?
Если мы знаем, как создаём контуры, можем ли мы каким-либо простым алгоритмом (исползующим это знание) исключать эти дуги, для работы с несколькими бесконтурными графами?
Возьмешься?
. Всё, я покинул эту тему — явно ничего не соображаю, хоть и работаю с графами.
)
