|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Vit Arsentyev 2:5049/117.9 28 Feb 2003 11:52:43
To : Mike Girkin
Subject : Поиск кратчайшего пути
--------------------------------------------------------------------------------
VA>> Hаписал я как-то прогу на вышеупомянутую тему.
MG> А я Hапример Hе совсем тебя поHял. У тебя массив типа "лабириHт"? Т.е.
MG> Проход помечеH 1, стеHа 0? Тогда волHовой алгоритм. Гораздо меHьше по
MG> времеHи должеH давать. Если у тебя просто весовой массив, то тогда чем
MG> тебе, да и всем отвечавшим Дейкстра так Hе угодил?
Расклад такой.
Есть ориентированный граф(представленный в виде обьекта).
Инфо непосредственно о графе хранится в массиве вершин типа:
GArr = array of TLinks;
TLinks = array of TLink;
TLink = Record
LinkTo : LongInt;
Value : LongInt;
End;
Дуги в общем случае произвольны.
В данном(тестируемом) случае они организованы так, что соответствуют связям
между ячейками в трехмерном массиве.
Hасчет Дейкстры - пытаюсь проверить... но судя по всему не думаю что будет лучше
чем уже реализованно у меня(принцип почти один и тот же)
Еще одна особенность: расстояние между смежными вершинами определяется
не значением GArr[i].[k].Value(это частный случай) а внешней функцией,
которой в качестве параметров передаются номера этих смежных вершин.
Как внешняя функция вычисляет путь - неважно. Главное, что она возвращает
вычисленное значение.
ЗЫ. Опечатка в прошлом письме прошла.
За 1.5с путь находится в графе, соответствующем массиву 512*512*1
Vit
--- GoldED+/W32 1.1.5-20020104
* Origin: Eins, zwei, Polizei... (2:5049/117.9)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
