По умолчанию в посте идут рассуждения, актуальные для игры 2-3 игроков (используется только один путь на «двухпутных» перегонах)
Из предыдущих наработок будет использоваться только таблица «количество ходов для строительства перегона длиной N»:
Поиск самого «выгодного» пути
Как показывает практика игры и комментарии уважаемых участников, самый короткий путь между двумя городами — не всегда самый выгодный (если быть предельно честным, то почти никогда). Попробуем найти путь у которого соотношение «заработанные очки / потраченные ходы» было бы максимальным.
— Длина (количество затраченных вагонов) не превышает 45 (максимум возможных вагонов)
— Каждый город может быть использован только один раз (петли не рассматриваются).
Всё это реализовано при помощи стандартного поиска «в глубину».
2. Из всех возможных «трасс» выбирается та, для которой соотношение
(Очки за перегоны + Очки за маршруты) / (Количество затраченных ходов)
является наибольшим.
Алгоритм оказался довольно медлительным, для каждой карточки маршрута он «шерстил» все возможные варианты около полутора минут, отъедая при этом 3 гигабайта ОЗУ.
Самые «выгодные» маршруты и трассы для них
Результаты выполнения алгоритма выдавали порой совершенно «нелогичные» на человеческий взгляд результаты. Например, маршрут «Лондон-Берлин» (7 очков), компьютер предлагает построить таким образом: «Лондон-Дьеп-Париж-Марсель-Рим-Палермо-Смирна-Константинополь-Бухарест-Будапешт-Киев-Варшава-Берлин» (в среднем 101 ход; 81 очко за построенные перегоны).
Как говорил мой дед-фронтовик: «Из Киева через Пензу, на Житомир»
После того, как сформирован список самых «выгодных» маршрутов, можно переходить к следующим этапам вычислений.
Поиск самых загруженных городов
Как и в прошлый раз, для каждого города было подсчитано количество маршрутов, в которых он участвует (в качестве конечной станции и в качестве промежуточной). «Загруженность» считалась как разность путей от города/к городу и количества маршрутов.
Самые загруженные города
Самые «свободные» города
При подсчёте загруженности городов, учитывалось только количество перегонов, подходящих к городу, количество путей в перегоне (один или два) игнорировалось. Соответственно, цифры более-менее актуальны для игры вдвоём или втроём. Ну и… сами по себе приведённые таблицы не несут никакой полезной информации, разве что помогут выбрать с какого города начать строительство при прочих равных условиях. Гораздо важнее информация по перегонам.
Самые загруженные перегоны
Как и в прошлый раз, были проанализированы наиболее «выгодные трассы», было подсчитано использование перегонов в них, вне зависимости от направления движения (то есть, перемещения вида «Лондон-Эдинбург» и «Эдинбург-Лондон» считаются как движения по одному и тому же перегону).
Самые загруженные перегоны, их нужно занимать в первую очередь
Перегоны, которые не использовались для прокладывания маршрутов
В комментариях к прошлой записи, pproger и g000phy писали, что для победы в игре следует использовать перегоны длиной 8 и 6 вагонов. Как и предполагалось, 6-вагонные перегоны «Киев-Будапешт» и «Палермо-Смирна», а также подъездные пути к ним находятся вверху таблицы «самых загруженных». Неожиданно, но «Стокгольм-Петроград» оказался внизу рейтинга Top-10. Видимо, сказывается его отдалённость от основных маршрутов и большое количество вагонов, которые следует затратить на строительство.
Тепловая карта. Чем дальше от зелёного, тем более загружен данный перегон/город. Белым отмечены неиспользуемые пути
Перегоны высочайшего приоритета
В комментариях к предыдущей записи woozle написал про ключевые перегоны, незанятие которых приведёт к повышенному расходу вагонов и ходов (яркий пример — перегон «Харьков-Ростов» для восточного сегмента).
По процессу поиска этих перегонов хотелось бы попросить совета у уважаемого сообщества. Алгоритм поиска мне видится следующим:
- Количество ходов, необходимых для строительства каждого маршрута суммируется (получается некоторый эталон).
- Из матрицы путей поочерёдно исключается каждый перегон. Снова считается сумма ходов, затраченных на каждый маршрут.
- «Важность» каждого перегона считается как разность между затраченными ходами при удалённом перегоне и эталоном.
На текущий момент под рукой есть два варианта «трассы» для каждого маршрута:
- Маршрут от точки А до точки В за наименьшее количество ходов. Алгоритм описан в прошлой статье, результат расчёта важности приведён ниже:
В списке не указан «Эдинбург-Лондон» (если один игрок построит вагоны на данном перегоне, второй будет ставить станцию или останется с незаконченным маршрутом). Важность перегонов «Копенгаген-Эссен», «Стокгольм-Копенгаген» и «Харьков-Ростов» тоже очевидна, а вот остальные в списке вызывают сомнение… - Маршрут из точки А до точки В с наибольшим соотношением «количество полученных очков / количество затраченных ходов». Для этого случая критические перегоны не считались по двум причинам. Во-первых, долго (90 перегонов * 46 маршрутов * 1.5 минуты на подсчёт). Во-вторых, проложенные «трассы» маршрутов дают такие «кругали», что в большинстве своём вряд ли будут использоваться в реальной игре.
Собственно, поиск «ключевых» перегонов упирается в набор первичных данных (список логично построенных маршрутов). Этих «логично построенных маршрутов» под рукой нет, нет и идей — как их найти. Буду признателен за мысли и предложения.
Продолжение (станции, самый длинный путь) следует…
Источник
