|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Pavel Girnov 2:5066/18.66 13 Jul 2001 11:12:14
To : Aleksey V. Vaneev
Subject : Поиск пути (хитрый ;)
--------------------------------------------------------------------------------
AV> Hо необходимо сделать поиск пути в геометрическом 2D пространстве с
AV> наличием карты высот. В самом пространстве существуют прямоугольники
AV> (произвольно ориентированные), а также окружности. Поиск пути нужно
AV> осуществлять для объектов обоих видов. Проблем-то, вроде бы, и нет -
AV> лучевой алгоритм использовать можно. Hо хочется ввести в этот алгоритм
AV> стоимость пути. Вот как тут быть? Что нужно добавить в лучевой
AV> алгоритм, чтобы стоимость пути отражалась, чтобы алгоритм не тащил
AV> объект в гору, когда это дорого, а пускал его в обход?
Вариант такой:
Имеем "горную поверхность"
Hаходим "вершины гор" (максимумы функций)
Строим сетку соединияющие "вешины"
В каждой ячейке находим "низину" (точку минимуа, должна быть одна (??вроде), и
не обязательно точку - линию, плоскость).
Hаходим все пути соединяющие "низины" и их цену, заносим в табличку
По таблице, расматривая все суммы, находим путь с минимальной стоимостью.
Или можно рассмотреть пути внутри ячейки соединяющие минимумы на линии
соединяющие две вершины, ограничивающие ячейку.
вабще весь алгоритм "высосан из пальца" за 30 минут, так что можешь н не
обращать внимания :)
Да и в мелочах проработать надо.
С уважением, Господин ПЖ
--- УТВЕРЖДАЮ. [ПШГ-РУЛЕЗ]
* Origin: Бывают сны, как говорил дедушка Фрейд. Просто сны! (2:5066/18.66)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Поиск пути (хитрый ;) 
