2 / 2 / 0
Регистрация: 06.08.2013
Сообщений: 50
1

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

09.10.2015, 19:54. Показов 7344. Ответов 8
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Программу, в ее стандартном виде(для пользователя) я написал. Теперь нужно прикрутить возможность автоматической сборки игры машиной. Хочу узнать, где можно найти информацию/алгоритмы, для реализации данной задачи?!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.10.2015, 19:54
Ответы с готовыми решениями:

Алгоритм пятнашек
Я хочу сам написать игру пятнашки, пожалуйста не кидайте готовые программы, Хочу сам по...

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

компонент проведения голосований и автоматического сбора статистики в рамках системы поддержки
В общем попала в институте: надо написать УИР на тему Проектирование и разработка реиспользуемых...

Алгоритм А* для решения нестандартных пятнашек
Добрый день! Если есть кто-то, кто может решить эту задачу, прошу откликнитесь. Обсудим все в...

Алгоритм поиска в ширину для пятнашек 3х3
Здравствуйте, хочу разобраться с поиском в ширину на примере сборки пятнашек 3х3. Вроде бы понимаю...

8
2 / 2 / 2
Регистрация: 16.06.2014
Сообщений: 70
09.10.2015, 20:45 2
Вот интересный способ:

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

Написано на паскале, но разобраться можно.
0
167 / 106 / 30
Регистрация: 19.01.2013
Сообщений: 842
10.10.2015, 07:59 3
Посмотрите как вообще решаются эти задачи. в книге перельман живая математика об этом написано. Там собственно все задачи 15ек сводятся к двум случаям: решаемому и принципиально не решаемому. Это зачисит но количества цифр находящихся не на своих местах. По моему если это кол-во чётно, то задача решаема, если нет- то не решаема. т.е. в конце вы получите 1 2 ... 12 13 15 14 и никак по другому. Обратите на это внимание.
0
2 / 2 / 0
Регистрация: 06.08.2013
Сообщений: 50
10.10.2015, 09:20  [ТС] 4
Насколько я понял, там берется не кол-во цифр, находящихся не на своем месте, а расстояние каждой цифры от своего правильного места ("беспорядок"). И если сумма таких беспорядков четная, то задача решаема, если нечетная - нерешаемая. Т.е. вначале нужно еще организовать проверку на это условие.
0
2509 / 1130 / 582
Регистрация: 07.06.2014
Сообщений: 3,286
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
2 / 2 / 0
Регистрация: 06.08.2013
Сообщений: 50
10.10.2015, 10:50  [ТС] 6
В приведенном тобой примере показано конечное положение для начальных позиций, имеющих нечетное кол-во "беспорядков"/инверсий. Как я понял, задачу надо решать с помощью эвристического поиска.
0
2509 / 1130 / 582
Регистрация: 07.06.2014
Сообщений: 3,286
10.10.2015, 10:57 7
Цитата Сообщение от cruim Посмотреть сообщение
В приведенном тобой примере показано конечное положение для начальных позиций, имеющих нечетное кол-во "беспорядков"/инверсий.
прости, я тебя не понял.
можешь пояснить, что ты имел в виду?! Или хотя бы расшифруй "конечное положение для начальных позиций"?
0
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
2509 / 1130 / 582
Регистрация: 07.06.2014
Сообщений: 3,286
10.10.2015, 11:55 9
cruim, помни про бритву Оккама, не надо плодить сущности!
я же дал конкретный, простой, работающий алгоритм.
заносишь значения пятнашек в простой линейный массив, считаешь по предложенному алгоритму (фактически это простой готовый код) некое число.
если это число получилось чётное, решение есть, если нечётное - решения нет.
всё просто.
0
10.10.2015, 11:55
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
10.10.2015, 11:55
Помогаю со студенческими работами здесь

Алгоритм и реализация автоматического учета расхода воды
доброго времени суток. Хотел бы посоветоваться и принять помощь в решении задачи. (я дилетант и...

Алгоритм автоматического распределения текстур по карте для игры типа Героев 3
Здравствуйте! Недавно захотелось написать игру похожую на герои 3, начал с редактора карт. Все шло...

Написать алгоритм автоматического определения параметров радиосигналов с фазовой манипуляцией (ФМн)
Гайс очень нужна помощь может у когото есть заготовки или сам код Нужно написать алгоритм...

Задача на ДП "алгоритм сбора ранца"
Помогите с решением задачи : Надо собрать ранец чтоб ценность вещей была максимально возможной ,...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru