Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 23.11.2009, 13:44
Новичок

Отправить личное сообщение для login Посмотреть профиль Найти все сообщения от login
 
Регистрация: 23.11.2009
Сообщений: 1

Поиск лучшего варианта игры в "кликоманию"
Прошу помощи:
Есть такая популярная игра - поле завалено шариками разного цвета (цветов 5) при лопании области шариков (шарики рядом стоящие одного цвета) - начисляются очки в арифметической прогрессии:
2 шарика - 10 очков
3 шарика - 30 очков
4 шарика - 60 очков
5 шариков - 100 очков и т.д.
после лопания шариков, оставшиеся вначале падают вниз, потом сдвигаются слева направо на освободившиеся места.
Цель игры - набрать большее кол-во очков

я много думал, реализовал классический рекурсивный поиск в глубину с полным перебором но это долго.... ОЧЕНЬ долго ))))
поэтому должен быть какой-то алгоритм, который сможет объективно оценить и как-то ускорить процесс.

Если есть какие-то идеи - подскажите. реализовать я могу и сам )))) но идей пока никаких.


для оптимизации рекурсии, смог придумать только:
1. Ограничить перебор одной и той же области (одну и туже область можно лопнуть исходя из разных шариков.)
2. если оставшиеся шарики не позволяют даже гипотетически (сумма шариков) набрать кол-во очков, большее чем уже найденный вариант, - программа их не считает.
Но все равно считает очень долго. )))
3. при прохождении кол-во шариков уменьшается (они скапливаются в правом нижнем углу) в связи с этим область поиска сужается по высоте и ширине.
  #2  
Старый 23.11.2009, 22:06
гость

 
Сообщений: n/a

По поводу игры знаю только что есть более простая вариация - где шарики на прямой располагаются - она динамой решается.
  #3  
Старый 23.11.2009, 22:10
гость

 
Сообщений: n/a

alpha-beta pruning.
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Построение пирамиды из "Х" и " " с помощью for. Alexander_ua Задачи 3 10.11.2009 13:35
[язык Си] Задача "Скрудж МакДак",поиск в глубину гость Задачи 0 18.03.2009 18:03
Поиск "элитного номера" valet Математические алгоритмы 10 18.03.2009 04:40
[язык Си] Задача "Скрудж МакДак",поиск в глубину гость Графы 0 18.03.2009 03:21
Проверка на существование/отсутствие предыдущего поколение в игре "Жизнь" гость Сортировка и поиск 0 02.12.2007 00:31