Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Алгорифм стремительного поиска слов в игре балда

Anna | 24.06.2014 | нет комментариев

Как-то в одной общественной сети наткнулся на игру балда с нестандартными правилами (крупные поля и узелки). Программы-подбиралки в основном работают по типичным правилам и на полях 5х5. Следственно у меня возник спортивный интерес написать свою подбиралку всецело адаптированную под нетрадиционные правила. Причем не легко написать подбиралку, а реализовать максимально стремительный алгорифм поиска слов.


Из нестандартных правил выдается достаточно увлекательный режим «узелки», в котором составлять слово дозволено, применяя одну букву до 2-х раз (скажем, на скриншоте сверху дозволено составить слово ШАЛАШ, буквы Ш и А использованы 2 раза). Как потом выяснилось, в одной и той же позиции алгорифм ищет все слова в режиме узелки примерно ровно в 1.5 раз дольше, чем в классическом режиме без узелков (это и не чудесно, т.к. вариантов составления слов огромнее и обнаруженные слова длиннее). В конце статьи описанный алгорифм будет протестирован в тестовой позиции в режиме узелки.

Словарь

Для того Дабы ещё огромнее затруднить жизнь алгорифму будет применяться один из самых крупных словарей в сходственных программах. Он насчитывает приблизительно 110000 слов.
Значимую роль в алгорифме играет метод хранения словаря в памяти программы. При загрузке всякое слово записывается в конструкцию в виде дерева. Всякий узел этого дерева обозначает определенную букву слова и ссылается на не больше чем 32 поддерева (по числу букв в алфавите). Узел дерева в программе выглядит так:

typedef TREE *NEXT;     //указатель на следующую букву 
struct TREE 
{ 
    NEXT *next;         //массив указателей на все допустимые следующие буквы 
    char *str;          //строка со всеми допустимыми следующими буквами 
    char *wrd;          //если не NULL, то это слово из словаря 
}; 

В поле str содержится строка со всеми буквами, которые выходят из данного узла, размер массива next[]равен длине этой строки.
Поле str применяется для нахождения определенного узла среди массива узлов next[] для данной буквы. Для этого введена функция ind(), основанная на strchr():

int k=ind('и',str);         //возвращает индекс (позицию) буквы ‘и’ в строке str 

Если k<0, то данной буквы нет в str, напротив next[k] указывает на узел, соответствующий этой букве. Скажем, если str содержит строку "аоикт", то из этого узла идут ровно 5 поддеревьев, причем next[2]ссылается на букву 'и', т.к. str[2]== 'и', то же самое и с другими буквами.
Для иллюстрации каждого вышеописанного приведу пример дерева на намеренно подготовленном словаре, состоящем из слов:

балда, банка, бар, манка, барсук

Если поле str==NULL, то данный узел является листом и в нём содержится словарное слово wrd. Узел, соответствующий букве 'р', содержит слово "бар", и при этом он не является листом, потому что в данном словаре есть ещё одно слово, начинающееся на бар-. Поле wrd содержит строку, которая получается, если идти от корня к соответствующему узлу, но если эта строка не является словарным словом, то wrd содержитNULL.
Назовём это дерево словарным, в нём содержатся все слова из словаря. Помимо словарного дерева нужно подготовить ещё одно, в котором содержатся все допустимые инвертированные префиксы слов для всякого слова (назовём это дерево инвертированным). К примеру, для слова "балда" в инвертированное дерево попадут следующие строки: "адлаб", "длаб", "лаб", "аб", "б". Даже для тестового словаря с пятью словами такое дерево будет массивным, следственно приведу упрощенный вариант:

Слова Префиксы словарных слов в этом дереве расположены задом-наперед. Узел в красном кружочке соответствует последней букве инвертированного префикса словарного слова, т.е. соответствует первой букве этого слова. Дабы прочитать предисловие словарного слова необходимо двигаться от красного узла к корню. Исключительное различие инвертированного дерева от словарного – это то, что wrd исполняет роль флага (NULL/не NULL). Т.е. в нем хранится не строка с инвертированным префиксом слова, а:

  • 1) Адрес всеобщей строки (содержимое строки не имеет значения), если данный узел соответствует первой букве словарного слова
  • 2) NULL, для всех остальных узлов.

Это сделано для экономии места. Для всех красных узлов wrd!=NULL, для остальных wrd==NULL. К примеру:

