Алгоритм автоматического сбора "пятнашек"

@cruim · Регистрация: 06.08.2013

Программу, в ее стандартном виде(для пользователя) я написал. Теперь нужно прикрутить возможность автоматической сборки игры машиной. Хочу узнать, где можно найти информацию/алгоритмы, для реализации данной задачи?!

@Kherson_IT · 09.10.2015, 20:45

Вот интересный способ:

http://uggway.ru/?drv=view&art=90

Написано на паскале, но разобраться можно.

@dan24 · 10.10.2015, 07:59

Посмотрите как вообще решаются эти задачи. в книге перельман живая математика об этом написано. Там собственно все задачи 15ек сводятся к двум случаям: решаемому и принципиально не решаемому. Это зачисит но количества цифр находящихся не на своих местах. По моему если это кол-во чётно, то задача решаема, если нет- то не решаема. т.е. в конце вы получите 1 2 ... 12 13 15 14 и никак по другому. Обратите на это внимание.

@cruim · 10.10.2015, 09:20 **[ТС]**

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

@Sergio Leone · 10.10.2015, 10:36

Сообщение от dan24

Это зачисит но количества цифр находящихся не на своих местах. По моему если это кол-во чётно, то задача решаема,

не цифр, а чисел. но суть не в этом.
ты сам себе противоречишь

если это так, тогда скажи, для твоего примера:
1 2 3 4 5 6 7 8 9 10 11 12 13 15 14
сколько плашек стоит не на своём месте?
Это число чётно? Задача имеет решение?

только без обид! Платон мне друг, но истина дороже...

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

код на псевдо языке:

Код

inv = 0   ! inv - число инверсий
для i = 1 до 14
  для j = i+1 до 15
    если фишки[i] > фишка[j] то inc(inv)

если число инверсий чётное, то расстановка решаема,
если число инверсий нечётное, то решений нет.

@cruim · 10.10.2015, 10:50 **[ТС]**

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

@Sergio Leone · 10.10.2015, 10:57

Сообщение от cruim

В приведенном тобой примере показано конечное положение для начальных позиций, имеющих нечетное кол-во "беспорядков"/инверсий.

прости, я тебя не понял.

можешь пояснить, что ты имел в виду?! Или хотя бы расшифруй "конечное положение для начальных позиций"?

@cruim · 10.10.2015, 11:17 **[ТС]**

имеем рандомное расположение пятнашек, для одних позиций, конечным положением будет 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. конечное положение(в моем понимании), это при котором дальнейшее улучшение позиции не представляется возможным(не имеет смысла).

@Sergio Leone · 10.10.2015, 11:55

cruim, помни про бритву Оккама, не надо плодить сущности!
я же дал конкретный, простой, работающий алгоритм.
заносишь значения пятнашек в простой линейный массив, считаешь по предложенному алгоритму (фактически это простой готовый код) некое число.
если это число получилось чётное, решение есть, если нечётное - решения нет.
всё просто.

@cruim 2 / 2 / 0 Регистрация: 06.08.2013 Сообщений: 50
		1
	Алгоритм автоматического сбора "пятнашек" 09.10.2015, 19:54. Просмотров 4755. Ответов 8 Метки нет (Все метки) Программу, в ее стандартном виде(для пользователя) я написал. Теперь нужно прикрутить возможность автоматической сборки игры машиной. Хочу узнать, где можно найти информацию/алгоритмы, для реализации данной задачи?! 0

@Kherson_IT 1 / 1 / 2 Регистрация: 16.06.2014 Сообщений: 70
	09.10.2015, 20:45	2
	Вот интересный способ: http://uggway.ru/?drv=view&art=90 Написано на паскале, но разобраться можно. 0

@dan24 162 / 101 / 30 Регистрация: 19.01.2013 Сообщений: 821
	10.10.2015, 07:59	3
	Посмотрите как вообще решаются эти задачи. в книге перельман живая математика об этом написано. Там собственно все задачи 15ек сводятся к двум случаям: решаемому и принципиально не решаемому. Это зачисит но количества цифр находящихся не на своих местах. По моему если это кол-во чётно, то задача решаема, если нет- то не решаема. т.е. в конце вы получите 1 2 ... 12 13 15 14 и никак по другому. Обратите на это внимание. 0

@cruim 2 / 2 / 0 Регистрация: 06.08.2013 Сообщений: 50
	10.10.2015, 09:20 [ТС]	4
	Насколько я понял, там берется не кол-во цифр, находящихся не на своем месте, а расстояние каждой цифры от своего правильного места ("беспорядок"). И если сумма таких беспорядков четная, то задача решаема, если нечетная - нерешаемая. Т.е. вначале нужно еще организовать проверку на это условие. 0

@Sergio Leone 2508 / 1129 / 582 Регистрация: 07.06.2014 Сообщений: 3,281
	10.10.2015, 10:36	5
	Сообщение от dan24 Это зачисит но количества цифр находящихся не на своих местах. По моему если это кол-во чётно, то задача решаема, не цифр, а чисел. но суть не в этом. ты сам себе противоречишь если это так, тогда скажи, для твоего примера: 1 2 3 4 5 6 7 8 9 10 11 12 13 15 14 сколько плашек стоит не на своём месте? Это число чётно? Задача имеет решение? только без обид! Платон мне друг, но истина дороже... погуглил. пишут, что должно быть число инверсий чётное. число инверсий можно посчитать так: код на псевдо языке: Код inv = 0 ! inv - число инверсий для i = 1 до 14 для j = i+1 до 15 если фишки[i] > фишка[j] то inc(inv) если число инверсий чётное, то расстановка решаема, если число инверсий нечётное, то решений нет. 0

@cruim 2 / 2 / 0 Регистрация: 06.08.2013 Сообщений: 50
	10.10.2015, 10:50 [ТС]	6
	В приведенном тобой примере показано конечное положение для начальных позиций, имеющих нечетное кол-во "беспорядков"/инверсий. Как я понял, задачу надо решать с помощью эвристического поиска. 0

@Sergio Leone 2508 / 1129 / 582 Регистрация: 07.06.2014 Сообщений: 3,281
	10.10.2015, 10:57	7
	Сообщение от cruim В приведенном тобой примере показано конечное положение для начальных позиций, имеющих нечетное кол-во "беспорядков"/инверсий. прости, я тебя не понял. можешь пояснить, что ты имел в виду?! Или хотя бы расшифруй "конечное положение для начальных позиций"? 0

@cruim 2 / 2 / 0 Регистрация: 06.08.2013 Сообщений: 50
	10.10.2015, 11:17 [ТС]	8
	имеем рандомное расположение пятнашек, для одних позиций, конечным положением будет 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. конечное положение(в моем понимании), это при котором дальнейшее улучшение позиции не представляется возможным(не имеет смысла). 0

@Sergio Leone 2508 / 1129 / 582 Регистрация: 07.06.2014 Сообщений: 3,281
	10.10.2015, 11:55	9
	cruim, помни про бритву Оккама, не надо плодить сущности! я же дал конкретный, простой, работающий алгоритм. заносишь значения пятнашек в простой линейный массив, считаешь по предложенному алгоритму (фактически это простой готовый код) некое число. если это число получилось чётное, решение есть, если нечётное - решения нет. всё просто. 0

Опции темы