На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Максимальный путь в графе
    Помогите ребят, горю. Весь нет обыскал - ничего не нашёл(
      Можно использовать алгоритм Дейкстры или Флойда-Уоршелла, поменяв там знак у условия: меньше на больше. Только надо отметить, что в неориентированных графах максимального пути не существует, а существует только в ориентированных графах без циклов отрицательного веса.
        Цитата mo3r @
        Можно использовать алгоритм Дейкстры или Флойда-Уоршелла, поменяв там знак у условия: меньше на больше. Только надо отметить, что в неориентированных графах максимального пути не существует, а существует только в ориентированных графах без циклов отрицательного веса.

        чушь с позволения сказать
          Цитата esperanto @
          чушь с позволения сказать

          ?

          Добавлено
          Цитата esperanto @
          чушь с позволения сказать

          Да, точно.
          Цитата mo3r @
          без циклов отрицательного веса

          Должно быть без циклов положительного веса.
            попробуй поиск по ключевой фразе "гамильтонов путь (цикл)".
            например http://www.intuit.ru/department/algorithms/gaa/8/gaa_8.html (Алгоритм 2. Поиск гамильтоновых циклов)
              Никакой Дейкстра и Флойд Варшал тут не помогат, это известная NP задача. не обязательно гамильтонов цикл.
                Цитата ArdI @
                Никакой Дейкстра и Флойд Варшал тут не помогат, это известная NP задача.

                Да неужели? Алгоритмом Флойда-Уоршелла спокойно ищется максимальный путь или факт его отсутствия (только надо добавить еще одну итерацию для проверки недостижимости), а алгоритмом Дейкстры можно спокойно найти максимальный путь при условии его существования.

                А вот максимальный простой путь — это совсем другая задача. И имеет мало общего с тем, о чем было спрошено.
                  Точно...нужно найти максимальный простой путь...
                    Цитата mo3r @
                    Цитата ArdI @
                    Никакой Дейкстра и Флойд Варшал тут не помогат, это известная NP задача.

                    Да неужели? Алгоритмом Флойда-Уоршелла спокойно ищется максимальный путь или факт его отсутствия (только надо добавить еще одну итерацию для проверки недостижимости), а алгоритмом Дейкстры можно спокойно найти максимальный путь при условии его существования.

                    А вот максимальный простой путь — это совсем другая задача. И имеет мало общего с тем, о чем было спрошено.

                    Я как раз и говорю о простом пути, а вы о каком ?
                      Цитата ArdI @
                      Я как раз и говорю о простом пути, а вы о каком ?

                      Те высказывания справедливы для максимального пути.
                        А что такое максимальный путь ? Можно же несколько типов придумать, я хочу, чтобы вы это и объяснили.
                          Вот кусок кода поиска минимального пути в графе по алгоритму Дейкстры на С:
                          #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) .


                          Но это не сработало, программа почти всегда находит максимальные пути неправильно. Возможно, кто-нибудь подскажет, как изменить это код минимального пути на код нахождения максимального?
                          Сообщение отредактировано: _Spy_ -
                            мистер Spy, ну вы совсем не в ту оперу, у нас тут речь идёт о Длинном пусти, а не о коротком.
                              Вообще-то Вы не дочитали мой пост до конца.
                              Я написАл, что этот код можно изменить для максимального пути, но у меня это не совсем получилось, и я подумал, что, возможно, кто-то поймёт, как это сделать.
                                а, да, прошу прощения. ну это элементарно. Алгоритм дейстры работает правильно почему? Потому что соблюдается свойство подстуктуры. Т.е. если я на первом шаре выбираю минимальный путь из источника в какуюнить вершину, то я могу эту вершину после этого шага смело зачеркивать. Так вот дело в том, что для определенных максимальных путей это неверно, поэтому я не понимаю, что щас пытается мистер mo3r скаЗать.
                                Сообщение отредактировано: ArdI -
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0447 ]   [ 16 queries used ]   [ Generated: 19.03.24, 04:39 GMT ]