Клуб Логистов | Логист.ру - Печатать страницу

Клуб Логистов | Логист.ру
https://old.logist.ru/archive/YaBB.cgi
Практика >> Информационные технологии в логистике >> Задачка: быстрый рассчет расстояния между ячейками
https://old.logist.ru/archive/YaBB.cgi?num=1222689588

Сообщение написано Рубанов Сергей 29.09.2008 :: 15:59:48

Заголовок: Задачка: быстрый рассчет расстояния между ячейками
Создано Рубанов Сергей 29.09.2008 :: 15:59:48

Задачка: быстрый рассчет расстояния между ячейками

Дано:

Есть массив ячеек с координатами (для простоты X,Y)
Есть возможность предварительно разово подготовить промежуточные данные (ввести проходы, ряды, группы и т.п.)

Нужно:

Быстрый алгоритм поиска некого физического расстояния (с учетом стен и проходов) между одной заданной ячейкой и массивом других ячеек (т.е. фактически расстояние рассчитывается в одном запросе).

При этом рассчитывать выделенным алгоритмом (например, методом волны от точки до точки) расстояние между двумя ячейками слишком накладно.
Также нестоит сводить задачу к вычитанию рейтинга одной ячейки из другой т.к. это не учитывает возможность к ячейке подойти разными путями.

Заголовок: Re: Задачка: быстрый рассчет расстояния между ячей
Создано Соломатин Владимир 29.09.2008 :: 16:11:28

:-?
Первое что приходит на ум - это соединить эти точки и назвать эту прямую "производной".
Потом взять интеграл и поиграться с произвольным коэффициентом.

Заголовок: Re: Задачка: быстрый рассчет расстояния между ячей
Создано Соломатин Владимир 29.09.2008 :: 16:54:27

Хотя, придется рисовать не одну производную....
Наверное плохое решение и сложное.
Будут идеи - подкину.

Заголовок: Re: Задачка: быстрый рассчет расстояния между ячей
Создано Плужников Сергей 29.09.2008 :: 20:00:45

Первое что приходит на ум :

система не стабильна :o

Заголовок: Re: Задачка: быстрый рассчет расстояния между ячей
Создано Соломатин Владимир 29.09.2008 :: 21:43:00

Плужников Сергей wrote:

Первое что приходит на ум :

система не стабильна :o

:)
Да, с адронным коллайдером шутки плохи.

Заголовок: Re: Задачка: быстрый рассчет расстояния между ячей
Создано Соломатин Владимир 30.09.2008 :: 10:36:34

:-?
Неплохой пример с исходниками и описанием алгоритмов.
http://robot.paccbet.ru/docs/robot_path.php

Заголовок: Re: Задачка: быстрый рассчет расстояния между ячей
Создано Рубанов Сергей 30.09.2008 :: 10:51:05

Соломатин Владимир wrote:

:-?
Неплохой пример с исходниками и описанием алгоритмов.
http://robot.paccbet.ru/docs/robot_path.php

Ответ не отвечает условием задачи:

При этом рассчитывать выделенным алгоритмом (например, методом волны от точки до точки) расстояние между двумя ячейками слишком накладно.

Еще раз повторяю - есть текущая точка (например, где мы находимся - центр склада).
Есть множество ячеек которые мы должны посетить. Теперь нужно ОЧЕНЬ БЫСТРО решить до какой ячейки нам всего ближе идти из всех N ячеек. Причем это расстояние должно учитывать припятствие и дополнительные проходы между стелажжами (которые позволяют пройти к одной и той же ячейке различными путями в зависимости откуда мы идем)

Если ячеек 100, то рассчитывает 100 раз расстояние от текущего место до каждой отдельной ячейки слишком накладно. Нужен алгоритм который позволит все это сделать за доли секунды. Видимо тут нужно вводить предварительно рассчитанные данные по неизменяемой топологии склада