Помогите с алгоритмом приведения пятнашек в исходное состояние (т.е. 1,2, .. 15)

Здравствуйте STANT, Вы писали:

STA>Помогите с алгоритмом приведения пятнашек в исходное состояние (т.е. 1,2, .. 15)
Да какой там алгоритм...
1, 2 на место
3 на место 4
4 на место 8
3, 4 на место
для 5, 6, 7, 8 аналогично
13 на место 9
9 на место 10
13, 9 на место
для 10, 14 аналогично
11, 12, 15 если еще не на месте то покрути немного.

ЗЫ че заочный тур олимпиады?

А как быть в таком случае:

1 2 3 4
5 6 7 8
9 10 15
13 11 14 12

10 поставили на место, а как теперь ставить 14, чтобы не сдвинуть 10 с места?
Программа как-то должна решать, каким образом ставить на место?

>>че заочный тур олимпиады?
нет, лабораторная работа.

Здравствуйте STANT, Вы писали:

[skipped]
Ты кстати в курсе, что не каждая комбинации собирается, например:

 01 02 03 04
 05 06 07 08
 09 10 11 12
 13 15 14

Эта "комбинация" не собирается.

Здравствуйте STANT, Вы писали:

STA>А как быть в таком случае:

А ГОЛОВОЙ ХОТЬ ЧУТЬ-ЧУТЬ ПОДУМАТЬ!?!? А КАК ТЫ ПОСТАВИЛ 9 И 13!?!?!?

Здравствуйте VVP, Вы писали:

VVP>Здравствуйте STANT, Вы писали:

VVP>[skipped]
VVP>Ты кстати в курсе, что не каждая комбинации собирается, например:
VVP>

VVP> 01 02 03 04
VVP> 05 06 07 08
VVP> 09 10 11 12
VVP> 13 15 14
VVP>

VVP>Эта "комбинация" не собирается.

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

WH>А ГОЛОВОЙ ХОТЬ ЧУТЬ-ЧУТЬ ПОДУМАТЬ!?!? А КАК ТЫ ПОСТАВИЛ 9 И 13!?!?!?
Да я пытаюсь..
9 и 13 можно было поставить, не сдвинув с места уже расставленные фишки, 10 тоже.
Но, как поставить 14, не сдвинув с места 10 или др. фишки, которые уже стоят на своих местах?
Ну, допустим, я-то еще могу поставить все на место, но программа?! Ей-то нужен четкий алгоритм!?
Или что-бы собрать Пятнашки нужен AI ?

Здравствуйте STANT, Вы писали:

STA>Или что-бы собрать Пятнашки нужен AI ?
Нет нужен IQ.
Плевать на 10 11 12 14 15 они не стоят на месте.
Убери 10 к чертям поставь туда 14 потом 10 на место 11 а дельше .... если IQ не в минусах сам разберешся.

ЗЫ извините за грубость.

Здравствуйте Nikto, Вы писали:

N>На сколько я понимаю классические пятнашки должны исходить не из случайной расстановки чисел, а из случайного перемщения чисел из начально собранных пятнашек. Поэтому такой ситуации быть не должно.

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

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

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 14 15

либо к

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 15 14

Здравствуйте WolfHound, Вы писали:

WH>ЗЫ извините за грубость.

Фи.

Здравствуйте WolfHound, Вы писали:

WH>Здравствуйте STANT, Вы писали:

STA>>Или что-бы собрать Пятнашки нужен AI ?
WH>Нет нужен IQ.
WH>Плевать на 10 11 12 14 15 они не стоят на месте.
WH>Убери 10 к чертям поставь туда 14 потом 10 на место 11 а дельше .... если IQ не в минусах сам разберешся.

WH>ЗЫ извините за грубость.

WH>

Я немного ошибся — хотел написать ответ, а написал новое сообщение — Re.
У меня некоторые проблемы с навигацией по этому сайту, наверное с непривычки.

Здравствуйте STANT, Вы писали:

STA>Помогите с алгоритмом приведения пятнашек в исходное состояние (т.е. 1,2, .. 15)

Это классическая задача искуственного интеллекта.

Медленный решатель должен поступать так:

1) оценочная функция — это сумма расстояний каждой фишки от своего "родного" места
(можно использовать как эвклидову метрику, т.е. sqrt(x^2+y^2), так и метрику первой степени, |x|+|y|).
2) каждый раз, когда имеются 2 или более вариантов хода, предпочитать такой, который улучшает ситуацию — то есть, определять, какая фишка сдвинется "более" в нужном направлении.
3) запоминать ситуации и ходы из них; не возвращаться к ним (кроме отката)
4) если решается задача "в реальных условиях", то выбирать лучший ход из текущей ситуации (предпочитая не ходить назад); если можно "моделировать", то выбирается лучший ход из всей истории ситуаций (моментальный откат).

Здравствуйте STANT, Вы писали:

STA>Я немного ошибся — хотел написать ответ, а написал новое сообщение — Re.
STA>У меня некоторые проблемы с навигацией по этому сайту, наверное с непривычки.

Позволю себе процитировать тебя. На будущее: если ошибся, то главное -- запости сообщение туда, куда надо. Лишнее я удалю. А сейчас твоё сообщение пишу в эту ветку. Вот оно:

>WolfHound
Не у всех IQ зашкаливает, но мне по крайней мере своего IQ пока хватало. Не нужно считать, что если человек тебя не понимает, то он тупой или не думает вообще. Может быть ты не правильно объясняешь свою мысль.

-----------------------------------------------------------------------------
Представим, что я программа, работающая по алгоритму:
1) 1, 2 на место
2) 3 на место 4
3) 4 на место 8
4) 3, 4 на место
5) для 5, 6, 7, 8 аналогично
6) 13 на место 9
7) 9 на место 10
8) 13, 9 на место
9) для 10, 14 аналогично
10) 11, 12, 15 если еще не на месте то покрути немного.

Ситуация такая:
1 2 3 4
5 6 7 8
13 14 12 10
9 11 15

Согласно алгоритму:
6)Поставил "13 на место 9";
7)Ставлю "9 на место 10", получаю:
....
....
14 9 12 10
13 11 15

8)Пытаюсь ставить "13, 9 на место", получаю, что порядок, созданный до этого начинает
нарушатся:
.... ....
.... 14 5 6 8
9 12 10 или 9 7 10
14 13 11 15 13 11 12 15

На шаге 10 зависаю...

---------------------------------------------------------------------------------------

Где ошибки в работе программы?

Здравствуйте, STANT, Вы писали:

STA>Помогите с алгоритмом приведения пятнашек в исходное состояние (т.е. 1,2, .. 15)

Прежде всего определим, заданное состояние решаемое или нет (т.е в конце 13,14,15 или 13,15,14).
Все зависит от числа перестановок двух соседних камней. Если число перестановок- четное число, перестановка сводится к первому варианту, иначе- ко второму.

Выставить 1 не проблема. 2 и 3 тоже. 4 устанавливает в состояние 8, 1 сдвигаем вниз, влево 2,3 и камень(х), что был в позиции 4. Четверку подымаем вверх. х опускаем вниз и 1,2,3 возвращаем на свои позиции.

Также поступаем с 5,6,7,8.

9 и 13 будем устанавливать вместе так, чтоб 13 находился слева от 9 в третьем ряду. Сдвигаем 13 и 9 влево до конца.13 опускаем вниз на свое место и устанавливаем 9. Также поступаем с 10 и 14. 11,12 и 15 устанавливаются элементарно.

Здравствуйте, Кодт, Вы писали:


К>Это классическая задача искуственного интеллекта.

К>Медленный решатель должен поступать так:

К>1) оценочная функция — это сумма расстояний каждой фишки от своего "родного" места
К>(можно использовать как эвклидову метрику, т.е. sqrt(x^2+y^2), так и метрику первой степени, |x|+|y|).
К>2) каждый раз, когда имеются 2 или более вариантов хода, предпочитать такой, который улучшает ситуацию — то есть, определять, какая фишка сдвинется "более" в нужном направлении.
К>3) запоминать ситуации и ходы из них; не возвращаться к ним (кроме отката)
К>4) если решается задача "в реальных условиях", то выбирать лучший ход из текущей ситуации (предпочитая не ходить назад); если можно "моделировать", то выбирается лучший ход из всей истории ситуаций (моментальный откат).

Здесь код моей программки для оптимального решения игры "Пятнашки". Я нахожу ее работу весьма быстрой. Базовое описание в статье Alexander Reinefeld: Complete Solution of the Eight-Puzzle and the Benefit of Node Ordering in IDA, хотя алгоритм подвергся заметным модификациям. Компилируется под VC 7.1 или 8 и GCC. Очень кстати для выполнения ряда проверок на этапе компиляции оказалось template metaprogramming. А вот запоминание ситуаций в данном случае оказалось напрасной тратой времени. Достаточно отсечения ходов, возвращающих к предыдущей ситуации, с чем тоже прекрасно справляются шаблоны.

Здравствуйте, STANT, Вы писали:

STA>Помогите с алгоритмом приведения пятнашек в исходное состояние (т.е. 1,2, .. 15)

Всевозможные состояния игры образуют неориентированный граф. Придумываем эвристическую функцию и запихиваем граф в алгоритм A*

Здравствуйте, konsoletyper, Вы писали:

K>Здравствуйте, STANT, Вы писали:

STA>>Помогите с алгоритмом приведения пятнашек в исходное состояние (т.е. 1,2, .. 15)

K>Всевозможные состояния игры образуют неориентированный граф. Придумываем эвристическую функцию и запихиваем граф в алгоритм A* :))) :))) :)))

Во-во. Удивительно что это сообщение написали так поздно. Причем если памяти не хватает, то A* легко модифицируется в упомянутый выше IDA или еще более продвинутый SMA. Эвристику тоже особо примумывать не надо — любая admissible функция (например Manhattan distance) подойдет.

Здравствуйте, konsoletyper, Вы писали:

>Всевозможные состояния игры образуют неориентированный граф. Придумываем эвристическую функцию и запихиваем граф в алгоритм A*

Максимальное число различных позиций менее 14*...*2*1. Значит для перебора пути от начальной позиции в конечную потребуется не более 21 Гб памяти.

Здравствуйте, <Аноним>, Вы писали:

>>Всевозможные состояния игры образуют неориентированный граф. Придумываем эвристическую функцию и запихиваем граф в алгоритм A*

А>Максимальное число различных позиций менее 14*...*2*1. Значит для перебора пути от начальной позиции в конечную потребуется не более 21 Гб памяти.

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

Здравствуйте, STANT, Вы писали:

STA>Помогите с алгоритмом приведения пятнашек в исходное состояние (т.е. 1,2, .. 15)

Вот здесь японец придумал хорошую эвристику.