Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Алгоритм обхода шахмотной доски, Перебор вариантов перемещения фишек 
:(
    Опции темы
SLAER
Дата 11.7.2008, 21:21 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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



Здравствуйте. Может быть кто-нибудь поможет в решении следующей задачи:

Имеется шахматная доска размером 5x5 и одна фишка в левом верхнем углу. Требуется определить количество всевозможных вариантов ее перемещения в правый нижний (противоположный) угол. 

Как я понимаю, решение сводится к составлению и обходу дерева вариантов, но я пока не представляю, как его составить. Если сможете, подскажите пожалуйста алгоритм.
PM MAIL   Вверх
Akina
Дата 11.7.2008, 21:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

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



Два раза в одну клетку не попадать?


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
SLAER
Дата 11.7.2008, 21:43 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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



Попадать можно, но только избегать зацикливания
PM MAIL   Вверх
maxim1000
Дата 11.7.2008, 21:55 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
****


Профиль
Группа: Участник
Сообщений: 3334
Регистрация: 11.1.2003
Где: Киев

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



что подразумевается под "зацикливанием"


--------------------
qqq
PM WWW   Вверх
SLAER
Дата 11.7.2008, 22:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 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]

и т.д.

т.е. вцелом пути не повторяются, но позиции могут повторяться.
PM MAIL   Вверх
dereyly
Дата 11.7.2008, 23:51 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Бывалый
*


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

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



Полагаю что на одну и ту же позицию нельзя вставить 2ды... иначе задача не имела бы точного решения... 
А в такой постановке мне пока ничего путного не приходит в голову кроме подсчета количества решений поиска в ширину.
PM MAIL   Вверх
polosatij
  Дата 12.7.2008, 02:08 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1143
Регистрация: 22.2.2004
Где: Stuttgart<-> ;Karlsruhe, Germany

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





не надо ничего считать.. задача очень простая.. и дерево тоже не надо рисовать..
смотри.. тебе надо всего лишь нарисовать "волны на доске" и перемещаться из меньшего в большее.. смотри на рисунке:

01234
12345
23456
34567
45678

 smile +1   smile 


--------------------
PM   Вверх
SLAER
Дата 12.7.2008, 07:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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



Но в таком случае перебраны будут не все возможные варианты, я так полагаю?

Добавлено через 1 минуту и 15 секунд
И подскажите пожалуйста алгоритм поиска в ширину в таком случае, а то везде пишут по разному

Добавлено через 5 минут и 34 секунды
Фишка может перемещаться на 1 клетку в любом направлении (по вертикали, по горизонтали и по диагонали)
PM MAIL   Вверх
Akina
Дата 12.7.2008, 08:12 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

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



polosatij, ты неправ. Нет ограничения на направление движения - а твой вариант допускает только движение вправо или вниз.

SLAER, дерево тут тебе не поможет - хотя бы потому, что связи узлов меняются в зависимости от пройденной части пути. Боюсь, что это таки переборная задача. Рекурсивный алгоритм перебора даст решение, пусть и неоптимальное.


--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
SLAER
Дата 12.7.2008, 08:52 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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



да мне и не важно, оптимальное оно или нет. Подскажите плз, как вообще этот рекурсивный алгоритм перебора реализовать? сложность и заключается в том, как перебрать все варианты. 
PM MAIL   Вверх
Akina
Дата 12.7.2008, 09:07 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Советчик
****


Профиль
Группа: Модератор
Сообщений: 20581
Регистрация: 8.4.2004
Где: Зеленоград

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



Цитата(SLAER @  12.7.2008,  09:52 Найти цитируемый пост)
как вообще этот рекурсивный алгоритм перебора реализовать? 

Пишется рекурсивная процедура.
В качестве параметров в нее передается текущее состояние доски - т.е. какие клетки в каком порядке посещены, соответственно вычисляется, какие не посещены и какая является текущей. 
Если текущая = концу маршрута - выводится текущий вариант обхода (или плюсуется единичка к количеству вариантов).
Если текущая <> концу маршрута - процедура в цикле делает каждый из возможных ходов, и вызывает себя же, передавая себе то состояние доски, которое получается в результате сделанного следующего хода.

Максимальное количество возможных ходов на каждом шаге рекурсии - 8, минимальное - 0 (загнали себя в тупик). Максимальная глубина вложенности для доски 5*5 - 24 хода, так что и стека, и памяти должно хватать.
Для снижения накладнЫх расходов я бы передавал адрес текущей клетки в дополнителдьной переменной.



--------------------
 О(б)суждение моих действий - в соответствующей теме, пожалуйста. Или в РМ. И высшая инстанция - Администрация форума.

PM MAIL WWW ICQ Jabber   Вверх
SLAER
Дата 12.7.2008, 10:05 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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



Очень признателен, попробую реализовать. Большое спасибо

Добавлено через 6 минут и 40 секунд
Только возникает вопрос, как определить текущее состояние доски, и как его передать в процедуру, как массив ячеек или как то по другому? и еще, какой вложенности делать рекурсию?

Добавлено через 6 минут и 57 секунд
Поясните поподробнее, если не сложно
PM MAIL   Вверх
polosatij
  Дата 12.7.2008, 13:30 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Эксперт
***


Профиль
Группа: Завсегдатай
Сообщений: 1143
Регистрация: 22.2.2004
Где: Stuttgart<-> ;Karlsruhe, Germany

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



Цитата(Akina @  12.7.2008,  08:12 Найти цитируемый пост)
Нет ограничения на направление движения - а твой вариант допускает только движение вправо или вниз.


поясни мне, что мне мешает двигаться по диогонали  smile  я написал, от меньшего к большему, два разве не больше, чем один?  smile 

Цитата(SLAER @  12.7.2008,  07:06 Найти цитируемый пост)
Но в таком случае перебраны будут не все возможные варианты, я так полагаю?


в таком случае, будут самые оптимальные варианты  smile 

Цитата(Akina @  12.7.2008,  09:07 Найти цитируемый пост)
В качестве параметров в нее передается текущее состояние доски - т.е. какие клетки в каком порядке посещены, соответственно вычисляется, какие не посещены и какая является текущей. 


если на пути будет тупик, то ты с такой функцией застрелишься.. слишком много чего нужно будет учитывать  smile 



--------------------
PM   Вверх
SLAER
Дата 12.7.2008, 14:06 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



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

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



polosatij, мне не нужно выбирать оптимальные варианты, задача заключается в подсчете количества всех возможных вариантов, даже если это займет много времени.

Добавлено через 7 минут и 31 секунду
переформулирую задачу, моожет быть тогда станет яснее и она будет иметь решение: 

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


PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


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

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


 




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


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

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