root_inv->str == ”адлбкнрусм”; 
root_inv->next[0]->str == ”бдкм”; 
root_inv->next[5]->next[0]->wrd == NULL; //АН не является префиксом словарного слова 
root_inv->next[5]->next[0]->next[1]->wrd != NULL; //МАН является префиксом словарного слова

Оба дерева занимают в памяти 33М, и непринужденно из словаря они строятся приблизительно за 5 секунд на i5, следственно было принято решение сберечь образ деревьев в файл и в последующем грузить именно его. Так скорость загрузки составила каждого 300 миллисекунд.

Алгорифм поиска

По правилам балды для хода необходимо предпочесть пустую клетку, и поставить туда всякую букву.

Спрятанный текст

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

После этого необходимо составить слово, применяя поставленную букву. Данная буква может быть как первой буквой в слове, так и не первой буквой (хоть и капитанство, но это значимо). Если бы в правилах было сказано, что поставленная буква должна быть верно первой, то легко используем словарное дерево, двигаясь по полю от поставленной буквы единовременно спускаясь вниз по дереву. Но т.к. поставленная буква может и не быть первой, словарное дерево применять невозможно, потому что не вестимо с какого именно узла начинать поиск. Но у нас ещё есть инвертированное дерево.
Идея такая: из клетки с поставленной буквой движемся по полю, спускаясь по инвертированному дереву. Если находим узел, у которого wrd!=NULL (алый узел), значит это валидный инвертированный префикс слова. Имея префикс слова, дозволено в словарном дереве обнаружить узел, соответствующий поставленной букве, и дальше легко «донайти» оставшийся кусок слова теснее в словарном дереве, начиная с этого узла.
Для того Дабы алгорифм не заходил в клетки, которые ранее для данного слова теснее прошёл, в всякой клетке имеется счетчик применения count. Перед началом поиска данный счетчик инициализируется числом 2 (для режима узелки) либо 1 (для классического режима) – это исключительное различие режимов с точки зрения алгорифма.
Больше подробнейший алгорифм:

  • 1) Перебираем все пустые смежные клетки
  • 2) Для всякой клетки перебираем все буквы алфавита (32 буквы)
  • 3) Заносим в нынешнюю клетку (пускай её координаты будут [x, y]) нынешнюю букву s. Так получаем 32*n различных позиций, где n – число смежных клеток в начальной позиции
  • 4) Внесенную букву считаем первой буквой для инвертированных префиксов.
    Следственно среди root_inv->next[] находим узел t_inv, соответствующий нынешний букве, т.е. t_inv– поддерево, начинающееся с нынешней буквы:

    int k = ind(s, root_inv->str);	//s – нынешняя буква
    if(k<0) continue;		//вдруг инвертированный префикс не может начинаться с этой буквы
    TREE * t_inv = root_inv->next[k];
    
  • 5) Сокращаем count[x, y] и вызываем функцию поиска в поддереве find (о которой ниже) для t_inv и клетки [x, y]
  • 6) Конец цикла по буквам
  • 7) Конец цикла по смежным клеткам

Безусловно позже цикла по буквам очищаем нынешнюю смежную клетку.
Функция поиска в поддереве find принимает игровое поле, узел дерева (tree) и координаты клетки (i, j), с которой нужно начать двигаться по полу, спускаясь по дереву tree:

  • 1) Если tree->wrd!=NULL, то обнаружена валидная подстрока
    • a. Если данный узел принадлежал словарному дереву, то эта подстрока вообще словарное слово, добавляем tree->wrd в массив обнаруженных слов.
    • b. Если узел принадлежал инвертированному дереву, то эта подстрока является инвертированным префиксом слова. В словарном дереве находим узел t, соответствующий этому префиксу, и вызываем функцию find для t и клетки [x, y] (внимание! Не та клетка, которую передали в эту функцию, а клетка, в которую алгорифм сходил на шаге 3):
      TREE *t=root;			//корень словарного дерева
      loopi(strlen(prefix))		//prefix содержит обнаруженный инвертированный префикс
      {
      	int k=ind(prefix[i],t->str);
      	t=t->next[k];
      }
      find(t,x,y);
      
  • 2) Самостоятельно от значения tree->wrd продолжаем
  • 3) Перебираем клетки, смежные с [i, j] (от 2-х в углу до 4-х в центре поля)
  • 4) Анализируем содержимое нынешней смежной клетки [i1, j1]
    • a. Если она пустая, то переходим на шаг (3)
    • b. Если буква, находящаяся в этой клетке, не имеется в tree->str, то переходим на шаг (3)
    • c. Если count[i1, j1]==0, то переходим на шаг (3)
    • d. Напротив переходим на шаг (5)
  • 5) Среди tree->next[] находим узел tnext, соответствующий букве в [i1, j1]
  • 6) Сокращаем счетчик применения count[i1, j1] и вызываем find для tnext и клетки [i1, j1]
  • 7) Конец цикла по смежным буквам

Разглядим работу алгорифма для центральной клетки на примере дальнейшей позиции:

Заносим в эту клетку всякую букву из строки ”адлбкнрусм” (остальные буквы алфавита легко не существуют в root_inv->str и алгорифм для них стремительно завершится, даже не начавшись). Для всякой буквы вызываем find. Для буквы А функция стремительно завершится, потому что в инвертированном дереве нет веток, начинающихся на АА-, АС- и АКУ-, то же самое и для Д, К, У, С.

Для остальных букв в инвертированном дереве будут обнаружены валидные префиксы:
Л – лаб, Б – б, Н – наб, Р – невольник, М – м. Для всякого префикса находим узел в словарном дереве (как описано в п.1.b) и вызываем для него функцию find.
Префиксу “бал” соответствует узел root->next[0]->next[0]->next[0]:

Дальнейшей смежной буквой может быть С либо К, но в поле str этого узла содержится “д”, следственно сразу завершаем функцию find, т.е. в дереве нет веток, начинающихся на БАЛС- и БАЛК-. Для префикса “б”в словарном дереве нет веток, начинающихся на БК-, БС-, БАБ-, БАЪ-, то же самое и для префиксов “бан”и “м”.

Префиксу “бар” соответствует узел root->next[0]->next[0]->next[2].
Т.к. поле wrd!=NULL, заносим строку wrd (БАР) в массив обнаруженных слов и продолжаем поиск дальше. Для строк БАРК и БАРСЪ нет веток, завершаем для них функциюfind, а вот строка БАРСУКсодержится в дереве, помещаем её в массив обнаруженных слов.

Итоги

Алгорифм тестировался на дальнейшем поле (безусловно теснее не на тестовом словаре, а на словаре из 110000 слов):

Спрятанный текст

Это реально игравшаяся партия.
Тут поле 9х9, и оно наполовину заполнено (вероятно, это одна из наихудших позиций для всякого алгорифма, потому что присутствует довольно много клеток, куда дозволено сходить, и довольно успешное взаимное расположение букв, из-за чего много длинных слов дозволено составить). В режиме узелки алгорифм находит все слова за следующее время:

  • 1) Mac mini i7 – 7 миллисекунд (не нативное приложение, а в эмуляторе iPhone)
  • 2) Комп. с i5 – 12 миллисекунд
  • 3) iPad 4 – 30 миллисекунд
  • 4) Samsung Galaxy Ace (сталь трёхлетней давности) – 50 миллисекунд (с применением NDK)

Для других позиций время поиска еще поменьше.

Приложение

Данный алгорифм применен в приложениях для iOS (доступно в app store) и Android. Помимо поиска всех слов реализованы ещё два вида поиска:

  • 1) Локальный поиск – если пользователю позарез необходимо занять какую-либо определённую пустую клетку (скажем, призовая клетка, либо прикрыть своим ходом клетку, в которой слишком много длинных слов), тогда он делает двойственный тап по этой клетке и программа ищет только те слова, которые дозволено сходить в неё
  • 2) Проверка подстав – двойственный тап по букве принудит программу обнаружить все слова, проходящие через эту букву. Использование: сразу позже хода конкурента проверить его букву (внезапно он жестко подставился), перед своим ходом следует проверить полагаемый ход на предмет подстав

Ещё одна специфика: идентичные по длине слова сортируются по редкости добавляемой буквы (скажем, сходить буквой Ч выигрышнее, чем буквой А).

 

Источник: programmingmaster.ru

 

Оставить комментарий
БАЗА ЗНАНИЙ
СЛУЧАЙНАЯ СТАТЬЯ
СЛУЧАЙНЫЙ БЛОГ
СЛУЧАЙНЫЙ МОД
СЛУЧАЙНЫЙ СКИН
НОВЫЕ МОДЫ
НОВЫЕ СКИНЫ
НАКОПЛЕННЫЙ ОПЫТ
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB