Компьютерный форум
Правила
Вернуться   Компьютерный форум > Форум программистов > Теория программирования > Игры разума
Перезагрузить страницу Пятнашки как найти алгоритм создания игры
Ответ
 
Опции темы Опции просмотра
  (#1 (permalink)) Старый
wwwslavan wwwslavan вне форума
Новичок
 
Сообщений: 3
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.03.2006
По умолчанию Пятнашки как найти алгоритм создания игры - 31.03.2006, 00:40

Старая и всем известная забава - пятнашки. Существует тривиальный способ сборки. Но самое интересное - существует ли алгоритм нахождения именно оптимальной сборки за адекватное время? Естественно полный перебор нам даст оптимальное решение, но вот затраты времени будут малость не адекватные. Но это еще не так интересно. Может ли кто предложить алгоритм для более общего случая n*n?
Ответить с цитированием
  (#2 (permalink)) Старый
pEtr0 pEtr0 вне форума
Member
 
Сообщений: 70
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 23.02.2006
По умолчанию 31.03.2006, 12:02

Если я не ошибаюсь пятнашки решаются эвристическим поиском, тока вот я не уверен что он находит оптимальное решение, хотя при соответсвующей эвристике наверное да...
Посмотри эту тему http://www.hardforum.ru/t64241
Ответить с цитированием
  (#3 (permalink)) Старый
Fuud Fuud вне форума
Member
 
Сообщений: 4,076
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.09.2004
По умолчанию 31.03.2006, 20:30

Нет. Есть два варианта - полный перебор (точно оптимальное решение). Эвристика - хорошое (не обязательно оптимальное) решение за меньшее время.
Ответить с цитированием
  (#4 (permalink)) Старый
wwwslavan wwwslavan вне форума
Новичок
 
Сообщений: 3
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.03.2006
По умолчанию 01.04.2006, 11:59

Тоесть на даный момент ничего лучшего чем эвристический способ не придумано? А доказано ли что нет оптимального решения и не может быть?
Ответить с цитированием
  (#5 (permalink)) Старый
Fuud Fuud вне форума
Member
 
Сообщений: 4,076
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.09.2004
По умолчанию 01.04.2006, 18:37

Нет, конечно не доказано. Если под оптимальным решением подразумевается алгоритм, однозначно определяющий ход, то думаю что такого нет (я такого не видел).
Ответить с цитированием
Ads.
  (#6 (permalink)) Старый
StarLey StarLey вне форума
Новичок
 
Сообщений: 11
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 28.03.2006
По умолчанию 06.04.2006, 19:29

Я думаю, что для решения такой задачи потребуеться большой ресурс вычислительный...
Ответить с цитированием
  (#7 (permalink)) Старый
Serega_Mexanik Serega_Mexanik вне форума
Member
 
Сообщений: 215
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 12.12.2005
По умолчанию 07.04.2006, 13:17

однокурсник мой писал курсрвую...
могу скинуть...

ЗЫ:а вы знаете что половина из разкиданных пятнашек - обратно не собираються...
есть какой-то критерий...
Ответить с цитированием
  (#8 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 07.04.2006, 18:49

Цитата:
Originally posted by Serega_Mexanik
[b]однокурсник мой писал курсрвую...
могу скинуть...

ЗЫ:а вы знаете что половина из разкиданных пятнашек - обратно не собираються...
есть какой-то критерий...
Вроде как критерий такой:
Возможно собрать только те комбинации, которые получаются чётным кол-вом перестановок соседних элементов.
- Где-то слышал, за верность не ручаюсь....


импортирован с progz.ru
Ответить с цитированием
  (#9 (permalink)) Старый
wwwslavan wwwslavan вне форума
Новичок
 
Сообщений: 3
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 27.03.2006
По умолчанию 08.04.2006, 19:10

Собираются пятнашки или нет зависит от четности инверсий расположения пятнашек.
Ответить с цитированием
  (#10 (permalink)) Старый
Fuud Fuud вне форума
Member
 
Сообщений: 4,076
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.09.2004
По умолчанию 08.04.2006, 22:27

Абсолютно верно. Раз уж тема расположена в ИграхРазума предлагаю доказать (это просто)!
Ответить с цитированием
  (#11 (permalink)) Старый
Shunix Shunix вне форума
Member
 
Сообщений: 1,355
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 07.06.2002
По умолчанию 22.04.2006, 16:37

Давно чесались руки выложить статью с сайта журнала "Программист", посвященную алгоритмам AI-поиска применительно к поиску решений для игры "Пятнашки" (ныне, к сожалению, почившего в бездну :-( ).
Итак, для тех, кому интересно:
Название статьи: "Алгоритмы AI-поиска"
Автор: Игорь Бобак
URL: Алгоритмы AI-поиска (125 kB)
Ответить с цитированием
  (#12 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 22.04.2006, 22:24

Цитата:
Originally posted by Fuud
[b]Абсолютно верно. Раз уж тема расположена в ИграхРазума предлагаю доказать (это просто)!
Ну-ка покажи клас!


импортирован с progz.ru
Ответить с цитированием
Ads
  (#13 (permalink)) Старый
Fuud Fuud вне форума
Member
 
Сообщений: 4,076
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.09.2004
По умолчанию 22.04.2006, 23:24

При каждом ходе четность перестановки не меняется=>из нечетной перестановки нельзя получить четную.
Ответить с цитированием
  (#14 (permalink)) Старый
Кошмар Кошмар вне форума
Member
 
Сообщений: 2,694
Сказал(а) спасибо: 0
Поблагодарили 1 раз в 1 сообщении
Регистрация: 23.04.2005
По умолчанию 23.04.2006, 12:43

Цитата:
Originally posted by Fuud
[b]При каждом ходе четность перестановки не меняется=>из нечетной перестановки нельзя получить четную.
Это-то понятно... Только не понятно утверждение, что чётность перестановки не меняется..
было расположение
1 2 3
4 5 6
7 8 0
где 0 дырка
стало
1 2 3
4 5 6
7 0 8
помоему очень даже поменялась - произошла одна перестановка (1- нечётное число)

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


Можешь поподробнее объяснить?


импортирован с progz.ru
Ответить с цитированием
  (#15 (permalink)) Старый
Fuud Fuud вне форума
Member
 
Сообщений: 4,076
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Регистрация: 03.09.2004
По умолчанию 23.04.2006, 13:30

Четность перестановки для пятнашек (4на4) определяется не так:
1)пустое место не учитывается
2)к четности перестановки прибавляется четность номера ряда (или сам номер ряда), содержащего пустое поле(*)

Тогда этот инвариант не меняется в процессе игры.


(*)для досок с нечетным количеством клеток на стороне прибавлять не надо.


ps я пропустил недочет в посте wwwslavan и, очевидно, не так поняли...
Ответить с цитированием
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Игра Пятнашки для одновременной игры нескольких игроков Light_Angel Вопросы начинающих программистов 8 13.03.2010 18:48
Что нужно для создания игры на С++ assars Вопросы начинающих программистов 5 04.03.2010 09:46
Какие компоненты и какой исходный код нужно использовать для создания игры Сапёр Byvaliy C++ Builder 7 03.12.2008 12:27
Алгоритм получения целевой расстановки для игры 15 Anonymous Алгоритмы 20 18.08.2006 12:22
Алгоритм для создания сайтов Worm Вопросы начинающих программистов 2 10.06.2006 03:11
Ищу партнёра для создания игры по сети JackTheHack Delphi 1 05.03.2006 15:37
Создание игры пятнашки pikass .NET 1 17.02.2006 09:39
Алгоритм создания меню Newey Алгоритмы 6 09.01.2006 21:51
CLIPS как посмотреть алгоритм написания игры пятнашки Marisha_M Lisp 1 16.06.2005 10:11
Где найти алгоритм хода компьютера игры "Балда" N0RtAn Вопросы начинающих программистов 15 11.05.2005 13:05
Команда разработчиков для создания игры ARKANTOS Некоммерческие проекты 0 22.09.2004 10:22
Как написать алгоритм игры Anonymous Алгоритмы 0 10.06.2003 21:36



Powered by vBulletin® Version 3.8.7
Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
Нardforum.ru - компьютерный форум и программирование, форум программистов