Я программирую пошаговую стратегическую игру, и у меня есть особая проблема кратчайшего пути для одной пары. У меня есть взвешенный ориентированный граф с неотрицательными ненулевыми весами ребер, и вот загвоздка с несколькими путешественниками, то есть единицы с разными типами движения, путешествующие вместе как группа. Каждое ребро графика имеет разные веса для разных единиц в зависимости от типа движения.
Обычно можно было бы использовать, например. Алгоритм Дейкстраса для решения задачи о кратчайшем пути. Но когда несколько юнитов движутся вместе как группа и разные веса ребер для каждого юнита, может случиться так, что оптимальный путь не будет таким же, как оптимальный путь для любого отдельного юнита, движущегося в одиночку. Как видно снизу
с красным и зеленым, движущимися из S в D. Оптимальным путем для движения только красного будет S-A-D со стоимостью 2, а оптимальным путем для движения только зеленого будет S-C-D со стоимостью 2. В обоих случаях, однако, другой стоимость движения юнитов будет 5 и, таким образом, оптимальный путь, когда юниты движутся вместе, это S-B-D с максимальной стоимостью движения 4.
Различное количество очков движения за ход для каждого типа юнитов, по-видимому, не является проблемой, поскольку веса ребер можно нормализовать. Можно ли это сформулировать как линейную программу и решить с помощью симплексного алгоритма? Казалось бы, у нас было бы несколько целевых функций, и мы хотели бы минимизировать максимум. Но, возможно, есть более простое решение?
