Какой придумать алгоритм для расстановки фигур в определённом порядке. По-сути это игра "пятнашки"

@KettyP · Регистрация: 20.03.2014

Студворк — интернет-сервис помощи студентам

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

Какой придумать алгоритм для расстановки фигур в определённом порядке. По-сути это игра "пятнашки"

Подскажите идею, как это реализовать?

@Cтанислав · 03.04.2014, 15:38

Как вариант можно попробовать метод обратных подстановок. Оптимальность решения не гарантирую.

@wingblack · 04.04.2014, 09:19

Через поиск находятся, в основном, упоминания о алгоритме A* на пространстве состояний с функцией расстояния как количество элементов не на своих местах + количество пройденных шагов. Впрочем, в одном из комментариев было предположено использовать расстояние между текущим положением элемента, и его требуемым положением.
Как один из примеров http://www.pvsm.ru/java/16174

Добавлено через 5 минут
но поскольку в нем предполагается хранить путь, то предположу что более правильно было бы вместо списка использовать дерево и прыгать по листьям с минимальным весом (например добавить список с ссылками на листья для ускорения поиска)

@KettyP · 04.04.2014, 23:06 **[ТС]**

Спасибо за ответы! Попробовала так вот реализовать, как в примере по ссылке. Для простых задач находит решение... где-то шагов 30 ещё может осилить, а вот в моём примере видимо больше шагов ((
Пишет не хватает памяти в куче. В файлике .ini изменила -Xms2048m -Xmx2048m. Но всё равно что-то не хочет работать. Видимо где-то утечка памяти... А вот ваша идея с деревом мне понравилась, только не знаю как реализовать( java учила очень давно...

@wingblack · 05.04.2014, 20:35

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

А вот ваша идея с деревом мне понравилась, только не знаю как реализовать( java учила очень давно...

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

Не обязательно прям на яве делать, делайте на том где удобнее, просто тут прямо пример реализации дается.

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

Пишет не хватает памяти

Минимизировать размеры хранимых данных(зачем int для элеметов массива для хранения состояния доски, который (int), наверное, равен или больше 4 байт, если для обозначения пятнашки 1 байта больше чем нужно), и не надеяться на сборщик мусора, а прибирать самому.
Кстати, для хранения состояния доски достаточно 32 байта (16*16/8).

Новые блоги и статьи Все статьи Все блоги /
Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .
Запрет удаления строк ТЧ документа при определённом условии Maks 19.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "Аккумуляторы", разработанного в конфигурации КА2. У данного документа есть ТЧ, в которой в зависимости от прав доступа. . .	Модель заражения группы наркоманов alhaos 17.04.2026 Условия задачи сформулированы тут Суть: - Группа наркоманов из 10 человек. - Только один инфицирован ВИЧ. - Колются одной иглой. - Колются раз в день. - Колются последовательно через. . .	Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .

@KettyP 1 / 1 / 1 Регистрация: 20.03.2014 Сообщений: 22

	Какой придумать алгоритм для расстановки фигур в определённом порядке. По-сути это игра "пятнашки" 03.04.2014, 15:23. Показов 1883. Ответов 4 Метки нет (Все метки) Нужно придумать алгоритм нахождения оптимального решения, то есть наименьшее количество перестановок. Подскажите идею, как это реализовать? 0

@Cтанислав 30 / 30 / 8 Регистрация: 15.04.2013 Сообщений: 244
	03.04.2014, 15:38
	Как вариант можно попробовать метод обратных подстановок. Оптимальность решения не гарантирую. 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	04.04.2014, 09:19
	Через поиск находятся, в основном, упоминания о алгоритме A* на пространстве состояний с функцией расстояния как количество элементов не на своих местах + количество пройденных шагов. Впрочем, в одном из комментариев было предположено использовать расстояние между текущим положением элемента, и его требуемым положением. Как один из примеров http://www.pvsm.ru/java/16174 Добавлено через 5 минут но поскольку в нем предполагается хранить путь, то предположу что более правильно было бы вместо списка использовать дерево и прыгать по листьям с минимальным весом (например добавить список с ссылками на листья для ускорения поиска) 1

@KettyP 1 / 1 / 1 Регистрация: 20.03.2014 Сообщений: 22
	04.04.2014, 23:06 [ТС]
	Спасибо за ответы! Попробовала так вот реализовать, как в примере по ссылке. Для простых задач находит решение... где-то шагов 30 ещё может осилить, а вот в моём примере видимо больше шагов (( Пишет не хватает памяти в куче. В файлике .ini изменила -Xms2048m -Xmx2048m. Но всё равно что-то не хочет работать. Видимо где-то утечка памяти... А вот ваша идея с деревом мне понравилась, только не знаю как реализовать( java учила очень давно... 0

Опции темы