ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Andrew Plyako                        2:5030/922.20  23 Oct 2002  12:29:48
 To : Vasiliy Kuntsevich
 Subject : Поиск минимального пути
 -------------------------------------------------------------------------------- 
 

 
  VK>   Hа компоненте TChart опpеделенным обpазом стpоятся
 
 [Skiped]
 
 "В правильно заданном вопросе содержится половина ответа" (цитата)
 
   Вот ты написал одно и тоже сообщение в Ru.Delphi и в Ru.Algorithms. И ни там
 ни там тебе не ответили. Как ты думаешь, почему? Люди злые? или же вопрос
 некорректный?
   По-мойму, второе. В Ru.Delphi на алгоритмические вопросы никто отвечать не
 будет; для этого есть данная эха. А здесь, после слова "TChart" половина людей
 твой вопрос дальше читать не будет, ибо справедливо сочтет его некорректным.
 
 Ибо вопрос, надо было разбить на два:
 
 1) В Ru.Algorithm спросить алгоритмическую часть:
   "Hа (прямоугольном) поле "заштрихованы" прямоугольные области; заданы две
 точки на поле, надо провести путь минимальной длины между двумя этими точками
 так, чтобы этот путь не пересекал "заштрихованные" области. Hint: на самом деле,
 штрихованные области не совсем произвольные: на поле рисуется неравномерная
 сетка, и штрихуется только одна ячейка из каждого столбца и из каждой строки -- 
 может это облегчит задачу?"
 
 2) В Ru.Delphi спросить интерфейсную часть -- как лучше отобразить такое поле
 (ибо использовать TChart для этой задачи -- извращение).
 По поводу алгоритмической части твоей задачи:
 
 все очень просто, надо
 (1) Построить граф всех возможных "движений" от исходной точки к конечной
 (2) Hайти путь минимальной длины в этом графе
 
 (1) - вершинами графа будут все вершины всех "штрихованных" прямоугольников +
 начальная и конечная точка. Для каждой пары вершин надо проверить можно ли
 провести между ними прямую (не задевая штрихованные области), если можно, то
 считаем, что в графе есть дуга соединяющая данные вершины. Hедавно помещенный в 
 эху "FAQ по геометрии" поможет тебе в этой подзадаче (проверка пересекает ли
 отрезок прямоугольник).
   С учетом "Hint" (см. мою формулировку твоей задачи), можно уменьшить
 количество вычислений. Hапример дуги соединяющие вершины одного (штрихованного) 
 прямоугольника можно не брать в расчет: можно считать, что их нет, они никогда
 не будут использованы в пути с наименьшей длинной.
 
 (2) - нахождение пути с минимальной длиной в графе -- это стандартная задача;
 решается алгоритмом Дейкстры. Сей алгоритм, если я не ошибаюсь, есть в одном из 
 местных FAQ. Если же и нет, то поиск в Google моментально выдаст тебе множество 
 описаний и реализаций этого алгоритма
 
 Удачи.
 
 Andrew
 
 ---
  * Origin: Думать безОбразно -- безобрАзно!!! (2:5030/922.20)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    <none>   Vasiliy Kuntsevich   20 Oct 2002 04:09:57   Поиск минимального пути   Andrew Plyako   23 Oct 2002 12:29:48