Поиск минимального пути

From

Andrew Plyako (2:5030/922.20)

To

Vasiliy Kuntsevich

Date

2002-10-23T12:29:48Z

Area

RU.ALGORITHMS

Hello Vasiliy.
20 Oct 02 04:09, you wrote to All:

 VK>   На компоненте TChart опpеделенным обpазом стpоятся
[Skiped]

"В правильно заданном вопросе содержится половина ответа" (цитата)

  Вот ты написал одно и тоже сообщение в Ru.Delphi и в Ru.Algorithms. И ни там ни там тебе не ответили. Как ты думаешь, почему? Люди злые? или же вопрос некорректный?
  По-мойму, второе. В Ru.Delphi на алгоритмические вопросы никто отвечать не будет; для этого есть данная эха. А здесь, после слова "TChart" половина людей твой вопрос дальше читать не будет, ибо справедливо сочтет его некорректным.

Ибо вопрос, надо было разбить на два:

1) В Ru.Algorithm спросить алгоритмическую часть:
  "На (прямоугольном) поле "заштрихованы" прямоугольные области; заданы две точки на поле, надо провести путь минимальной длины между двумя этими точками так, чтобы этот путь не пересекал "заштрихованные" области. Hint: на самом деле, штрихованные области не совсем произвольные: на поле рисуется неравномерная сетка, и штрихуется только одна ячейка из каждого столбца и из каждой строки -- может это облегчит задачу?"

2) В Ru.Delphi спросить интерфейсную часть -- как лучше отобразить такое поле (ибо использовать TChart для этой задачи -- извращение).


По поводу алгоритмической части твоей задачи:

все очень просто, надо
(1) Построить граф всех возможных "движений" от исходной точки к конечной
(2) Найти путь минимальной длины в этом графе

(1) - вершинами графа будут все вершины всех "штрихованных" прямоугольников + начальная и конечная точка. Для каждой пары вершин надо проверить можно ли провести между ними прямую (не задевая штрихованные области), если можно, то считаем, что в графе есть дуга соединяющая данные вершины. Недавно помещенный в эху "FAQ по геометрии" поможет тебе в этой подзадаче (проверка пересекает ли отрезок прямоугольник).
  С учетом "Hint" (см. мою формулировку твоей задачи), можно уменьшить количество вычислений. Например дуги соединяющие вершины одного (штрихованного) прямоугольника можно не брать в расчет: можно считать, что их нет, они никогда не будут использованы в пути с наименьшей длинной.

(2) - нахождение пути с минимальной длиной в графе -- это стандартная задача; решается алгоритмом Дейкстры. Сей алгоритм, если я не ошибаюсь, есть в одном из местных FAQ. Если же и нет, то поиск в Google моментально выдаст тебе множество описаний и реализаций этого алгоритма

Удачи.

Andrew

---
 * Origin: Думать безОбразно -- безобрАзно!!! (2:5030/922.20)