Я работаю над моделированием настольной игры по поиску и выводу, чтобы практиковать некоторые концепции, которые я изучаю в школе.Для меня это первая попытка анализа графиков, и я был бы признателен за совет о том, какая структура данных может быть подходящей для того, что я пытаюсь сделать.
Игра, которую я моделирую, представляет собой серию~ 200 взаимосвязанных узлов, как показано ниже.Учитывая известную исходную позицию для противника (узел 84, например, на рисунке ниже), цель состоит в том, чтобы идентифицировать возможные места укрытия противника.Ход противника от 84, естественно, неизвестен.
Рис. 1 - Иллюстративный подграф с начальной позицией противника в узле 84
Первоначально это приводит к ситуациикак тот, что ниже.Учитывая, что противник начал в 84, он / она может быть только в 66, 86 или 99 после первого хода.И т. Д.
Рис. 2. Возможные локации для противника после 1, 2 и 3 оборотов (на основе графика рис. 1)
До сих пор я смоделировалсама плата как неориентированный граф - используя реализацию библиотеки ocamlgraph от OCaml.То, что я сейчас пытаюсь сделать, это смоделировать путь, пройденный противником через график, чтобы идентифицировать потенциальные местоположения противника после каждого хода.
Хотя это удобно для целей иллюстрации, представление дерева, подразумеваемоерисунок выше имеет несколько недостатков:
Во-первых, отслеживать все возможные пути через сеть не нужно (меня волнует только местоположение терминала в укрытии противника, а не выбранный путь), а также обременительно: каждый узелв среднем подключен к ~ 7 другим узлам.К тому времени, когда мы подойдем к концу 15 ходов игры, это уже много ветвей!
Во-вторых, я подозреваю, что обрезка также станет проблемой.Действительно, часть упражнения здесь заключается в том, чтобы максимально использовать ограниченную информацию о движениях противника, которая раскрывается по ходу игры.Эта информация либо утверждает, что противник «никогда не был в узле X», либо «ранее посещал узел X».
Информация первого типа (например, «злоумышленник никогда не был в узле 65») привела бы меняжелание обрезать дерево «сверху», пройдя вниз по веткам и обрезав любую ветвь, которая признана недействительной из-за раскрытой информации.
Рис. 3 - Обрезка сверху («Противник не имел никогда»Been to Node 65 ")
Информация второго типа (например," Злоумышленник посетил узел 100 "), однако, предложила бы обрезку" снизу ", чтобы отрезать любую ветвь, которая не соответствовалаинформация.
Рис. 4. Обрезка снизу (например, «Злоумышленник посетил узел 100»)
Мне кажется, что наивный подход к дереву был быГрязное предложение, поэтому я подумал, что буду просить любые предложения или советы о том, как лучше использовать здесь структуру данных или как лучше подойти к проблеме.