Кто-нибудь пробовал решить такую задачку
Интересует не программный код ессесно, а сам метод (алгоритм) решения.
Ну первое что приходит на ум — взять любой шарик, составить для него список всех возможных путей и последовательно их проверить. Как только шар попал в дырку, брать любой из оставшихся, опять составить список всех путей до его дырки исходя из текущего (а не первоначального) положения и проверять эти пути.
Затем из первоначального состояния брать другой шарик и делать то же самое.
Но как мне кажется это не совсем рацианальный метод решения.
Господа, математики, может что подскажете.
28.01.10 19:44: Перенесено модератором из 'Алгоритмы' — Кодт
Здравствуйте, dilmah, Вы писали:
D>собеседование в CQG detected
Хотел я упомянуть про CQG, но не стал. Видимо зря.
ДА! ДА! ДА!
В начале осени прошлого года меня туда звали на собеседования и давали задачки. Но я отказался. Задач тама на самом деле 2. Кому интересно могу дать и вторую.
Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.
Здравствуйте, SullenMan, Вы писали:
SM>Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.
SM>В начале осени прошлого года меня туда звали на собеседования и давали задачки. Но я отказался. Задач тама на самом деле 2. Кому интересно могу дать и вторую. SM>Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.
ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.
Здравствуйте, blackhearted, Вы писали:
B>Здравствуйте, SullenMan, Вы писали:
SM>>Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.
B>Давайте,конечно
B>PS Я в CQG не собираюсь
SM>>В начале осени прошлого года меня туда звали на собеседования и давали задачки. Но я отказался. Задач тама на самом деле 2. Кому интересно могу дать и вторую. SM>>Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.
D>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.
Здравствуйте, SullenMan, Вы писали:
SM>Здравствуйте, dilmah, Вы писали:
SM>>>В начале осени прошлого года меня туда звали на собеседования и давали задачки. Но я отказался. Задач тама на самом деле 2. Кому интересно могу дать и вторую. SM>>>Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.
D>>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.
SM>А поподробнее идейку можно расписать?
Обычный поиск в ширину: http://en.wikipedia.org/wiki/Breadth_first_search
В качестве вершин графа — состояние игры. Ребра существуют, если возможно из одного состояния получить другое за один наклон доски. В данной игре за состояние можно взять совокупность координат шариков. Их в свою очередь можно представить в виде целого числа (шариков максимум 8, каждая координата — 2 бита). Чтобы определить, посещали ли мы уже текущее состояние, можно завести хэш-таблицу. На самом деле различных состояний будет на порядки меньше 2^32 из-за особенностей игрового поля и правил игры, поэтому должно шустро работать.
Здравствуйте, _DAle_, Вы писали:
_DA>В данной игре за состояние можно взять совокупность координат шариков.
Нельзя.
Нужно еще дырки учитывать. Ибо при попадании шарика в дырку дырку и шарик нужно удалять.
... << RSDN@Home 1.2.0 alpha 4 rev. 1305>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, _DAle_, Вы писали:
_DA>>В данной игре за состояние можно взять совокупность координат шариков. WH>Нельзя. WH>Нужно еще дырки учитывать. Ибо при попадании шарика в дырку дырку и шарик нужно удалять.
Здравствуйте, WolfHound, Вы писали:
WH>Здравствуйте, _DAle_, Вы писали:
_DA>>В данной игре за состояние можно взять совокупность координат шариков. WH>Нельзя. WH>Нужно еще дырки учитывать. Ибо при попадании шарика в дырку дырку и шарик нужно удалять.
А в чем проблема? Если у шарика такая же координата, что и у дырки, то считаем, что шарик в дырке. Координаты у дырок константные, так что никаких проблем с этим нет.
_DA>А в чем проблема? Если у шарика такая же координата, что и у дырки, то считаем, что шарик в дырке. Координаты у дырок константные, так что никаких проблем с этим нет.
не, в одной позиции могут быть 2 шарика -- один в дырке, другой сверху. Нужна еще информация кто где.
_DA>>А в чем проблема? Если у шарика такая же координата, что и у дырки, то считаем, что шарик в дырке. Координаты у дырок константные, так что никаких проблем с этим нет.
D>не, в одной позиции могут быть 2 шарика -- один в дырке, другой сверху. Нужна еще информация кто где.
Зачем? Шарик с нужным номером находится в дырке. Шарик с другим номером не может находиться в дырке по условию, мы в это состояние и переходить даже не будем. Когда мы пробуем перейти из текущего состояния, мы просто сначала проверяем, какие дырки уже закрыты, и работаем только с оставшимися шариками и дырками.
SM>>В начале осени прошлого года меня туда звали на собеседования и давали задачки. Но я отказался. Задач тама на самом деле 2. Кому интересно могу дать и вторую. SM>>Недавно разбирал хлам в документах и наткнулся на Marble Game. Любопытство взяло вверх. Прошерстил инет на предмет алгорима и ничего не нашёл.
D>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.
Т.е. я так понимаю сначала надо построить дерево.
Может подскажете как это лучше сделать?
_DA>>>А в чем проблема? Если у шарика такая же координата, что и у дырки, то считаем, что шарик в дырке. Координаты у дырок константные, так что никаких проблем с этим нет.
D>>не, в одной позиции могут быть 2 шарика -- один в дырке, другой сверху. Нужна еще информация кто где.
_DA>Зачем? Шарик с нужным номером находится в дырке. Шарик с другим номером не может находиться в дырке по условию, мы в это состояние и переходить даже не будем. Когда мы пробуем перейти из текущего состояния, мы просто сначала проверяем, какие дырки уже закрыты, и работаем только с оставшимися шариками и дырками.
да, точно. По памяти писал, сам реализовывал это в сентябре прошлого кода
D>>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.
SM>Т.е. я так понимаю сначала надо построить дерево.
там не дерево. Там граф с циклами. Ты же можешь совершить цепочку ходов и прийти в ту же позицию в которой уже был.
Во вторых, граф сразу целиком конечно не нужно строить. Нужно двигаться волной и динамически строить новые состояния в которые можно попадаешь.
Здравствуйте, dilmah, Вы писали:
D>>>ну довольно стандартная идея -- у игры есть состояния. Каждый ход (N, E, W, S) передвигает из состояния в состояние. Получается breadth-first поиск в графе состояний. Экспоненциальная сложность, понятно, в общем случае. CQG насколько я знаю ожидает именно такое решение + плюс чтобы этот breadth first search был распараллелен.
SM>>Т.е. я так понимаю сначала надо построить дерево.
D>там не дерево. Там граф с циклами. Ты же можешь совершить цепочку ходов и прийти в ту же позицию в которой уже был.
Ну я так понимаю что как раз в туже позицию ходть не надо. Иначе можно зацмклиться. Разве нет?
D>>там не дерево. Там граф с циклами. Ты же можешь совершить цепочку ходов и прийти в ту же позицию в которой уже был. SM>Ну я так понимаю что как раз в туже позицию ходть не надо. Иначе можно зацмклиться. Разве нет?
да. Я имел в виду, что сам граф состояний это не дерево. Ты идешь по нему волной как в breadth-first search, ты не ходишь на позиции в которых уже был.
Здравствуйте, SullenMan, Вы писали:
SM>Т.е. я так понимаю сначала надо построить дерево. SM>Может подскажете как это лучше сделать?
В императивных языках лучше на списках делать, а дерево в уме представлять.
Создаем два списка — просмотренные состояния и НЕ просмотренные. Берем по очереди состояния из списка непросмотренных.
Если является ответом — возвращаем ответ. Если нет, то на основе него генерируем новые состояния. Добавляем их в список не просмотренных исключая те, которые ранее были просмотрены (т.е. содержатся в списке просмотренных).
Вот то же самое, но более формально:
список_НЕпросмотренных := [начальное_состояние] // список из одного элемента
список_просмотренных := [] // пустой список
пока в список_НЕпросмотренных есть элементы
текущее_состояние := извлечь первый элемент из список_НЕпросмотренных
если текущее_состояние удовлетворяет условию задачи, то вернуть ответ
новые_состояния := сгенерировать новые состояния из текущее_состояние
для каждого состояния из новые_состояния
если оно отсутствует в список_просмотренных, то добавить его в конец список_НЕпросмотренных
конец_для
конец_пока
вернуть ответ "решения нет"
