Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.189.180.244] |
|
Сообщ.
#1
,
|
|
|
Помогите ребят, горю. Весь нет обыскал - ничего не нашёл(
|
Сообщ.
#2
,
|
|
|
Можно использовать алгоритм Дейкстры или Флойда-Уоршелла, поменяв там знак у условия: меньше на больше. Только надо отметить, что в неориентированных графах максимального пути не существует, а существует только в ориентированных графах без циклов отрицательного веса.
|
Сообщ.
#3
,
|
|
|
Цитата mo3r @ Можно использовать алгоритм Дейкстры или Флойда-Уоршелла, поменяв там знак у условия: меньше на больше. Только надо отметить, что в неориентированных графах максимального пути не существует, а существует только в ориентированных графах без циклов отрицательного веса. чушь с позволения сказать |
Сообщ.
#4
,
|
|
|
Цитата esperanto @ чушь с позволения сказать ? Добавлено Цитата esperanto @ чушь с позволения сказать Да, точно. Цитата mo3r @ без циклов отрицательного веса Должно быть без циклов положительного веса. |
Сообщ.
#5
,
|
|
|
попробуй поиск по ключевой фразе "гамильтонов путь (цикл)".
например http://www.intuit.ru/department/algorithms/gaa/8/gaa_8.html (Алгоритм 2. Поиск гамильтоновых циклов) |
Сообщ.
#6
,
|
|
|
Никакой Дейкстра и Флойд Варшал тут не помогат, это известная NP задача. не обязательно гамильтонов цикл.
|
Сообщ.
#7
,
|
|
|
Цитата ArdI @ Никакой Дейкстра и Флойд Варшал тут не помогат, это известная NP задача. Да неужели? Алгоритмом Флойда-Уоршелла спокойно ищется максимальный путь или факт его отсутствия (только надо добавить еще одну итерацию для проверки недостижимости), а алгоритмом Дейкстры можно спокойно найти максимальный путь при условии его существования. А вот максимальный простой путь — это совсем другая задача. И имеет мало общего с тем, о чем было спрошено. |
Сообщ.
#8
,
|
|
|
Точно...нужно найти максимальный простой путь...
|
Сообщ.
#9
,
|
|
|
Цитата mo3r @ Цитата ArdI @ Никакой Дейкстра и Флойд Варшал тут не помогат, это известная NP задача. Да неужели? Алгоритмом Флойда-Уоршелла спокойно ищется максимальный путь или факт его отсутствия (только надо добавить еще одну итерацию для проверки недостижимости), а алгоритмом Дейкстры можно спокойно найти максимальный путь при условии его существования. А вот максимальный простой путь — это совсем другая задача. И имеет мало общего с тем, о чем было спрошено. Я как раз и говорю о простом пути, а вы о каком ? |
Сообщ.
#10
,
|
|
|
Цитата ArdI @ Я как раз и говорю о простом пути, а вы о каком ? Те высказывания справедливы для максимального пути. |
Сообщ.
#11
,
|
|
|
А что такое максимальный путь ? Можно же несколько типов придумать, я хочу, чтобы вы это и объяснили.
|
Сообщ.
#12
,
|
|
|
Вот кусок кода поиска минимального пути в графе по алгоритму Дейкстры на С:
#include <stdio.h> #include <stdlib.h> #include <malloc.h> #define TOPS 4 int main(int argc, char* argv[]) { int infinity=10000; int p = TOPS; int** a = LoadDataFromFile("data1.txt"); int s = 1; int g = 3; int x[TOPS]; //Массив, содержащий единицы и нули для каждой вершины, // x[i]=0 - еще не найден кратчайший путь в i-ю вершину, // x[i]=1 - кратчайший путь в i-ю вершину уже найден int t[TOPS]; //t[i] - длина кратчайшего пути от вершины s в i int h[TOPS]; //h[i] - вершина, предшествующая i-й вершине // на кратчайшем пути // Инициализируем начальные значения массивов int u; // Счетчик вершин for (u=0;u<p;u++) { t[u]=infinity; //Сначала все кратчайшие пути из s в i //равны бесконечности x[u]=0; // и нет кратчайшего пути ни для одной вершины } h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует t[s]=0; // Кратчайший путь из s в s равен 0 x[s]=1; // Для вершины s найден кратчайший путь v=s; // Делаем s текущей вершиной while(1) { // Перебираем все вершины, смежные v, и ищем для них кратчайший путь for(u=0;u<p;u++) { if(a[v][u]==0)continue; // Вершины u и v несмежные if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не //найден кратчайший путь // и новый путь в u короче чем //старый, то { t[u]=t[v]+a[v][u]; //запоминаем более короткую длину пути в //массив t и h[u]=v; //запоминаем, что v->u часть кратчайшего //пути из s->u } printf("%d\n",t[u]); } // Ищем из всех длин некратчайших путей самый короткий int w=infinity; // Для поиска самого короткого пути v=-1; // В конце поиска v - вершина, в которую будет // найден новый кратчайший путь. Она станет // текущей вершиной for(u=0;u<p;u++) // Перебираем все вершины. { if(x[u]==0 && t[u]<w) // Если для вершины u не найден кратчайший // путь и если длина пути в вершину u меньше // уже найденной, то { v=u; // текущей вершиной становится u-я вершина w=t[u]; } } if(v==-1) { printf("No ways"); break; } if(v==g) // Найден кратчайший путь, { // выводим его printf("Min way = "); u=g; while(u!=s) { printf("%d<-",u); u=h[u]; } printf("%d\n",s); printf("%d",t[g]); break; } x[v]=1; } free(a); return 0; } Здесь из файла загружается матрица смежности. Я думал, что максимальный путь можно найти, поменяв кое-что в коде, а именно: int infinity = 10000 на int infinity = -10000; , затем строчку if(x[u]==0 && t[u]>t[v]+a[v][u]) на if(x[u]==0 && t[u]<t[v]+a[v][u]) и строчку if(x[u]==0 && t[u]<w) на if(x[u]==0 && t[u]>w) . Но это не сработало, программа почти всегда находит максимальные пути неправильно. Возможно, кто-нибудь подскажет, как изменить это код минимального пути на код нахождения максимального? |
Сообщ.
#13
,
|
|
|
мистер Spy, ну вы совсем не в ту оперу, у нас тут речь идёт о Длинном пусти, а не о коротком.
|
Сообщ.
#14
,
|
|
|
Вообще-то Вы не дочитали мой пост до конца.
Я написАл, что этот код можно изменить для максимального пути, но у меня это не совсем получилось, и я подумал, что, возможно, кто-то поймёт, как это сделать. |
Сообщ.
#15
,
|
|
|
а, да, прошу прощения. ну это элементарно. Алгоритм дейстры работает правильно почему? Потому что соблюдается свойство подстуктуры. Т.е. если я на первом шаре выбираю минимальный путь из источника в какуюнить вершину, то я могу эту вершину после этого шага смело зачеркивать. Так вот дело в том, что для определенных максимальных путей это неверно, поэтому я не понимаю, что щас пытается мистер mo3r скаЗать.
|
Сообщ.
#16
,
|
|
|
Хм...
Так возможно ли изменить вышенаписанный код так, чтобы максимальные пути искались, и искались правильно? Или надо применять вообще какой-то другой алгоритм ? |
Сообщ.
#17
,
|
|
|
Алгоритм Дейкстры не подойдёт (
|
Сообщ.
#18
,
|
|
|
Цитата Мавроди @ Алгоритм Дейкстры не подойдёт ( Алгоритм Дейкстры, действительно, не применим без дополнительных модификаций. Выложил очень простое решение с помощью метода динамического программирования: https://gist.github.com/Infl1ght/54960c499e...cf1db9c6f11b8ec |