Всё ещё продолжаю изучать основы математики и механики в игре. Данная статья является второй в серии (Ссылка на первую часть), в ней продолжается анализ перегонов, попытка их сортировки по потребности, изучение различных способов строительства маршрутов. Если проводить аналогии с математикой, это лишь основы, арифметика. Алгебра и высшая математика в духе «брать вагоны или строить перегон?», «что сейчас лучше построить — перегон или станцию?» и «использование одного перегона несколькими маршрутами» пока в стадии планов, надеюсь, руки и мозги дойдут и до них.

По умолчанию в посте идут рассуждения, актуальные для игры 2-3 игроков (используется только один путь на «двухпутных» перегонах)

Поиск самого «выгодного» пути

Как показывает практика игры и комментарии уважаемых участников, самый короткий путь между двумя городами — не всегда самый выгодный (если быть предельно честным, то почти никогда). Попробуем найти путь у которого соотношение «заработанные очки / потраченные ходы» было бы максимальным.


Алгоритм оказался довольно медлительным, для каждой карточки маршрута он «шерстил» все возможные варианты около полутора минут, отъедая при этом 3 гигабайта ОЗУ.


Самые «выгодные» маршруты и трассы для них

Результаты выполнения алгоритма выдавали порой совершенно «нелогичные» на человеческий взгляд результаты. Например, маршрут «Лондон-Берлин» (7 очков), компьютер предлагает построить таким образом: "Лондон-Дьеп-Париж-Марсель-Рим-Палермо-Смирна-Константинополь-Бухарест-Будапешт-Киев-Варшава-Берлин" (в среднем 101 ход; 81 очко за построенные перегоны).


Как говорил мой дед-фронтовик: «Из Киева через Пензу, на Житомир»

После того, как сформирован список самых «выгодных» маршрутов, можно переходить к следующим этапам вычислений.

Поиск самых загруженных городов

Как и в прошлый раз, для каждого города было подсчитано количество маршрутов, в которых он участвует (в качестве конечной станции и в качестве промежуточной). «Загруженность» считалась как разность путей от города/к городу и количества маршрутов.


Самые загруженные города


Самые «свободные» города

При подсчёте загруженности городов, учитывалось только количество перегонов, подходящих к городу, количество путей в перегоне (один или два) игнорировалось. Соответственно, цифры более-менее актуальны для игры вдвоём или втроём. Ну и… сами по себе приведённые таблицы не несут никакой полезной информации, разве что помогут выбрать с какого города начать строительство при прочих равных условиях. Гораздо важнее информация по перегонам.

Самые загруженные перегоны

Как и в прошлый раз, были проанализированы наиболее «выгодные трассы», было подсчитано использование перегонов в них, вне зависимости от направления движения (то есть, перемещения вида «Лондон-Эдинбург» и «Эдинбург-Лондон» считаются как движения по одному и тому же перегону).


Самые загруженные перегоны, их нужно занимать в первую очередь


Перегоны, которые не использовались для прокладывания маршрутов

В комментариях к прошлой записи, pproger и g000phy писали, что для победы в игре следует использовать перегоны длиной 8 и 6 вагонов. Как и предполагалось, 6-вагонные перегоны «Киев-Будапешт» и «Палермо-Смирна», а также подъездные пути к ним находятся вверху таблицы «самых загруженных». Неожиданно, но «Стокгольм-Петроград» оказался внизу рейтинга Top-10. Видимо, сказывается его отдалённость от основных маршрутов и большое количество вагонов, которые следует затратить на строительство.


Тепловая карта. Чем дальше от зелёного, тем более загружен данный перегон/город. Белым отмечены неиспользуемые пути

Перегоны высочайшего приоритета

В комментариях к предыдущей записи woozle написал про ключевые перегоны, незанятие которых приведёт к повышенному расходу вагонов и ходов (яркий пример — перегон «Харьков-Ростов» для восточного сегмента).

По процессу поиска этих перегонов хотелось бы попросить совета у уважаемого сообщества.

Алгоритм поиска мне видится следующим:

• Количество ходов, необходимых для строительства каждого маршрута суммируется (получается некоторый эталон).
• Из матрицы путей поочерёдно исключается каждый перегон. Снова считается сумма ходов, затраченных на каждый маршрут.
• «Важность» каждого перегона считается как разность между затраченными ходами при удалённом перегоне и эталоном.

На текущий момент под рукой есть два варианта «трассы» для каждого маршрута:

1. Маршрут от точки А до точки В за наименьшее количество ходов. Алгоритм описан в прошлой статье, результат расчёта важности приведён ниже:
   
   
   В списке не указан «Эдинбург-Лондон» (если один игрок построит вагоны на данном перегоне, второй будет ставить станцию или останется с незаконченным маршрутом). Важность перегонов «Копенгаген-Эссен», «Стокгольм-Копенгаген» и «Харьков-Ростов» тоже очевидна, а вот остальные в списке вызывают сомнение…
   
2. Маршрут из точки А до точки В с наибольшим соотношением «количество полученных очков / количество затраченных ходов». Для этого случая критические перегоны не считались по двум причинам. Во-первых, долго (90 перегонов * 46 маршрутов * 1.5 минуты на подсчёт). Во-вторых, проложенные «трассы» маршрутов дают такие «кругали», что в большинстве своём вряд ли будут использоваться в реальной игре.

Собственно, поиск «ключевых» перегонов упирается в набор первичных данных (список логично построенных маршрутов). Этих «логично построенных маршрутов» под рукой нет, нет и идей — как их найти. Буду признателен за мысли и предложения.

Продолжение (станции, самый длинный путь) следует...