VPF::Кратчайшие пути по графу от А до Б

rcdimon

Дата 21.7.2008, 21:46 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

Репутация: нет
Всего: 2

Всем привет.

Тема поиска оптимального пути по направленному взвешенному графу уже неоднократно обсуждалась на этом форуме, но внятногоответа, к сожалению, получить не удалось.

Граф с числом вершин более нескольких тысяч. Граф направленный, взвешенный, без отрицательных весов.

Есть Алгори́тм Де́йкстры, но он находит кратчайшее расстояние от одной из вершин графа до всех остальных. На графе с несколькими тысячами вершин это слишком дорого, при условии что нужен только один путь из одной вершины в другую.

Нужны алгоритмы для писка пути минимальной стоимости и для пути с минимальным числом вершин от вершины А до Б.

Нужен сам алгоритм по шагам или код.

Заранее спасибо

Akina

Дата 22.7.2008, 07:46 (ссылка)

(нет голосов)

Загрузка ...

Советчик

Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

Репутация: 20
Всего: 454

Граф ориентированный? тогда алгоритм Флойда—Уоршелла. Иначе все-таки Дейкстра.
По-любому для определения кратчайшего пути в ОДНУ вершину, если нет каких-то неозвученных особенностей графа, необходимо получение стоимостей достижения ВСЕХ вершин.

--------------------

О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

rcdimon

Дата 22.7.2008, 17:22 (ссылка)

(голосов:1)

Загрузка ...

Опытный

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

Репутация: нет
Всего: 2

Я просто тут сварганил какой-то алгоритмик ) Не берусь утверждать что он лучше чего-то, но по моему ничего. Вот интересно бред это сивый кобылы или что-то в этом есть? Как считаете?

Вобщем алгоритм следующий- Открываем учебник по дискретке и находим главу про графы. Там находим метод нахождения матрицы стоимостей для ориентированного графа... Для каждого столбца матрицы надо решить системку уравнений в полукольце R+.... Где 1 и 0 не являются 1 и 0 полуцольца, + - операция взятие наименьшего, *- арифметическое сложение. Подписываем к каждой строке справа еще по одному элементу. Если мы ищем первый столбец матрицы стоимостей- то напротив первой строки пишем 0, напротив других бесконечноть. Если второй столбец- то на против второй 0, напротив других бесконечность и т.д.

Решается система, находится столбец. А столбец- есть ни что иное, как стоимости прохождения от всех вершин В первую (если это первый столбец).

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

Встал вопрос- как заставить это сделать программу. Вспомнил что системы удобно решать в матричном виде- приводишь ее к ступенчатому виду и готово. Но там то математика нормальная, а тут через одно место ) И ноль не ноль и сложение не сложение )

В итоге стал изобретать метод решения системы уравнений. Записываю матрицу и натравливаю на нее программу. Что она делает:

1. Просто вычеркивает все диагональные элементы. (Если посчитать руками систему то получается что так и происходит. Например X1 = 2X1 + 3X2 + 4 из этого получается X1 = 2*(3X2 + 4) А итерация любого элемента в этом полукольце равна еденице. И получаем X1 = 3X2 + 4 то есть просто выкинули диагональный элемент из матрицы)

2. Строку справа от которой ноль- считать не надо. Всю ее вычеркиваем. Я запрограммировал программу так, что вычеркнуто- это когда стоит -1 на этом месте. Отрицательных дуг у меня нет.

3. Начинается основная часть алгоритма.
3.1 Вызов процедуры сервиса над матрицей. Она -
- удаляет диагональные элементы (которые могут появляться по ходу раоботы алгоритма)
- Подставляет переменные (я так назвал посчитаные уже строки. Одна такая у нас уже есть точно, та, где ноль был изначально справа. Программа знает какие строки уже посчитаны, и сканирует матрицу по вертикали по столбцу с тем же номером и вычеркивает все что там есть, но зато ту цифру что там была алгоритм складывает со значением переменной и записывает в правый элемент строки (там где изначально приписали бесконечность. Причем меняет он этот правый элемент только в том случае, если новый меньше чем то, что там уже находится))
- Находит новые переменные- Находит строки в которых нет ни одной цифры (кроме правого элемента). Если такая строка появилась- значит этот столбец посчитан и равен значению правого элемента.

3.2 Основной цикл - имитирует подстановку как при решении системы. Берем нужную строку (соответствует номеру элемента из которого мы движемся А. Надо из первого- берем первую строку)
И сканируем ее слева на право (наверно ничо не изменится и если с права на лево ))) )
Если там -1 (то есть ничего), переходим к следующему элементу строки. До тех пор, пока не найдем цифру. Она находится на месте X в строке. Тогда мы берем строку X и подставляем ее в текущую. А как-

Мы сканируем строку X, берем цифру из нее, складываем с цифрой из своей строки на месте X и записываем ее в свою строку на то место, в котором она была в строке X- но только при условии что новое значение меньше текущего. Если в строке X на этом месте -1, переходим к следующему элементу строки X. И так пока строка X Не кончится. Потом возьмем его правый элемент, сложим все с тем же числом из своей строки и если оно меньше, чем то что есть в последнем элементе нашей строки- запишем его на его место. После чего вычеркнем из своей строки то число что было на месте X. И так пока наша строка не кончится.

А когда наша строка кончилась- смотрим не осталось ли в ней цифр? Дело в том что они могут в ней появляться по ходу работы алгоритма.

Если там еще цифры есть- то повторяем все с пункта 3.

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

В итоге мы получаем в нашей строке в правом элементе некое число- оно и есть наша искомая минимальная стоимость ))

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

Но это мы нашли стоимость минимальную... А найти список вершин по этому пути- сложнее. Я пока не придумал стабильного способа это сделать. Но думаю скоро он будет найден. Все основывется на том, какие строки мы подставляем в текущую.. Подстановка строки в нашу- это переход на эту вершину, с номером строки которую подставляем. Следовательно за это можно цепляться.

Но бывает ситуация что он пробует несколько путей и поэтому все эти элементы попадают в путь. Я сделал некоторые фильтры там. Типа что если подстановка строки не изменила текущую (например записывала число большее чем у нас уже есть) но значит алгоритму эта вершина не понравилась и в путь ее не включаем. Так же не включаем в путь вершины, давшие в нашей строке только диагональный элемент. И другие. Но все равно если путь длинный в него попадают лишние вершины. Видимо надо сделать как-то не сразу запись в путь, а хранение сначала вершины в буфуру временном. Если ничего лучше нее не найдено- то уже копируем ее в путь, иначе заменяем лучшей.

Вот... Если у кого-то хватило сил прочитать этот бред до конца, то могу еще и код программы реализующей все это дать на Perl'е

Код


#!/usr/bin/perl

use strict;

#################################################### For write by user #############################
#my $Matrix = [
#    [-1,  -1,   5,  -1,  -1],
#    [ 4,  -1,  -1,  -1,  -1],
#    [-1,  -1,  -1,   2,  -1],
#    [-1,   3,  1,  -1,  -1],
#    [-1,  -1,   3,   2,  -1]
#];

#my $Matrix = [
#    [-1,  3,   -1,  -1,  8],
#    [ -1,  -1,  11,  -1,  -1],
#    [-1,  -1,  -1,   2,  -1],
#    [7,   -1,  10,  -1,  9],
#    [3,  -1,   -1,   -1,  -1]
#];

#
#my $Matrix = [
#    [-1,   -1,    3,    7,   -1,   -1, -1,  -1, -1,  -1],
#    [4,    -1,   -1,    -1,   7,    2, -1,  -1, -1,   4],
#    [-1,   -1,   -1,     2,  -1,   -1, -1,  -1,  3,  -1],
#    [-1,    4,   -1,    -1,  -1,   -1, -1,  -1, -1,  -1],
#    [-1,   -1,   -1,     3,  -1,   -1, -1,  -1, -1,  -1],
#    [-1,   10,   -1,    -1,   9,   -1, -1,   7, -1,  -1],
#    [-1,   -1,   -1,    -1,   1,   -1, -1,   3, -1   -1],
#    [-1,   -1,   -1,    -1,   9,   -1, -1,  -1, -1,  -1],
#    [-1,   -1,   -1,     4,  -1,   -1,  2,  -1, -1,  -1],
#    [ 4,   -1,    3,    -1,  -1,   -1, -1,  -1, -1,  -1]
#];

my $Matrix = [
    [-1,  -1,  -1,  2,  4],
    [-1,  -1,  -1,  -1,  4],
    [4,  3,  -1,  -1,  -1],
    [3,  -1,  3,  -1,  -1],
    [7,  6,  -1,  3,  -1]
];


my $From = 1;
my $To   = 2;

###################################################################################################
my @Way = ();
my $N = @{$Matrix};
my $Data = [];

for my $i (0..$N-1){ # Подписываем последний элемент к строкам, который обозначает что мы ищем
    @{$Data->[$i]} = @{$Matrix->[$i]};
    push @{$Data->[$i]}, $i == $To-1 ? 0 : 'Inf';
}

my @FoundedVars = ('No') x ($N+1);
my @UsedVars = ('No') x ($N+1);
Main();


