|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5020/1507.400 02 Mar 2002 22:10:12
To : Mihail S. Sidorenko
Subject : Re: поиск кратчайшего пути
--------------------------------------------------------------------------------
Однажды 28-Feb-02 в 10:33 Mihail S. Sidorenko (2:5030/744.237)
написал All по поводу
-=- поиск кратчайшего пути -=-
MSS> Привет, All!
MSS> Возник тут такой вопрос: есть плоскость, на которой координатами своих
MSS> вершин заданы многоугольники, как выпуклые, так и не выпуклые, не
MSS> самопересекающиеся. Также есть две точки, между которыми надо найти
MSS> кратчайший путь, состоящий из отрезков прямых (многоугольники считаются
MSS> препятствиями). В идеале хотелось бы минимизировать не длину, а некий
MSS> функционал, учитывающий как длину пути, так и количество вершин ломанной,
MSS> выдаваемой в качестве результата. Первое, что приходит в голову - разбить
MSS> обрабатываемый участок плоскости на квадратики, пометить пересекающиеся с
MSS> многоугольниками как непроходимые, и затем воспользоваться классическим
MSS> алгоритмом поиска пути. Hо это, по-моему, не есть оптимальный путь.
MSS> Подскажите, есть ли чио-нибудь более совершенное. Заранее спасибо всем
MSS> ответившим.
Я не знаю, что ты имеешь в виду под "классическим алгоритмом", подозреваю,
чть Дейкстру. Существует немало и других "классических", например, лучевой.
Проводишь отрезок прямой к цели до ближайшего препятствия, далее пытаешься
обойти препятствие с двух сторон. При нахождении "точки отрыва" пытаешься
"протянуть" путь между исходной и точкой отрыва.
Теперь в зависимости от того, что нужно, оптимальный с большой
ресурсоемкостью или близкий к оптимальному с малой, либо выбираешь ближайшую из
точек отрыва и повторяешь операцию, либо рекурсивно строишь дерево, пока не
доберешься до цели. Затем продолжаешь просмотр дерева, отсекая решения хуже
найденного.
До свидания, в 21:04 MSK
Sergey
---
* Origin: Sergiev Posad (2:5020/1507.400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
