Здесь будем учиться прокладывать сухопутные дороги, дающие самый большой выигрыш по сокращению дистанций.
Дорога между двумя пунктами[]
Задача поиска минимальной дороги между двумя пунктами является тривиальной и в нашем случае легко решается алгоритмами поиска в ширину. Чтобы понять суть этого алгоритма в случае прокладывания дорог между двумя городами представьте, что вся карта уже застроена мостами (если они открыты) и дорогами (доступными с текущими науками) где только возможно. Чтобы найти оптимальный путь и траекторию между городами А-Б расположим в городе А бесконечное количество юнитов, имеющих одинаковую скоростью (для примера возьмем рабочих) и условно прикажем им расходиться в разные стороны. На каждой клетке, куда доходят группы рабочих, они останавливаются, если на всех соседних клетках рабочие (в том числе других групп) уже побывали; или идут дальше (в не посещенные никем клетки), разделившись на новые группы поменьше (но все еще бесконечно большие). Если в итоге таких нехитрых операций все рабочие остановились и города Б так и не достигли, тогда сухопутного пути А-Б попросту не существует. Если до города Б все же дошли, тогда маршрут, который прошла группа (или группы, так как их может быть несколько) является оптимальной траекторией (с точки зрения дистанции), а время, которое они затратили - минимальной дистанцией (скорость рабочего одна клетка в час), при этом дороги на пути следования дошедшей группы нужны, а на остальных клетках - нет. У компьютера этот фокус выходит легко и быстро, для человека однако такой поиск пути сильно затратен по времени (да и легко ошибиться). Поэтому практически используется другой метод. "На глаз" выбираются предполагаемые оптимальные траектории, потом каждая из них считается и выбираются реально оптимальные. Но тут нужно хорошо оценивать "на глаз".
Дорога между несколькими городами[]
Это тот случай, когда проще один раз показать, чем объяснить. Но мы все же попробуем.
Поставим себе задачу соединить несколько городов оптимальными дорогами (по дистанции), да еще при этом потратить минимальное количество ресурсов. Для объяснения воспользуемся примером, который изображен правее. Тут домики - города, треугольник - гора, а все остальное - равнина. Попробуйте самостоятельно проложить дороги между городами так, чтобы максимально сократить дистанции, при этом построив минимум дорог. Запомните свой результат.
А теперь проложим их правильно.
Пример.
Для этого нам понадобится начертить все маршруты оптимальных дорог между всеми городами. Выглядеть это будет примерно как на рисунке слева снизу. Тут синие штрихи - дорога 1-2 и 2-1 соответственно (в этом простом примере любая короткая дорога А-Б является короткой и для Б-А)
План
, зеленые для 1-3, черные для 1-4, коричневые для 2-3, фиолетовые для 2-4 и желтые для 3-4. Эта зарисовка (которую мы назовем План) нам понадобится в дальнейшем.
Будем делать следующие шаги, пока наш План не станет чистым (объяснение этих шагов на примере будет далее, так что не пугайтесь):
Шаг 1: Проложить все короткие дороги, если они единственные, или уже частично проложены (больше чем остальные короткие дороги)
Шаг 2: Если первый шаг проложил хотя бы одну дорогу, возвращаемся к первому шагу.
Шаг 3: Стереть с плана все зарисовки для уже проложенных дорог.
Шаг 4: Построить самый частовстречаемый (любой, если их несколько) кусок дороги.
Шаг 5: Вернутся к шагу один
Теперь для нашего примера.
На шаге один мы найдем две единственно возможные короткие дороги на плане. Это дороги 1-2 (синий
пунктир на плане) и 2-3 (коричневый). Проложим их и получим следующую застройку дорог (как справа).
Потом шаг два отправит нас на шаг один (так как шаг один проложил новые дороги).
На первом шаге мы прокладываем дорогу 1-3 используя уже проложенный кусочек дороги 1-2. (То есть, из всех коротких путей, путь 1-2 оказывается более отстроенным, чем остальные). Получим картинку как на следующей картинке справа.
Затем второй шаг опять заставит нас повторить шаг один, но первый шаг не даст никакого результата и поэтому, пропустив первый и второй шаг, мы переходим к шагу три.
На шаге три мы стираем все зарисовки для уже проведенных дорог. То есть синий пунктир для 1-2, коричневый для 2-3 и зеленый для 1-3. Результат должен получится как на картинке слева (для наглядности на план иногда будут нанесены отмеченные дороги).
Перейдя к шагу четыре нам необходимо выбрать самый частовстречаемый участок дороги в плане. В нашем случае это участки, которые встречаются два раза. У нас четыре таких участка. Один черно-фиолетовый (справа вверху от города 4) и три желто-фиолетовых (снизу справа от города 4) . Возьмем черно-фиолетовый участок и построим его. Получим ситуацию как на картинке справа.
Перейдя к шагу пять, мы вернемся к шагу один.
На первом шаге мы обнаружим, что мы способны найти один короткий путь 2-4 который уже содержит уже два участка дороги (среди них построенный на шаге 4 участок), что больше, чем содержат другие короткие пути на плане. Нарисовав его и не обнаружив больше никаких коротких дорог, имеющих преимущество застройки перед своими собратьями, мы получим следующую картинку справа.
Затем безрезультатно пройдясь по шагам два один и снова два мы перейдем к шагу три, который скажет вычеркнуть из плана новопроложеный путь 2-4. Получим примерный результат как на картинке слева
.
Шаг четыре говорит построить еще один частовстречаемый участок. Так как теперь у нас все участки встречаются по одному разу, то выбираем любой.
При дальнейшем исполнении шагов, дойдя к шагу 4 несколько раз, мы получим, например, следующую хронологию картинок.
После этого наш план опустеет, что будет означать, что все дороги проложены . В итоге мы проложили 18 участков дороги. А теперь вспомните, сколько проложили Вы в начале. Если столько же и условия задачи соблюдены, тогда можете про себя тихо порадоваться. Для закрепления полезно посмотреть, к чему приведут дороги с выбранных других наиболее востребованных участков.
Несколько комментариев:[]
1) Различные ландшафты (месторождения, холмы и реки) следует учитывать при составлении плана дорог. Алгоритм от этого не меняется.
2) В план легко можно включать уже существующие на карте дороги.
3) Если короткие дороги А-Б и Б-А это разные дороги, то это нужно учесть в плане (нарисовав разными цветами обе четких коротких дороги).
4) Если какие-то города не требуют соединения (например, пром города) тогда они просто не соединяются в плане.
5) Советую сразу присмотреться к тому, как будет меняться дорожная сетка после изучения наук, дающих новые дороги и мосты.
6) Короткая дорога не значит самая лучшая. Экономике дорог будет посвящена следующая наша статья.
Статья НЕ ОКОНЧЕНА. не редактируйте пожалуйста.
Хорошо не будем.