sub Main {
    # 1. Находим строку с нулем и очищаем ее. Вписываем в массив $FoundedVars соотв. данные
    for my $i (1..$N){
        if (Get($N+1, $i) eq 0){
            for my $j (1..$N){
                Set ($j,$i,-1,1); # Перезаписываем на -1. Не сравнивая ни с чем.
            }
            $FoundedVars[$i] = 0;
            last;
        }
    }
    
    while (Uncomplete()){
        # 2. Подставляем переменные и удаляем диагональные эл-ты
        MatrixService();
        
        # Начинаем сканировать строку, подставляя в нее все, что нужно
        for my $i (1..$N){
            my $CurrentValue = Get($i, $From); # Смотрим что написано в ней на текущей позиции
            if ($CurrentValue != -1){ # Если там есть число- нужно подставить эту строку, сложив с текущим значением
                # Сотрем значение на том месте, какую строку подставляли в эту
                Set($i, $From, -1, 1); # Не сравнивая
                last if $UsedVars[$i] ne 'No'; # Если эта переменная уже подставлялась- пропускаем
                # Подставляем эту переменную
                my $Change = 0; # Служит флагом модификации
                for my $nINsecond(1..$N){ # Проходим по всей строке, которую подставляем
                    my $ValueInSecond = Get($nINsecond, $i);
                    if ($ValueInSecond != -1){
                        $Change = 1 if Set ($nINsecond, $From, $ValueInSecond+$CurrentValue); # Подставляем сравнивая
                    }
                }
                # Подставим последнее значение строки
                my $Temp = Get($N+1,$i);
                $Change = 1 if SetLast($From, $Temp eq 'Inf'? 'Inf' : $Temp+$CurrentValue);
                push @Way, $i if $Change; # Если была модификация- заносим этот эл-т в путь
                $UsedVars[$i] = 1; # Зписываем что использовали эту переменную
            }
        }
    }
    
    print 'Min way: ' . Get($N+1,$From) . "\n";
    print 'Points between From ant To: ' . join(',',@Way);
}


########################################### Functions ##############################################

sub Uncomplete {
    for my $i (0..$N-1){
        return 1 if ($Data->[$From-1]->[$i] != -1); # Нужное  значение еще не найдено- в этой строке присутствуют данные
    }
    return 0;
}

sub Get {
    my ($x, $y) = @_;
    
    my $temp =  $Data->[$y-1]->[$x-1];
    return $temp;
}


sub Set {
    my ($x, $y, $value, $NoCompare) = @_;
    
    if ($NoCompare){ # Не сравнивая
        $Data->[$y-1]->[$x-1] = $value;
    } else {
        return 0 if $x == $y; # Не заносим диагональные эл-ы
        return 0 if $UsedVars[$x] ne 'No'; # Если эта переменная уже использовалась- не подставляем ее
        my $CurrentValue = Get($x, $y);
        if ($CurrentValue == -1){
            $Data->[$y-1]->[$x-1] = $value;
            return 1; # Была модификация
        } else {
            if ($value < $CurrentValue){
                $Data->[$y-1]->[$x-1] = $value;
                return 1; # Была модификация
            } else {
                return 0; # Не было модификации
            }
        }
    }
}

sub MatrixService { # Сервисная функция, удаляет диагональные эл-ты и подставляет наденные переменные, Определяет что найдены новые переменные
    for my $i (1..$N){ #Находим и удаляем элементы с диагонали
        if (Get($i,$i) ne '-1'){
            Set($i, $i, -1);
        }
    }
    
    for my $Num (1..$N){ # Проходим по всем переменным
        if ($FoundedVars[$Num] ne 'No'){ # Если эта переменная уже была найдена
            for my $i (1..$N){ # Проходим по вертикали по матрице
                my $CurrentValue = Get($Num, $i);
                if ($CurrentValue != -1){ # Считываем значения, и если там есть число
                    Set($Num, $i, -1, 1); # Стираем его
                    SetLast ($i, $FoundedVars[$Num] + $CurrentValue); # Устанавливая значение последней цифры столба в сумму переменной и поля (Внутри функции происходит сравнение)
                    push @Way, $Num if ($From == $i);
                }
            }
        }
    }
    
    # СМотрим не нашлись ли новые переменные
    for my $i (1..$N){
        if ($FoundedVars[$i] eq 'No'){ # Если такой переменной еще нет
            # Проходим по строке, смотря не найдена ли новая переменная
            my $OK = 1;
            for my $j (1..$N){
                 if (Get($j, $i) != -1){ # Если в строке не пустое значение- выходим. Эта строка не есть найденная переменная
                    $OK = 0;
                    last;
                 }
            }
            $FoundedVars[$i] = Get($N+1, $i) if $OK; # Устанавливаем новую найденную переменную
        }
    }
}


sub SetLast { # Процедура установки последнего значения строки. Производит сравнивание
    my ($y, $value) = @_;
    my $Getter = Get($N+1, $y);
    
    return 0 if ($value eq 'Inf');
    if ($Getter > $value or $Getter eq 'Inf'){ # Если новое значение меньше предыдущего
        Set($N+1, $y, $value, 1); # Записываем новое ничего не сравнивая
        return 1;
    }
    return 0;
}

Добавлено через 8 минут и 19 секунд
Вообще мне надо это все для нахождения транспортных маршрутов... В масштабах города москвы... Метро, все автобусы, маршрутки, троллейбусы, трамваи...

Поэтому тут не плохо бы как-то так сделать, что бы программа понимала что есть маршруты и пересадки. Чтобы поменьше пересадок давала, чтобы не гоняла то в метро, то на трамвай и т.д.

rcdimon

Дата 22.7.2008, 20:21 (ссылка)

(нет голосов)

Загрузка ...

Опытный

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

Репутация: нет
Всего: 2

Я тут подумал что алгоритм А* очень бы мне подошел. Но не знаю как определить H - Эвристическая оценка расстояния от рассматриваемой вершины к конечной. Подскажите пожалуйста какие ни будь варианты H для транспортной сети

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »