|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergiy Kanilo 2:5020/400 26 Feb 2003 18:56:48
To : Vit Arsentyev
Subject : Re: Поиск кратчайшего пути
--------------------------------------------------------------------------------
"Vit Arsentyev" <Vit.Arsentyev@p9.f117.n5049.z2.fidonet.org> wrote in
message news:1046229121@p9.f117.n5049.z2.ftn...
> SK> практически лобовое решение на PIV1.8 считается около 0.1 сек
>
> Что это счкм его едят. ^^^^^^^^^
описка вышла, Pentium 4, 1.8GHz
> >> Это нормально или у меня руки кривые?
> >> Если кто знает как ускорить это хотя бы в 2-3 раза прошу помочь.
>
> SK> ну вот грязный код на С++
>
> Попробую разобраться...
> Hо лучше бы описание алгоритма.
1. отмечаем все узлы как свободные,
2. помечаем конечную точку как первый уровень,
помешаем ее в список текущего уровня
3. если в списке текущего уровня есть начальная точка,
то идем на 6, иначе
4. все свободные узлы и прилегаюшие к текущему
помечаются как следующие, c номером на 1 больше и
помешаются в список следубшего уровня
5. следующий уровень назначается текущим и продолжаем с 3
6. заносим стартовую точку в список искомого пути,
номер последнего уровня - оставшаяся длина пути
7. если текущая стартовая точка - есть конечная -
заканчиваем, иначе
8. ищем в окрестности старта точку с уровнем меньшим
текущего и передвигаем старт туда, понидаем уровень
и идем на 6
Алгоритм простейший - без весов на ребрах и без явного
построения графа, с весам и графом было бы не намного
сложнее.
Cheers,
Serge
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
