Архив форума

Задачка: быстрый рассчет расстояния между ячейками
 
Дано:
 
Есть массив ячеек с координатами (для простоты X,Y)  
Есть возможность предварительно разово подготовить промежуточные данные (ввести проходы, ряды, группы и т.п.)
 
Нужно:
 
Быстрый алгоритм поиска некого физического расстояния (с учетом стен и проходов) между одной заданной ячейкой и массивом других ячеек (т.е. фактически расстояние рассчитывается в одном запросе).
 
При этом рассчитывать выделенным алгоритмом (например, методом волны от точки до точки) расстояние между двумя ячейками слишком накладно.
Также нестоит сводить задачу к вычитанию рейтинга одной ячейки из другой т.к. это не учитывает возможность к ячейке подойти разными путями.

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

Процитировано сообщение: Плужников Сергей от 29.09.2008 :: 20:00:45:

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

Процитировано сообщение: Соломатин Владимир от 30.09.2008 :: 10:36:34:

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