Алгоритм поиска наиболее эффективных ходов для достижения данной точки

Question

(Это не совсем та проблема, которая у меня есть, но она изоморфна, и я думаю, что это объяснение будет легче понять другим.)

Предположим, что у меня есть множество точек в n -мерном пространстве. Используя 3 измерения, например:

A : [1,2,3]
B : [4,5,6]
C : [7,8,9]

У меня также есть набор векторов, которые описывают возможные движения в этом пространстве:

V1 : [+1,0,-1]
V2 : [+2,0,0]

Теперь, учитывая точку dest , мне нужно найти начальную точку p и набор векторов движений , которые приведут меня к dest самым эффективным способом. Эффективность определяется как «наименьшее количество ходов», а не обязательно «наименьшее линейное расстояние»: допустимо выбрать p , что дальше от dest , чем другие кандидаты, если набор ходов такой что вы можете добраться туда за меньшее количество ходов. Векторы в движениях должны быть строгим подмножеством доступных векторов; вы не можете использовать один и тот же вектор более одного раза, если только он не появится более одного раза во входном наборе.

Мой вход содержит ~ 100 начальных точек и, возможно, ~ 10 векторов, а мое число измерений ~ 20. Начальные точки и доступные векторы будут фиксироваться на протяжении всего жизненного цикла приложения, но я буду искать пути для множества различных dest точек. Я хочу оптимизировать скорость, а не память. Приемлемо, что алгоритм потерпит неудачу (не найти возможных путей к dest ).

Обновление с принятым решением

Я принял решение, очень похожее на помеченное ниже как «принятое». Я перебираю все точки и векторы и строю список всех достижимых точек с маршрутами их достижения. Я преобразую этот список в хеш <<em> dest , p + vectors >, выбирая кратчайший набор векторов для каждой точки назначения. (Также есть небольшая оптимизация для размера хеша, которая здесь не актуальна.) Последующие dest поиски происходят в постоянное время.

Answer 1

На самом деле, учитывая, что у вас есть около 10 векторов, вы можете, для данной dest точки, рассчитать только 1024 "целей" из подмножества векторов - например, каждый достижимое пространство, с информацией о том, какой набор движется туда. Это может быть «медленно» или «быстро» в зависимости от контекста (это будет нелепо быстро, если реализовано на параллельном вычислительном устройстве, таком как GPU).

Имея все наборы, которые вы получаете, вы можете намного быстрее рассчитать пути, затем вы можете выбрать точку, из которой можно добраться до dest за наименьшее количество ходов, выбирая из подмножества тех, которые либо ваш запрос, либо дальше.

(спасибо Strilanc)

Answer 2

Итак, вы хотите найти подмножество вашего набора векторов так, чтобы подмножество суммировалось с заданным значением. В одном измерении это называется проблемой подмножества сумм и является NP-Complete.

К счастью, у вас всего ~ 10 векторов, так что размер вашей проблемы на самом деле очень мал и поддается решению. Начните с того, что попробуйте все 2 ^ 10 комбинаций ходов для каждой начальной точки и выберите лучшую. Затем работайте в поисках простых оптимизаций.

Некоторые простые оптимизации, которые могут работать:

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

Answer 3

Я полагаю, что вы сможете сделать обобщенное применение алгоритма поиска пути A * (aka A star). Нет никаких причин, почему это не может быть сделано в N-ом пространстве. Он гарантирует наиболее оптимальный путь, если вы можете описать стоимость каждого хода.

http://en.wikipedia.org/wiki/A*_search_algorithm

Answer 4

Учитывая, что у вас есть начальные точки и фиксированный набор векторов, можете ли вы рассчитать список всех достижимых пунктов назначения, а затем просто найти данный пункт назначения?

Answer 5

Как утверждает Корнел, у вас есть максимум 2 ^ 10 = 1024 доступных пунктов назначения. Таким образом, вы можете просто сгенерировать все достижимые места назначения за 2 ^ N времени (где N - количество векторов) с помощью простого рекурсивного генерирования. Это будет достаточно быстро, конечно. Однако предположим, что вы хотели растянуть его.

Вы можете оптимизировать его до времени O (2 ^ (N / 2 + 1)), используя решение для встреч в середине. Вы разбиваете векторный набор на два подмножества и генерируете все доступные пункты назначения для каждого подмножества независимо. Затем вы выполняете итерацию по одному набору доступных пунктов назначения и для каждого местоположения находите разницу между ним и целевым пунктом назначения. Если этот разностный вектор находится в другом наборе достижимых пунктов назначения, у вас есть решение: объедините два, и все готово. Трудность заключается в том, чтобы эффективно запрашивать, есть ли у вас требуемый вектор в другом наборе: это можно сделать за O (1) раз, используя хеш-таблицу.

Это O (2 ^ (N / 2)) время на подмножество, умноженное на два подмножества дает O (2 ^ (N / 2 + 1)). Чтобы присоединиться к ним, настало время O (2 ^ (N / 2)). Так что это дает нам время O (2 ^ (N / 2 + 1)).

Answer 6

1. Начните с начала.
2. сделать на некоторое время
3. Получить расстояние до пункта назначения
4. Проверьте все возможные ходы и выберите тот, который приблизит вас к месту назначения за один ход.
5. end do

Это может колебаться вокруг пункта назначения, но оно приблизит вас.