Алгоритм поиска пути

Я работаю над проектом, цель которого состоит в том, чтобы найти способ с меньшими затратами времени отправить X муравьев из точки A в точку B с ограничением, что только один муравей за раз может стоять на «промежуточных платформах» - не надо. Я не знаю, как сказать это по-английски - за исключением пунктов А и Б.

Я уже смотрел на такие алгоритмы, как A * или Dijkstra, но они сосредоточены только на кратчайшем пути, чтобы добраться из точки A в точку B, что в некоторых случаях не является лучшим, так как вы бы предпочли выбрать 2 более длинных пути. и отправить больше муравьев за один ход.

И вот где ты мне нужен. Вы знаете такой алгоритм?

Надеюсь, я прояснил свой вопрос и с нетерпением жду ответов. Спасибо.

РЕДАКТИРОВАТЬ: Вот пример того, где A * не будет работать:

-L-M-N-O-P-S-T-U-V-W-X-Y-Z--|    Going from one letter
|                  |        |    to another costs 1 turn
H-----I-----J------K        |
|                  |        |
START--A-B-C-D-E-F-G-------END

Если у меня 17 муравьев, лучший вариант - отправить 2 муравьев за раз в следующих направлениях:

  • START-H-I-J-K-W-X-Y-Z-END
  • START-A-B-C-D-E-F-G-END

а не все в START-H-I-J-K-G-END, поскольку A * предлагает как лучший вариант.


path-finding a-star
person Pyos    schedule 03.04.2013    source источник
comment
Я проголосовал за закрытие этого вопроса, потому что, поскольку вопрос стоит, вы «делаете покупки» для решения. Если вы опубликуете пример A * и объясните, в чем проблема, тогда возникнет более конкретный, SO-правильный вопрос. Предлагаю вам также добавить звездочку.   -  person martin clayton    schedule 03.04.2013
comment
Что ж, я только хочу расширить свои знания в поисках пути   -  person Pyos    schedule 03.04.2013

Ответы (2)


arrow_upward
0
arrow_downward

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

person tiridactil    schedule 03.04.2013
comment
Да, я думал об этом раньше, но у меня есть пример, когда A * может пойти не так. Я выложу это. - person Pyos; 03.04.2013

arrow_upward
0
arrow_downward

Вы можете использовать заливку. Что делает Floodfill, так это то, что он отслеживает все возможные пути и определяет лучшее решение, но вы можете определить «лучшее». Например, вы можете создать переменную общего времени, которая отслеживает время посредством рекурсии. Вы можете создать рекурсивный метод, который возвращает временную переменную, только когда она достигает B, а затем выбирает самое короткое значение.

person Morgan Hill    schedule 23.10.2016