2 / 2 / 0
Регистрация: 06.08.2013
Сообщений: 50
|
|
1 | |
Алгоритм автоматического сбора "пятнашек"09.10.2015, 19:54. Показов 7344. Ответов 8
Метки нет (Все метки)
Программу, в ее стандартном виде(для пользователя) я написал. Теперь нужно прикрутить возможность автоматической сборки игры машиной. Хочу узнать, где можно найти информацию/алгоритмы, для реализации данной задачи?!
0
|
09.10.2015, 19:54 | |
Ответы с готовыми решениями:
8
Алгоритм пятнашек Написать программу, которая будет искать оптимальное решение для сбора пятнашек компонент проведения голосований и автоматического сбора статистики в рамках системы поддержки Алгоритм А* для решения нестандартных пятнашек Алгоритм поиска в ширину для пятнашек 3х3 |
2 / 2 / 2
Регистрация: 16.06.2014
Сообщений: 70
|
|
09.10.2015, 20:45 | 2 |
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 |
не цифр, а чисел. но суть не в этом.
ты сам себе противоречишь если это так, тогда скажи, для твоего примера: 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 |
прости, я тебя не понял.
можешь пояснить, что ты имел в виду?! Или хотя бы расшифруй "конечное положение для начальных позиций"?
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 | |
10.10.2015, 11:55 | |
Помогаю со студенческими работами здесь
9
Алгоритм и реализация автоматического учета расхода воды Алгоритм автоматического распределения текстур по карте для игры типа Героев 3 Написать алгоритм автоматического определения параметров радиосигналов с фазовой манипуляцией (ФМн) Задача на ДП "алгоритм сбора ранца" Необходимо придумать и имплементировать алгоритм для автоматического решения игры "заполнить квадратное поле фигурками" Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |