|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Mihail S. Sidorenko 2:5030/744.237 28 Feb 2002 11:33:13
To : All
Subject : поиск кратчайшего пути
--------------------------------------------------------------------------------
Возник тут такой вопрос: есть плоскость, на которой координатами своих вершин
заданы многоугольники, как выпуклые, так и не выпуклые, не самопересекающиеся.
Также есть две точки, между которыми надо найти кратчайший путь, состоящий из
отрезков прямых (многоугольники считаются препятствиями). В идеале хотелось бы
минимизировать не длину, а некий функционал, учитывающий как длину пути, так и
количество вершин ломанной, выдаваемой в качестве результата.
Первое, что приходит в голову - разбить обрабатываемый участок плоскости на
квадратики, пометить пересекающиеся с многоугольниками как непроходимые, и затем
воспользоваться классическим алгоритмом поиска пути. Hо это, по-моему, не есть
оптимальный путь. Подскажите, есть ли чио-нибудь более совершенное.
Заранее спасибо всем ответившим.
С уважением, Mihail.
--- GoldED+/W32 1.1.4.7
* Origin: Origin here (2:5030/744.237)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
