Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
KettyP
1 / 1 / 1
Регистрация: 20.03.2014
Сообщений: 22
1

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

03.04.2014, 15:23. Просмотров 764. Ответов 4
Метки нет (Все метки)

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

Подскажите идею, как это реализовать?
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.04.2014, 15:23
Ответы с готовыми решениями:

Алгоритм А* для игры "Пятнашки"
Привет всем, помогите пожалуйста разобраться в одной статье, в которой говорится об использовании...

Игра "пятнашки" - адаптировать готовый код к новому проекту
Помогите или объясните как создать в форме эту игру по этому коду: Fifteen.cpp...

Как создать такое же окно с фишками? Игра "Пятнашки"
#include <stdio.h> #include <stdlib.h> #include <time.h> #include <windows.h> #define SIZE ...

Игра пятнашки, или Как создать структуру хранения "Дерево"?
Для реализации алгоритма игры пятнашки необходима структура Дерево, которая бы хранила матрицы...

Игра "пятнашки": событие, что-бы кнопки передвигались на пустое место
Добрый день всем. Подскажите пожалуста как написать событие Clik так что-бы кнопкт передвигались...

4
Cтанислав
30 / 30 / 8
Регистрация: 15.04.2013
Сообщений: 244
03.04.2014, 15:38 2
Как вариант можно попробовать метод обратных подстановок. Оптимальность решения не гарантирую.
0
wingblack
281 / 255 / 45
Регистрация: 09.04.2013
Сообщений: 953
04.04.2014, 09:19 3
Через поиск находятся, в основном, упоминания о алгоритме A* на пространстве состояний с функцией расстояния как количество элементов не на своих местах + количество пройденных шагов. Впрочем, в одном из комментариев было предположено использовать расстояние между текущим положением элемента, и его требуемым положением.
Как один из примеров http://www.pvsm.ru/java/16174

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

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

Цитата Сообщение от KettyP Посмотреть сообщение
Пишет не хватает памяти
Минимизировать размеры хранимых данных(зачем int для элеметов массива для хранения состояния доски, который (int), наверное, равен или больше 4 байт, если для обозначения пятнашки 1 байта больше чем нужно), и не надеяться на сборщик мусора, а прибирать самому.
Кстати, для хранения состояния доски достаточно 32 байта (16*16/8).
1
05.04.2014, 20:35
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.04.2014, 20:35

Игра "Пятнашки", не получается перемешать фишки
Помогите немного, не получается, перемешать фишки, как это можно реализовать, и что то с проверкой...

Игра "Пятнашки" в режиме игрок-компьютер
Итак,проблема такова: при игре в режиме игрок-компьютер,компьютер делает максимум 3 хода,либо...

Игра "Пятнашки": реализовать подсчет очков
Я ещё новичок. Вообщем, у меня пятнашки. Они состоят из двух форм: сама игра и настройки. В...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru