![]() |
|
![]() ![]() ![]() |
|
SLAER |
|
|||
Новичок Профиль Группа: Участник Сообщений: 39 Регистрация: 11.7.2008 Репутация: нет Всего: нет |
Здравствуйте. Может быть кто-нибудь поможет в решении следующей задачи:
Имеется шахматная доска размером 5x5 и одна фишка в левом верхнем углу. Требуется определить количество всевозможных вариантов ее перемещения в правый нижний (противоположный) угол. Как я понимаю, решение сводится к составлению и обходу дерева вариантов, но я пока не представляю, как его составить. Если сможете, подскажите пожалуйста алгоритм. |
|||
|
||||
Akina |
|
|||
Советчик ![]() ![]() ![]() ![]() Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Два раза в одну клетку не попадать?
-------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
SLAER |
|
|||
Новичок Профиль Группа: Участник Сообщений: 39 Регистрация: 11.7.2008 Репутация: нет Всего: нет |
Попадать можно, но только избегать зацикливания
|
|||
|
||||
maxim1000 |
|
|||
![]() Эксперт ![]() ![]() ![]() ![]() Профиль Группа: Участник Сообщений: 3334 Регистрация: 11.1.2003 Где: Киев Репутация: 33 Всего: 110 |
что подразумевается под "зацикливанием"
-------------------- qqq |
|||
|
||||
SLAER |
|
|||
Новичок Профиль Группа: Участник Сообщений: 39 Регистрация: 11.7.2008 Репутация: нет Всего: нет |
ну значит, чтобы один и тот же вариант не пересматривался бесконечное число раз
Добавлено через 13 минут и 32 секунды например: если начальную позицию обозначить как [0][0], а конечную как [5][5], то из [0][0] в [5][5] мы можем добраться: [0][0]->[1][1]->[2][2]->[3][3]->[4][4]->[5][5] или [0][0]->[1][1]->[2][1]->[2][2]->[3][3]->[4][4]->[5][5] или [0][0]->[1][1]->[1][2]->[2][2]->[3][3]->[4][4]->[5][5] и т.д. т.е. вцелом пути не повторяются, но позиции могут повторяться. |
|||
|
||||
dereyly |
|
|||
Бывалый ![]() Профиль Группа: Участник Сообщений: 217 Регистрация: 16.6.2006 Репутация: 1 Всего: 4 |
Полагаю что на одну и ту же позицию нельзя вставить 2ды... иначе задача не имела бы точного решения...
А в такой постановке мне пока ничего путного не приходит в голову кроме подсчета количества решений поиска в ширину. |
|||
|
||||
polosatij |
|
|||
![]() Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1143 Регистрация: 22.2.2004 Где: Stuttgart<-> ;Karlsruhe, Germany Репутация: нет Всего: 8 |
не надо ничего считать.. задача очень простая.. и дерево тоже не надо рисовать.. смотри.. тебе надо всего лишь нарисовать "волны на доске" и перемещаться из меньшего в большее.. смотри на рисунке: 01234 12345 23456 34567 45678 ![]() ![]() |
|||
|
||||
SLAER |
|
|||
Новичок Профиль Группа: Участник Сообщений: 39 Регистрация: 11.7.2008 Репутация: нет Всего: нет |
Но в таком случае перебраны будут не все возможные варианты, я так полагаю?
Добавлено через 1 минуту и 15 секунд И подскажите пожалуйста алгоритм поиска в ширину в таком случае, а то везде пишут по разному Добавлено через 5 минут и 34 секунды Фишка может перемещаться на 1 клетку в любом направлении (по вертикали, по горизонтали и по диагонали) |
|||
|
||||
Akina |
|
|||
Советчик ![]() ![]() ![]() ![]() Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
polosatij, ты неправ. Нет ограничения на направление движения - а твой вариант допускает только движение вправо или вниз.
SLAER, дерево тут тебе не поможет - хотя бы потому, что связи узлов меняются в зависимости от пройденной части пути. Боюсь, что это таки переборная задача. Рекурсивный алгоритм перебора даст решение, пусть и неоптимальное. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
SLAER |
|
|||
Новичок Профиль Группа: Участник Сообщений: 39 Регистрация: 11.7.2008 Репутация: нет Всего: нет |
да мне и не важно, оптимальное оно или нет. Подскажите плз, как вообще этот рекурсивный алгоритм перебора реализовать? сложность и заключается в том, как перебрать все варианты.
|
|||
|
||||
Akina |
|
|||
Советчик ![]() ![]() ![]() ![]() Профиль Группа: Модератор Сообщений: 20581 Регистрация: 8.4.2004 Где: Зеленоград Репутация: 20 Всего: 454 |
Пишется рекурсивная процедура. В качестве параметров в нее передается текущее состояние доски - т.е. какие клетки в каком порядке посещены, соответственно вычисляется, какие не посещены и какая является текущей. Если текущая = концу маршрута - выводится текущий вариант обхода (или плюсуется единичка к количеству вариантов). Если текущая <> концу маршрута - процедура в цикле делает каждый из возможных ходов, и вызывает себя же, передавая себе то состояние доски, которое получается в результате сделанного следующего хода. Максимальное количество возможных ходов на каждом шаге рекурсии - 8, минимальное - 0 (загнали себя в тупик). Максимальная глубина вложенности для доски 5*5 - 24 хода, так что и стека, и памяти должно хватать. Для снижения накладнЫх расходов я бы передавал адрес текущей клетки в дополнителдьной переменной. -------------------- О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума. |
|||
|
||||
SLAER |
|
|||
Новичок Профиль Группа: Участник Сообщений: 39 Регистрация: 11.7.2008 Репутация: нет Всего: нет |
Очень признателен, попробую реализовать. Большое спасибо
Добавлено через 6 минут и 40 секунд Только возникает вопрос, как определить текущее состояние доски, и как его передать в процедуру, как массив ячеек или как то по другому? и еще, какой вложенности делать рекурсию? Добавлено через 6 минут и 57 секунд Поясните поподробнее, если не сложно |
|||
|
||||
polosatij |
|
||||
![]() Эксперт ![]() ![]() ![]() Профиль Группа: Завсегдатай Сообщений: 1143 Регистрация: 22.2.2004 Где: Stuttgart<-> ;Karlsruhe, Germany Репутация: нет Всего: 8 |
поясни мне, что мне мешает двигаться по диогонали ![]() ![]()
в таком случае, будут самые оптимальные варианты ![]() если на пути будет тупик, то ты с такой функцией застрелишься.. слишком много чего нужно будет учитывать ![]() |
||||
|
|||||
SLAER |
|
|||
Новичок Профиль Группа: Участник Сообщений: 39 Регистрация: 11.7.2008 Репутация: нет Всего: нет |
polosatij, мне не нужно выбирать оптимальные варианты, задача заключается в подсчете количества всех возможных вариантов, даже если это займет много времени.
Добавлено через 7 минут и 31 секунду переформулирую задачу, моожет быть тогда станет яснее и она будет иметь решение: требуется определить количество всевозможных вариантов перемещения фишки в правый нижний (противоположный) угол за 50 ходов по доске. Фишка может двигаться за 1 ход на 1 клетку в любом направлении (горизонтальном, вертикальном и диагональном). |
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |