Вы можете использовать алгоритм A * . В проблеме, которую решает этот алгоритм, узел будет представлять возможное состояние всех автомобилей. Таким образом, начальный узел будет представлять начальное состояние автомобилей, а целевой узел - состояние, в котором все автомобили находятся в пункте назначения.
A * выбирает следующий узел n , свернув следующую функцию:
f (n) = g (n) + h (n)
Если нет возможных коллизий, будет только один узел n для добавления в коллекцию узлов для рассмотрения, но если есть столкновение, чтобы избежать, будут варианты (т.е. разные узлы) на выбор, каждый раз с другим набором автомобилей, которые должны ждать.
g (n) - номер итерации для этого конкретного узла. Важно понимать, что во время этого алгоритма набор рассматриваемых узлов может не все находиться в одной и той же итерации.
h (n) - эвристическая функция. Для целей этой задачи h (n) должно быть допустимым , и поэтому мы можем определить его как максимальное число итераций, которое может понадобиться каждому автомобилю (без коллизий)добраться до места назначения. h (n) дает оптимистичное количество итераций, поскольку предполагает, что дальнейших коллизий больше не будет.
Как всегда с A *, вам нужна очередь с приоритетами (например, minкуча) для хранения узлов. Он начинается только с начального узла. Затем каждый соседний узел (следующая итерация) генерируется из него и помещается в кучу. Как указывалось ранее, если нет коллизий, существует только один соседний узел для отправки. Однако, если тривиальное движение каждого автомобиля приведет к одному или нескольким столкновениям, несколько соседей могут быть рассмотрены и перенесены в кучу. Затем узел извлекается из кучи, и процесс продолжается.
Когда узел помещается в кучу, к нему должна быть добавлена одна дополнительная информация: количество итераций, чтобы добраться до этого узла. Это значение g (n) для этого узла. Когда узел назначения достигнут, решение будет возвращено.