Модераторы: Daevaorn
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Прошу помочь, алгоритм критического пути в графе (C++) 
:(
    Опции темы
Dars2
  Дата 21.5.2006, 10:54 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 7
Регистрация: 21.5.2006

Репутация: нет
Всего: нет
Следующая проблема:
 
Нужен алгоритм нахождения критического (длиннейшего) пути в орграфе от самой первой вершины до последней (от 0 до m-1), представленного в виде матрицы 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). Поэтому стандартный алгоритм нахождения критического пути не работает. Необходимо сделать так чтобы он искал длиннейший путь, при это не заходя в уже посещенные вершины. На данный момент есть следующий код, но он не похоже не работает при зацикливании:
Код

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]) 
}

Возможно, как-то можно внести изменение в этот код, чтобы решалось нормально. Помогите плиз!!!!
  

Это сообщение отредактировал(а) Dars2 - 21.5.2006, 11:03
PM MAIL   Вверх
Dars2
Дата 24.5.2006, 16:56 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 7
Регистрация: 21.5.2006

Репутация: нет
Всего: нет
Неужели нет решения???? 
PM MAIL   Вверх
Vaulter
Дата 24.5.2006, 17:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Участник Клуба
Сообщений: 1724
Регистрация: 30.12.2002
Где: бункер

Репутация: 2
Всего: 22
Dars2, есть, но стоит денег 


--------------------
PM MAIL WWW ICQ   Вверх
Helicopterr
Дата 25.5.2006, 00:49 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 355
Регистрация: 20.8.2005
Где: Stavropol

Репутация: 2
Всего: 3
Цитата(Dars2)
Необходимо сделать так чтобы он искал длиннейший путь, при это не заходя в уже посещенные вершины

Это же задача коммивояжера. Только там, кажется, ближайший путь. Ищи в сети + посмотри   

Это сообщение отредактировал(а) Helicopterr - 25.5.2006, 01:19


--------------------
people can fly
PM MAIL   Вверх
Dars2
Дата 27.5.2006, 09:38 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 7
Регистрация: 21.5.2006

Репутация: нет
Всего: нет
Цитата(Vaulter @ 24.5.2006,  17:49)
Dars2, есть, но стоит денег

Готов заплатить если действительно четкое решение будет с минимальной сложностью 
PM MAIL   Вверх
Helicopterr
Дата 27.5.2006, 18:36 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 355
Регистрация: 20.8.2005
Где: Stavropol

Репутация: 2
Всего: 3
Dars2
А что значит 
Цитата(Dars2)
Используем техничку динамического программирования
 smile ??? 


--------------------
people can fly
PM MAIL   Вверх
Dars2
Дата 27.5.2006, 19:14 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 7
Регистрация: 21.5.2006

Репутация: нет
Всего: нет
Цитата(Helicopterr @ 27.5.2006,  18:36)
Dars2
А что значит 
Цитата(Dars2)
Используем техничку динамического программирования
 smile ???

очепятка)))

Люди ну помогите плиз!!! 
PM MAIL   Вверх
Earnest
Дата 29.5.2006, 12:16 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183
1) Топологическая сортировка не применима к графу с циклами. 
2) Чтобы не заходить в вершины повторно, помечай их - это стандартная техника. 


--------------------
...
PM   Вверх
pablo
Дата 29.5.2006, 16:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 320
Регистрация: 12.2.2005
Где: Вильнюс, Литва

Репутация: 4
Всего: 6
А не подойдёт ли здесь алгоритм Дейкстры, только вмеско поиска самой короткой вершины графа, искать самую длинную ? 


--------------------
Первый блин всегда похож на сферу, иногда бывает и куб.
PM MAIL ICQ   Вверх
Dars2
Дата 3.6.2006, 11:40 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 7
Регистрация: 21.5.2006

Репутация: нет
Всего: нет
Earnest, ну я так понимаю что без топологической сортировки, даже если помечать вершины алгоритм уже не будет работать корректно? 

pablo, Дейкстры тоже только без циклов работает... 
PM MAIL   Вверх
Earnest
Дата 5.6.2006, 08:25 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Экс. модератор
Сообщений: 5962
Регистрация: 17.6.2005
Где: Рязань

Репутация: 53
Всего: 183
Цитата(Dars2 @  3.6.2006,  12:40 Найти цитируемый пост)
Earnest, ну я так понимаю что без топологической сортировки, даже если помечать вершины алгоритм уже не будет работать корректно? 

Естественно... 
А алгоритм поиска короткого пути не обращается... Кстати, с циклами он отлично работает: кратчайший путь он и есть кратчайший. А вот самый длинный путь требует более жесткого определения: ведь если начать ходить кругами, много накрутить можно. Поэтому это требование (без возвратов) должно быть явно выражено в алгоритме. 


--------------------
...
PM   Вверх
  
 Ответ в темуСоздание новой темы Создание опроса
Правила форума "С++:Общие вопросы"
Earnest Daevaorn

Добро пожаловать!

  • Черновик стандарта C++ (за октябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика(4.4мб).
  • Черновик стандарта C (за сентябрь 2005) можно скачать с этого сайта. Прямая ссылка на файл черновика (3.4мб).
  • Прежде чем задать вопрос, прочтите это и/или это!
  • Здесь хранится весь мировой запас ссылок на документы, связанные с C++ :)
  • Не брезгуйте пользоваться тегами [code=cpp][/code].
  • Пожалуйста, не просите написать за вас программы в этом разделе - для этого существует "Центр Помощи".
  • C++ FAQ

Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, Earnest Daevaorn
 
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | C/C++: Общие вопросы | Следующая тема »

Подписаться на тему | Подписка на этот форум | Скачать/Распечатать тему


 




[ Время генерации скрипта: 0.0571 ]   [ Использовано запросов: 22 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
 По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.