Оптимальный алгоритм поиска пути в матрице, который не полностью помещается в память

Question

Я столкнулся с трудной проблемой:

Представьте, что у меня есть карта всей страны, представленная огромной матрицей Клеток. Каждая клетка представляет собой 1 квадратный метр территории. Каждая ячейка представлена ​​в виде значения double между 0 и 1, которое представляет стоимость обхода ячейки.

Карта явно не помещается в память.

Я пытаюсь обдумать способ вычисления оптимального пути робота от начальной точки до конечной позиции. Первой идеей было создать движущееся окно, похожее на TCP, с миникартой реальной карты вокруг движущегося робота и выполнением там алгоритма A *, но я столкнулся с некоторыми проблемами с картами с огромными стенами, плохо поиск путей и т.д ...

Я ищу литературу об A * -подобных алгоритмах и не могу представить себе приблизительное решение, которое было бы хорошим решением для этой проблемы.

Мне интересно, сталкивался ли кто-то с подобной проблемой или может помочь с идеей возможного решения!

Заранее спасибо:)

Answer 1

Имеет ли ваша проблема какую-либо особую структуру, например, имеет ли место неравенство треугольника / можете ли вы гарантировать, что кратчайший путь не будет двигаться назад и вперед? Вы хотите выполнить запрос много раз? (Если это так, вы можете выполнить предварительную обработку, которая будет амортизировать несколько запросов.) Вам нужно точное минимальное решение, или что-то в эпсилон-факторе будет в порядке?

Одна мысль заключалась в том, что вы можете укоротить матрицу - сформировать квадраты размером 100 на 100 метров и определить кратчайшие расстояния через 100 \ 100 квадратов. Теперь это уместится в памяти (около 1 гигабайта), вы можете запустить Dijkstra, а затем расширить каждый шаг через квадрат 100 \ х 100.

Кроме того, вы пытались запустить прямую-обратную версию алгоритма Дейкстры? Т.е. развернитесь от источника и одновременно ищите приемник и остановитесь, когда будет пересечение.

Кстати, зачем вам такой высокий уровень детализации?

Answer 2

Вот некоторые идеи, которые могут работать

Вы можете смоделировать свой путь как кусочно-линейную кривую.Если у вас есть 31 отрезок, то ваша кривая полностью описана 60 числами.У каждой из возможных кривых есть стоимость, поэтому стоимость является функцией в следующей форме

стоимость (x1, x2, x3 ..... x60)

Теперь ваша проблема заключается внайти глобальный оптимум функции 60 переменных.Вы можете использовать стандартные методы для этого.Одна идея состоит в том, чтобы использовать генетические алгоритмы.Другая идея состоит в том, чтобы использовать метод Монте-Карло, такой как параллельный отпуск

http://en.wikipedia.org/wiki/Parallel_tempering

Когда у вас есть многообещающий путь, вы можете использовать его в качестве отправной точки, чтобы найти локальный минимумфункция стоимости.Возможно, вы можете использовать некоторую интерполяцию, чтобы сделать вашу функцию стоимости дифференцируемой.Затем вы можете использовать метод Ньютона (или, скорее, BFGS), чтобы найти локальные минимумы функции стоимости.

http://en.wikipedia.org/wiki/Local_minimum

http://en.wikipedia.org/wiki/BFGS

Ваша проблема чем-то похожа на проблему поиска путей реакции в химических системах.Возможно, вы можете найти вдохновение в книге Дэвиса Уэльса «Энергетические пейзажи».

Но у меня также есть несколько вопросов:

• Необходимо ли вам найти оптимальный путь,или вы просто ищете путь, который подходит?
• Сколько у вас под рукой компьютера и времени?
• Может ли робот делать крутые повороты или вам нужно дополнительное физическое моделирование?улучшить функцию стоимости?

Answer 3

Поскольку я не знаю точных данных, вот некоторая информация, которая может быть полезна:

• Частичный путь кратчайшего пути сам по себе является кратчайшим путем.Т.е. вы можете разбить свою матрицу на подматрицы и найти там (все) кратчайшие пути.Обратите внимание, что вам не нужно хранить все результаты: например, вы можете сэкономить память, сохранив не полный путь, а только информацию: путь идет от A до B.Промежуточные узлы могут быть вычислены позже снова или сохранены в файле для дальнейшего использования.Возможно, вы даже сможете предварительно рассчитать несколько кратчайших путей для определенных областей.

• Другой подход заключается в том, что вы можете каким-то образом сжать свою матрицу.Т.е. если у вас есть большие области, состоящие только из одного и того же числа, было бы хорошо хранить только это число и размеры этой области.

• Другой подход (в связи с предварительным вычислениемнекоторые кратчайшие пути), чтобы генерировать различные уровни детализации вашей карты.Рассматривая карту США, это может выглядеть следующим образом: самый грубый уровень детализации содержит только города Нью-Йорк, Лос-Анджелес, Чикаго, Даллас, Филадельфия, Хьюстон и Феникс.Чем мельче уровни, тем больше городов они содержат, но, с другой стороны, они показывают меньшую площадь всей вашей карты.