Модераторы: Poseidon
  

Поиск:

Ответ в темуСоздание новой темы Создание опроса
> [Алгоритм] Игра на орграфе 
:(
    Опции темы
Rhianin
Дата 10.4.2011, 12:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 1
Регистрация: 1.1.2010

Репутация: нет
Всего: нет



Здравствуйте.
Дана следующая задача :
В игре на орграфе два игрока поочередно накрывают белыми (соответственно, черными) фишками вершины орграфа. Игрок при своем ходе может накрыть фишкой любую из свободных вершин, хотя бы один предшественник которой накрыт фишкой противника; первым ходом белые накрывают любую вершину. Проигрывает тот, кто при своем ходе не может выставить фишку в соответствии с правилами игры. Определить, является ли начальная конфигурация игры на заданном орграфе выигрышной для белых.

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

Я так понимаю, что в данном случае нас интересуют орграфы, не имеющие вершин от которых не отходят дуги, т.к. в противном случае, белый игрок ставит на такую вершину свою фишку и выигрывает.
У меня пока что есть только одна идея решения: полный перебор всех вариантов ходов, и построение дерева игры.

В соответствии с этим есть несколько вопросов:
1. В правильную ли сторону я думаю, и является ли полный перебор и построение дерева единственным способом решения? 
        Если да, то:
                а) Как оптимальнее построить дерево? Ведь в орграфе возможно достижение одной вершины несколькими способами с равным кол-вом
                ходов, в следствии чего в дереве будут одинаковые лишние поддеревья.
                б) К примеру я построил дерево игры, как определить, какие из листьев, обозначающих победу белых, достигаются независимо от ходов
                чёрных?
        Если же нет, то:
                Прошу подсказать другой способ решения.
2. Для этой задачи орграф лучше представлять с помощью матрицы смежности?

Прошу направить на верный путь.
Заранее спасибо. smile 
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Центр помощи"

ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Несоблюдение правил может повлечь за собой самые строгие меры от закрытия/удаления темы до бана пользователя!


  • Название темы должно отражать её суть! (Не следует добавлять туда слова "помогите", "срочно" и т.п.)
  • При создании темы, первым делом в квадратных скобках укажите область, из которой исходит вопрос (язык, дисциплина, диплом). Пример: [C++].
  • В названии темы не нужно указывать происхождение задачи (например "школьная задача", "задача из учебника" и т.п.), не нужно указывать ее сложность ("простая задача", "легкий вопрос" и т.п.). Все это можно писать в тексте самой задачи.
  • Если Вы ошиблись при вводе названия темы, отправьте письмо любому из модераторов раздела (через личные сообщения или report).
  • Для подсветки кода пользуйтесь тегами [code][/code] (выделяйте код и нажимаете на кнопку "Код"). Не забывайте выбирать при этом соответствующий язык.
  • Помните: один топик - один вопрос!
  • В данном разделе запрещено поднимать темы, т.е. при отсутствии ответов на Ваш вопрос добавлять новые ответы к теме, тем самым поднимая тему на верх списка.
  • Если вы хотите, чтобы вашу проблему решили при помощи определенного алгоритма, то не забудьте описать его!
  • Если вопрос решён, то воспользуйтесь ссылкой "Пометить как решённый", которая находится под кнопками создания темы или специальным флажком при ответе.

Более подробно с правилами данного раздела Вы можете ознакомится в этой теме.

Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Центр помощи | Следующая тема »


 




[ Время генерации скрипта: 0.0499 ]   [ Использовано запросов: 21 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.