Здравствуйте, Mab, Вы писали:
FDS>>>>Само по себе наличие контуров в графе ещё не говорит о том, что стандартные алгоритмы не работают. Вообще, там можно сделать коорекцию весов дуг, так что стандартные алгоритмы будут работать. Как я не очень в курсе... но это стандартно Mab>>>И чего же, после этого мы научимся решать NP-трудную задачу? V>>А что, NP — трудные задачи уже неразрешимы? Mab>Разрешимы-то разрешимы, да вот только загадочные "стандартные алгоритмы" работают за полином (или какие тогда имеются в виду? backtracking?).
Насколько я понял, под словом "работают" понимается именно "работают в принципе", а не "работают за полиномиальное время". Естественно, никакой коррекцией весов NP-трудную задачу свести к полиномиально-разрешимой не получится, разве что эта коррекция сама неполиномиальна.
Но неполиномиальность алгоритма решения не означает, что им нельзя пользоваться. Решают же задачу коммивояжера. Да и, скажем, широко используемый симплекс-метод тоже неполиномиален и ничего, пользуются.
--
Sergey Chadov
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Re[15]: Критический путь в графе с циклами при определенных
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, FDSC, Вы писали:
Mab>Честно говоря, надоело спорить, т.к. я уже не понимаю, о чем именно спор
FDS>>Почему все длины равны -1? Mab>Ну потому, что так мне кажется резонно сводить задачу о длиннейшем пути к задаче о кратчайшем. Есть другие варианты сведения?
Все длины умножаются на -1, но не равны. Там есть длины 0, 4, 5, 6, 8, может ещё. Вот и получится, что 4 заменим на -4 и т.д.
А так согласен.
FDS>>Если он у нас с контурами — нужно в алгоритме просто ставить предохранитель против нахождения циклов и зацикливания Mab>Не знаю, что тут имеется в виду под "предохранителем". Это будет разновидность backtracking-а такая?
Нет, не в обратном ходе. В прямом ходе, как я указал выше, нужно сохранять путь и отслеживать циклы. Только там небольшая ошибка, нужно в путь текущей вершины и её записывать то же, тогда алгоритм циклы будет игнорировать.
Re[16]: Критический путь в графе с циклами при определенных
Здравствуйте, FDSC, Вы писали:
FDS>Все длины умножаются на -1, но не равны. Там есть длины 0, 4, 5, 6, 8, может ещё. Вот и получится, что 4 заменим на -4 и т.д. FDS>А так согласен.
Да, я не заметил, что длины разные -- на картинке их не было, а матрицу я не смотрел. В любом случае, если они положительные, но дела это не меняет.
FDS>Нет, не в обратном ходе. В прямом ходе, как я указал выше, нужно сохранять путь и отслеживать циклы. Только там небольшая ошибка, нужно в путь текущей вершины и её записывать то же, тогда алгоритм циклы будет игнорировать.
Backtracking -- это не обратный ход, а т.н. перебор с возвратом.
Re[17]: Критический путь в графе с циклами при определенных
Здравствуйте, Mab, Вы писали:
FDS>>Нет, не в обратном ходе. В прямом ходе, как я указал выше, нужно сохранять путь и отслеживать циклы. Только там небольшая ошибка, нужно в путь текущей вершины и её записывать то же, тогда алгоритм циклы будет игнорировать. Mab>Backtracking -- это не обратный ход, а т.н. перебор с возвратом.
Сути дела это не меняет: выше я указал алгоритм, который должен работать на указанных графах за полиномиальное время.
Что такое перебор с возвратом? Пожалуйста, приведите какой нибудь пример.
Re[18]: Критический путь в графе с циклами при определенных
Здравствуйте, FDSC, Вы писали:
FDS>Сути дела это не меняет: выше я указал алгоритм, который должен работать на указанных графах за полиномиальное время.
Указанных -- это каких? Скажем, он может найти длиннейший простой путь в произвольном направленном графе, где длина пути измеряется числом дуг? Извините, но я не верю в чудеса. Обычно тот факт, что из рассуждений следует P = NP автора настораживает и он проверяет свои рассуждения, чтобы найти в них ошибку.
FDS>Что такое перебор с возвратом? Пожалуйста, приведите какой нибудь пример.
Use google: backtracking.
Re[19]: Критический путь в графе с циклами при определенных
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, FDSC, Вы писали:
FDS>>Сути дела это не меняет: выше я указал алгоритм, который должен работать на указанных графах за полиномиальное время. Mab>Указанных -- это каких? Скажем, он может найти длиннейший простой путь в произвольном направленном графе, где длина пути измеряется числом дуг? Извините, но я не верю в чудеса.
найти длиннейший простой путь в произвольном направленном графе и найти длиннейший простой путь в произвольном направленном графе, связывающий вершины a и b — не одно и то же.
Mab>Обычно тот факт, что из рассуждений следует P = NP автора настораживает и он проверяет свои рассуждения, чтобы найти в них ошибку.
Вы мне так и не доказали, что данная задача NP
FDS>>Что такое перебор с возвратом? Пожалуйста, приведите какой нибудь пример. Mab>Use google: backtracking.
М-м-м, не люблю google. Так и скажите — лень.
Re[20]: Критический путь в графе с циклами при определенных
Здравствуйте, FDSC, Вы писали:
FDS>Вы мне так и не доказали, что данная задача NP
Мне жаль, что так вышло. Только дела это не меняет.
FDS>М-м-м, не люблю google. Так и скажите — лень.
Как угодно. Первая же ссылка дает ответ на этот вопрос и избавляет он необходимости спрашивать здесь.
Re[21]: Критический путь в графе с циклами при определенных
Здравствуйте, Mab, Вы писали:
Mab>Здравствуйте, FDSC, Вы писали:
FDS>>Вы мне так и не доказали, что данная задача NP Mab>Мне жаль, что так вышло. Только дела это не меняет.
Да, дела это не меняет — задача не NP-полная, я так и не услышал ни одного возражения по существу, а мой алгоритм должен найти решение за n^3, где ошибка? Опять лень? Честно говоря — мне тоже
FDS>>М-м-м, не люблю google. Так и скажите — лень. Mab>Как угодно. Первая же ссылка дает ответ на этот вопрос и избавляет он необходимости спрашивать здесь.
Ну-ну. Вы хоть смотрели на что первая ссылка указывает?
Re[22]: Критический путь в графе с циклами при определенных
Здравствуйте, FDSC, Вы писали:
FDS>Да, дела это не меняет — задача не NP-полная, я так и не услышал ни одного возражения по существу, а мой алгоритм должен найти решение за n^3, где ошибка? Опять лень? Честно говоря — мне тоже
Вы внимательно прочитали? К задаче о длиннейшем пути в невзвешенном графе сводится задача о гамильтоновом пути. Задача в невзвешенном графе сводится к задаче во взвешенном. Значит, задача поиска длиннейшего пути во взвешенном графе — NP.
Теперь что касается вашего утверждения о том, что путь между двумя заданными вершинами проще найти, чем длиннейший путь между произвольными вершинами. Это не так. Элементарное соображение: пусть мы умеем искать путь из A в B за полином. Тогда чтобы найти длиннейший путь в произвольном графе добавим две вершины: исток (из него есть ребра во все остальные вершины) и сток (в него ведут ребра из всех остальных вершин). Найдем путь из истока в сток. Если из найденного пути исключить исток и сток — это и будет искомый длиннейший путь в заданном графе.
Re[20]: Критический путь в графе с циклами при определенных
Здравствуйте, FDSC, Вы писали:
FDS>Здравствуйте, Mab, Вы писали:
Mab>>Здравствуйте, FDSC, Вы писали:
FDS>>>Сути дела это не меняет: выше я указал алгоритм, который должен работать на указанных графах за полиномиальное время. Mab>>Указанных -- это каких? Скажем, он может найти длиннейший простой путь в произвольном направленном графе, где длина пути измеряется числом дуг? Извините, но я не верю в чудеса.
FDS>найти длиннейший простой путь в произвольном направленном графе и найти длиннейший простой путь в произвольном направленном графе, связывающий вершины a и b — не одно и то же.
Из полиномиальности второй задачи будет следовать полиномиальность решения первой. Так что в данном случае это ничего не меняет.
Mab>>Обычно тот факт, что из рассуждений следует P = NP автора настораживает и он проверяет свои рассуждения, чтобы найти в них ошибку.
FDS>Вы мне так и не доказали, что данная задача NP
Рассмотрим задачу о максимальной гамильтоновой цепи во взвешенном графе. Она является NP-трудной. Очевидно, что она сводится к задаче о максимальном гамильтоновом пути в ориентированном взвешенном графе. Эта задача сводится к задаче о максимальном пути в ор графе. А эта сводится к нашей исходной задаче.
Re[2]: Критический путь в графе с циклами при определенных у
Здравствуйте, LaptevVV, Вы писали:
LVV>Здравствуйте, Darsufa, Вы писали:
D>>Уважаемые!
D>>Прошу помочь в такой проблеме: D>>Имеется ориентированный граф, в котором возможны циклы. В нем необходимо найти длиннейший (критический) путь из начальной вершины в конечную. Все дуги однонаправленны. Путь 100% существует (особенность графа). LVV>А применика ты алгоритм Дейкстры, только вместо минимума вычисляй максимум...
Вы же вроде в университете преподаете, как же так?
Re: Критический путь в графе с циклами при определенных усло
От:
Аноним
Дата:
05.06.06 11:47
Оценка:
Здравствуйте, Darsufa, Вы писали:
D>Уважаемые!
D>Прошу помочь в такой проблеме: D>Имеется ориентированный граф, в котором возможны циклы. В нем необходимо найти длиннейший (критический) путь из начальной вершины в конечную. Все дуги однонаправленны. Путь 100% существует (особенность графа). D>Граф представлен в виде матрицы m x m типа(как пример):
D>
D>Вышеприведенный пример представляет собой ориентированный граф, внутри которого есть циклы (цикл путь: 2-3-5-6-7-2). Поэтому стандартный алгоритм нахождения критического пути не работает(также как и топологическая сортировка). Необходимо сделать так чтобы он искал длиннейший путь, при это не заходя в уже посещенные вершины. Вот как выглядит данный граф:
D>
не силен в графах, но недавно наткнулся на тут может поможет
Re[21]: Критический путь в графе с циклами при определенных
Здравствуйте, _DAle_, Вы писали:
FDS>>>>Сути дела это не меняет: выше я указал алгоритм, который должен работать на указанных графах за полиномиальное время. Mab>>>Указанных -- это каких? Скажем, он может найти длиннейший простой путь в произвольном направленном графе, где длина пути измеряется числом дуг? Извините, но я не верю в чудеса.
FDS>>найти длиннейший простой путь в произвольном направленном графе и найти длиннейший простой путь в произвольном направленном графе, связывающий вершины a и b — не одно и то же.
_DA>Из полиномиальности второй задачи будет следовать полиномиальность решения первой. Так что в данном случае это ничего не меняет.
Mab>>>Обычно тот факт, что из рассуждений следует P = NP автора настораживает и он проверяет свои рассуждения, чтобы найти в них ошибку.
FDS>>Вы мне так и не доказали, что данная задача NP
_DA>Рассмотрим задачу о максимальной гамильтоновой цепи во взвешенном графе. Она является NP-трудной. Очевидно, что она сводится к задаче о максимальном гамильтоновом пути в ориентированном взвешенном графе. Эта задача сводится к задаче о максимальном пути в ор графе. А эта сводится к нашей исходной задаче.
Попытайтесь найти Гамильтонов путь в приведённом графе.
НАШ ПУТЬ НЕ ГАМИЛЬТОНОВ, Гамильтонов путь есть путь в котором участвуют все вершины.
В графе где мы ищем путь вообще может не существовать Гамильтоновых путей.
А если они существуют и мы их найдём нашим алгоритмом, то это означает, что в данном случае NP-полная задача решается за полиномиальное время
Re[22]: Критический путь в графе с циклами при определенных
Здравствуйте, FDSC, Вы писали:
FDS>Попытайтесь найти Гамильтонов путь в приведённом графе. FDS>НАШ ПУТЬ НЕ ГАМИЛЬТОНОВ, Гамильтонов путь есть путь в котором участвуют все вершины. FDS>В графе где мы ищем путь вообще может не существовать Гамильтоновых путей. FDS>А если они существуют и мы их найдём нашим алгоритмом, то это означает, что в данном случае NP-полная задача решается за полиномиальное время на данном конкретном графе
Re[22]: Критический путь в графе с циклами при определенных
FDSC wrote: > Попытайтесь найти Гамильтонов путь в приведённом графе. > НАШ ПУТЬ НЕ ГАМИЛЬТОНОВ, Гамильтонов путь есть путь в котором участвуют > все вершины. > В графе где мы ищем путь вообще может не существовать Гамильтоновых путей. > А если они существуют и мы их найдём нашим алгоритмом, то это означает, > что в данном случае NP-полная задача решается за полиномиальное время
Рассмотрим произвольный граф. Переберём все его рёбра. Для каждого
найдём длиннейший простой путь, соединяющий вершины гипотетическим
алгоритмом поиска длиннейшего пути с весом 1 для каждого ребра. Если ни
один не даст гамильтонов цикл, то его банально нет. Если найдём — то вот
он. Алгоритм всегда решает точно. Сведение увеличивает время в $n^2$
раз. Т.е. Вы просите полиномиальный алгоритм для NPC задачи.
Posted via RSDN NNTP Server 2.1 beta
Re[22]: Критический путь в графе с циклами при определенных
Еще раз советую внимательно прочитать написанное по ходу ветки. И вообще подумать над тем, что такое редукция задач. Попробуйте вникнуть в смысл фразы:
Запустим поиск длиннейшего простого a-b пути в данном графе. Если будет будет иметь длину n — 1 (где n -- число вершин), то значит он гамильтонов. Иначе гамиильтоновых путей нет. Тем самым, получено сведение задачи распознавания a-b гамильтоновости к задаче нахождения длиннейшего простого a-b пути.
Упираться на настаивать на том, что у Вас есть полиномиальный алгоритм просто глупо.
Re[23]: Критический путь в графе с циклами при определенных
Здравствуйте, raskin, Вы писали:
R>FDSC wrote: >> Попытайтесь найти Гамильтонов путь в приведённом графе. >> НАШ ПУТЬ НЕ ГАМИЛЬТОНОВ, Гамильтонов путь есть путь в котором участвуют >> все вершины. >> В графе где мы ищем путь вообще может не существовать Гамильтоновых путей. >> А если они существуют и мы их найдём нашим алгоритмом, то это означает, >> что в данном случае NP-полная задача решается за полиномиальное время R>Рассмотрим произвольный граф. Переберём все его рёбра. Для каждого R>найдём длиннейший простой путь, соединяющий вершины гипотетическим R>алгоритмом поиска длиннейшего пути с весом 1 для каждого ребра. Если ни R>один не даст гамильтонов цикл, то его банально нет. Если найдём — то вот R>он. Алгоритм всегда решает точно. Сведение увеличивает время в $n^2$ R>раз. Т.е. Вы просите полиномиальный алгоритм для NPC задачи.
Ну, я не прошу. Кажется я всё-таки не прав . Осталось только найти у себя ошибку, чем и буду заниматься весь оставшийся вечер
(На самом деле гениев никогда не понимают )
Re: Критический путь в графе с циклами при определенных усло
Т.е. есть начальная вершина и есть m множеств путей(в данном примере 3, это пути 1-2-3-4-11, 1-5-6-7-11 и 1-8-9-10-11), которые состоят каждая из m вершин. В этом графе легко найти длиннейший путь — это длина длиннейшего пути (какогото из m).
Но в процессе работы начальный граф видоизменяется и, соответственно, принимает, к примеру, такой вид(все дуги взвешенные): D>
Изменения происходят следующие(причем в процессе работы разными способами делаются изменения в начальном графе и для каждого необходимо считать длиннейший путь из 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])
}
D>Уважаемые!
D>Прошу помочь в такой проблеме: D>Имеется ориентированный граф, в котором возможны циклы. В нем необходимо найти длиннейший (критический) путь из начальной вершины в конечную. Все дуги однонаправленны. Путь 100% существует (особенность графа). D>Граф представлен в виде матрицы m x m типа(как пример):
D>
D>Вышеприведенный пример представляет собой ориентированный граф, внутри которого есть циклы (цикл путь: 2-3-5-6-7-2). Поэтому стандартный алгоритм нахождения критического пути не работает(также как и топологическая сортировка). Необходимо сделать так чтобы он искал длиннейший путь, при это не заходя в уже посещенные вершины. Вот как выглядит данный граф:
D>
Re: Критический путь в графе с циклами при определенных усло
Здравствуйте, Darsufa, Вы писали:
D>Уважаемые!
D>Прошу помочь в такой проблеме: D>Имеется ориентированный граф, в котором возможны циклы. В нем необходимо найти длиннейший (критический) путь из начальной вершины в конечную. Все дуги однонаправленны. Путь 100% существует (особенность графа). D>Граф представлен в виде матрицы m x m типа(как пример):
. Осталось только найти у себя ошибку, чем и буду заниматься весь оставшийся вечер 
)
