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