Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Поиск слов для игры "Балда"


Автор: Superklug 6.2.2007, 10:06
Дорый день. smile

Я думаю все знакомы с этой игрой в слова, поэтому в подробности вдаваться не буду.
Есть поле размером 5x5 клеток. В некоторых клетках стоят буквы. Необходимо составить все возможные на этом поле слова.
В принципе я уже все сам написал, но алгоритм слишком медленно работает.

Если есть какие-нибудь мысли, пишите. Заранее спасибо!

P.S. Если надо, могу описать свой алгоритм.

Автор: nini 6.2.2007, 11:30
Привет,
Давай алгоритм в общих чертах   smile   =)
Мож слишком много вложенных циклов взял? Чего-ниб по экспоненте =)?, поэтому и медленный...

Автор: Strannik 6.2.2007, 11:38
А как слова могут быть расположены на этом квадрате?

 Если словарь большой, то основное время уходит на поиск слова в словаре. Попробуй организовать словарь как хэш-таблицу... Тогда время обращения в среднем (при хорошей хэш-функции) будет О(1).

Автор: _Evrey_ 7.2.2007, 10:30
Есть исходники данной игры написанна на Делфи, скорость заполнения всего поля 5 Х 5 при словаре 9237 слов примерно 2 минуты 5 секунд, начальное слово парта....
вот ссылка на http://slil.ru/23887538 .
Когда в нее играли победить ее было непросто, если честно играть...

Автор: nerezus 7.2.2007, 14:50
я бы делл так:
составляется словарь, сортируется
цикл по х: цикл по у: рекурсивный перебор по направлениям(верх, них, лево, право) до тех пор, пока начало слова есть в словаре.

Автор: Superklug 7.2.2007, 18:20
Цитата(Strannik @  6.2.2007,  11:38 Найти цитируемый пост)
А как слова могут быть расположены на этом квадрате?

Как угодно smile Читать можно в любых направлениях. Игрок должен за свой ход поставить одну букву на поле и составить слово с этой буквой.

Цитата(Strannik @  6.2.2007,  11:38 Найти цитируемый пост)
Если словарь большой, то основное время уходит на поиск слова в словаре.

Словарь и вправду огромный. Но проблема в том, что процесс долгий даже если вообще не пользоваться словарем. Т.е. долго идет поиск всех возможных комбинаций.

Цитата(_Evrey_ @  7.2.2007,  10:30 Найти цитируемый пост)
Есть исходники данной игры написанна на Делфи

Большое спасибо за ссылку. Я когда искал не смог найти... Посмотрим что там...

Цитата(nini @  6.2.2007,  11:30 Найти цитируемый пост)
Давай алгоритм в общих чертах   

Сейчас попробую описать...
Значит так. 
Во-первых я создаю массив 5x5 целых чисел и заполняю его след. образом: Если в соответствующей клетке стоит буква - 1; если клетка является соседней - 0; иначе - -1.
Затем для каждой соседний клетки (0 в нашем массиве) выполняю следующие: сначала запускаю рекурсию, которая составляет все возможные пути, начинающиеся в этой клетке; затем из того, что нашел составляю все возможные комбинации (т.к. введенная буква может быть в середине слова).
После того, как проделаю это для всех клеток (для всех соседних клеток) ищу в базе слов. Т.е. у меня есть множество разных комбинаций вида апр?ап, опы?ф, ?фы, где "?" - это любая буква.
Надеюсь понятно объяснил... Если надо подробней или если нужен код, скажите smile

Сейчас пришла мысль: я сначало составляю все возможные комбинации, и затем ищу их в словаре, а может лучше перебирать все слова из словаря и проверять можно ли их вписать?
Кстати может у кого-нибудь есть словарь? А то мой ну уж очень огромный...

Может быть не в тему, но все же спрошу. У меня программа зависает если очень много операций... Как сделать так, чтобы этого не было? Пусть ищет долго, но не виснет. И еще если начинается поиск, то его нельзя прервать. Как это исправить? Может там в цикл какаую-нибудь задержку вставить надо?

Автор: nerezus 7.2.2007, 19:18
Цитата

Если словарь большой, то основное время уходит на поиск слова в словаре.
 Сортировка по алфавиту рулит )

Автор: _Evrey_ 8.2.2007, 07:12
Цитата(Superklug @  7.2.2007,  18:20 Найти цитируемый пост)
Сейчас пришла мысль: я сначало составляю все возможные комбинации, и затем ищу их в словаре, а может лучше перебирать все слова из словаря и проверять можно ли их вписать?
Кстати может у кого-нибудь есть словарь? А то мой ну уж очень огромный...

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

Цитата(Superklug @  7.2.2007,  18:20 Найти цитируемый пост)
Кстати может у кого-нибудь есть словарь? А то мой ну уж очень огромный...

В том архиве есть мой словарь, в принципе с ним уже трудно играть...

Цитата(Superklug @  7.2.2007,  18:20 Найти цитируемый пост)
У меня программа зависает если очень много операций... Как сделать так, чтобы этого не было? Пусть ищет долго, но не виснет. И еще если начинается поиск, то его нельзя прервать. Как это исправить? Может там в цикл какаую-нибудь задержку вставить надо?

Задержки замедлят алгоритм, а так лучше всего поиск выделить в отдельный поток, или если пишешь под Borland Builder то поставь в начале цикла Application->ProcessMessages().

Автор: Superklug 8.2.2007, 11:00
Цитата(_Evrey_ @  8.2.2007,  07:12 Найти цитируемый пост)
поэтому словарь нужно сортировать именно по количеству букв в слове 

Это понятно... Дело в том, что мне нужно найти все возможные слова, а не самое длинное. А слова точно нужно в таком порядке располагать. (например если на поле всего 7 символов, то не имеет смысла искать среди слов из 9 символов)

Цитата(_Evrey_ @  8.2.2007,  07:12 Найти цитируемый пост)
или если пишешь под Borland Builder то поставь в начале цикла Application->ProcessMessages().

smile надо было наверное об этом раньше сказать... Да я пишу на билдере. Попробую.

Автор: _Evrey_ 8.2.2007, 15:04
Цитата(Superklug @  8.2.2007,  11:00 Найти цитируемый пост)
Дело в том, что мне нужно найти все возможные слова, а не самое длинное.

Ну это немного другая задача... Вот набрасал быстро код на c++ Builder выполняет то что тебе нужно, из текущего состояния выберает все слова которые подходят... Будет что-то непонятно по коду, спрашивай отвечу...
Данный кусок кода выводит все найденные слова в компонент TListBox1 на форме...
Данный код не оптимальный и возможно имеет ошибки, особо не проверял но работает быстро...
Код

 TStringList *List = new TStringList;
 String a[5][5];
 String temp[5][5];
 int pr[5][5];
 int temp_pr[5][5];
 int i,j,k,p,t;
 int ai = i,aj = j; // Временные переменные для сохранения позиции в массиве
 int curr;
 String word;
 bool bl;
 bool tl;
 List->LoadFromFile("word.txt");
 for(i=0;i<5;i++)
  for(j=0;j<5;j++)
   a[i][j] = " ";

 memset(pr,0,sizeof(int)*5*5);
 memset(temp_pr,0,sizeof(int)*5*5);

 a[3][0] = "п";
 a[3][1] = "а";
 a[3][2] = "р";
 a[3][3] = "т";
 a[3][4] = "а";

 pr[3][0] = 2;
 pr[3][1] = 2;
 pr[3][2] = 2;
 pr[3][3] = 2;
 pr[3][4] = 2;

 memcpy(temp_pr,pr,sizeof(int)*5*5);
 curr = 0;
 try
 {
   while(curr<List->Count)//Цикл по словарю
   {
    Application->ProcessMessages();
    word = List->Strings[curr];
    memcpy(pr,temp_pr,sizeof(int)*5*5);
    tl = true;
    for(k=1;k<word.Length();k++) //Цикл по слову из словаря
    {
     for(i=0;i<5;i++) // Цикл по самому массиву.
     {
      for(j=0;j<5;j++)
      {
       if(a[i][j]==" ")
       {
        for(ai=0;ai<5;ai++)
         for(aj=0;aj<5;aj++)
          temp[ai][aj] = a[ai][aj];  // сохранили массив, для возврата в предыдущее состояние.
        a[i][j] = String(word[k]);
        bl = true;
        p = k; // С какой буквы подставляли для поиска в конец слова
        t = k; // С какой буквы подставляли для поиска в начало слова
         ai = i;
         aj = j;
         memcpy(pr,temp_pr,sizeof(int)*5*5);
         pr[i][j] = 1;
         for(p = p+1;p<=word.Length();p++)
         {
          if(ai+1!=5)
            if((a[ai+1][aj]==word[p])&&(pr[ai+1][aj]!=1))
            {
             pr[ai+1][aj] = 1;
             ai++;
             continue;
            }
          if(ai-1!=-1)
            if((a[ai-1][aj]==word[p])&&(pr[ai-1][aj]!=1))
            {
             pr[ai-1][aj] = 1;
             ai--;
             continue;
            }
          if(aj+1!=5)
            if((a[ai][aj+1]==word[p])&&(pr[ai][aj+1]!=1))
            {
             pr[ai][aj+1] = 1;
             aj++;
             continue;
            }
          if(aj-1!=-1)
            if((a[ai][aj-1]==word[p])&&(pr[ai][aj-1]!=1))
            {
             pr[ai][aj-1] = 1;
             aj--;
             continue;
            }
          bl = false; // Если не совпало ни одно условие выше то это слово не подходит.
          break;
         }
         ai = i;
         aj = j;
         if(bl)
         {
           for(t = t-1;t>0;t--)
           {
            if(ai+1!=5)
              if((a[ai+1][aj]==word[t])&&(pr[ai+1][aj]!=1))
              {
               pr[ai+1][aj] = 1;
               ai++;
               continue;
              }
            if(ai-1!=-1)
              if((a[ai-1][aj]==word[t])&&(pr[ai-1][aj]!=1))
              {
               pr[ai-1][aj] = 1;
               ai--;
               continue;
              }
            if(aj+1!=5)
              if((a[ai][aj+1]==word[t])&&(pr[ai][aj+1]!=1))
              {
               pr[ai][aj+1] = 1;
               aj++;
               continue;
              }
            if(aj-1!=-1)
              if((a[ai][aj-1]==word[t])&&(pr[ai][aj-1]!=1))
              {
               pr[ai][aj-1] = 1;
               aj--;
               continue;
              }
            bl = false; // Если не совпало ни одно условие выше то это слово не подходит.
            break;
           }
           if(bl)
           {
            ListBox1->Items->Add(word);
            for(ai=0;ai<5;ai++)
             for(aj=0;aj<5;aj++)
              a[ai][aj] = temp[ai][aj];  // восстановили массив, в текущем состоянии.
            tl = false;
            break;   // Слово подошло переходим к следующему слову
           }
         }
          for(ai=0;ai<5;ai++)
           for(aj=0;aj<5;aj++)
            a[ai][aj] = temp[ai][aj];  // восстановили массив, в текущем состоянии.
       }
      }
      if(!tl)
       break;
     }
    }
    curr ++;
   }
 }
 catch(...)
 {
  ShowMessage(word);
 }
 delete List;

Автор: SelenIT 8.2.2007, 19:29
Имхо, для уменьшения числа переборов нужно отсекать пути с невозможными сочетаниями букв (типа "ЪЩ" или "ОЬ") до любых обращений к словарю. AFAIK, на списках таких исключений работают автопереключалки раскладки клавиатуры (типа PuntoSwitcher), из какой-нибудь из них и можно "выдрать" такой список...

Автор: Superklug 9.2.2007, 17:36
Цитата(_Evrey_ @  8.2.2007,  15:04 Найти цитируемый пост)
Данный код не оптимальный и возможно имеет ошибки, особо не проверял но работает быстро...

Да есть ошибки smile Я не люблю разбираться в чужом коде, поэтому писал сам, а уже потом с твоим сравнивал. Некоторые вещи не понимаю. 
Например:
Зачем нужно использовать try и catch?
Еще не понятно зачем ты делал вот это
Код

a[i][j] = String(word[k]);

И следовательно вот такие вещи
Код

for(ai=0;ai<5;ai++)
 for(aj=0;aj<5;aj++)
   temp[ai][aj] = a[ai][aj]; 


Вобщем-то идея у меня такая же. Проверять подходят ли начало и конец слова. Но есть и отличая, например я это проверяю не для всех пустых клеток, а только для соседних. И еще я не все слова из словаря перебираю, а только те, длина которых меньше или равна количеству букв на поле +1.

Большое тебе спасибо smile

Цитата(SelenIT @  8.2.2007,  19:29 Найти цитируемый пост)
Имхо, для уменьшения числа переборов нужно отсекать пути с невозможными сочетаниями букв (типа "ЪЩ" или "ОЬ") до любых обращений к словарю. AFAIK, на списках таких исключений работают автопереключалки раскладки клавиатуры (типа PuntoSwitcher), из какой-нибудь из них и можно "выдрать" такой список... 

Это если сначала составлять комбинации, а затем искать по ним слова в словаре. Я сейчас по другому делаю. Перебираю слова из словаря и проверяю можно ли их вписать на данное поле. (так быстрее получается даже с моим словарем)

Автор: _Evrey_ 9.2.2007, 19:57
Цитата(Superklug @  9.2.2007,  17:36 Найти цитируемый пост)
Да есть ошибки  Я не люблю разбираться в чужом коде, поэтому писал сам, а уже потом с твоим сравнивал.  

В принципе правильно  smile 
try, catch - для отлова ошибок, в начале когда писал выходил за границы массивов и строк, вываливалось исключение, которое в этом блоке отлавливал...

a[i][j] = String(word[k]);
Это у меня такой стиль програмирования, иногда сталкивался с проблемой что компилятор при компилировании кода переводил цифры в ASCII символы, подразумевая что у меня там используется тип char....

for(ai=0;ai<5;ai++)
 for(aj=0;aj<5;aj++)
   temp[ai][aj] = a[ai][aj];
Так сохранял массив, потом его востанавливал, необходимо для того чтобы поле после подстановки букв имело первоначальный вид... 

Автор: Superklug 10.2.2007, 01:16
Цитата(_Evrey_ @  9.2.2007,  19:57 Найти цитируемый пост)
a[i][j] = String(word[k]);
Это у меня такой стиль програмирования, иногда сталкивался с проблемой что компилятор при компилировании кода переводил цифры в ASCII символы, подразумевая что у меня там используется тип char....

for(ai=0;ai<5;ai++)
 for(aj=0;aj<5;aj++)
   temp[ai][aj] = a[ai][aj];
Так сохранял массив, потом его востанавливал, необходимо для того чтобы поле после подстановки букв имело первоначальный вид...  


Я имел ввиду, что это в принципе не нужно. Т.е. не надо подставлять буквы. Ты ведь добавляешь в массив pr 1 - этого достаточно.

У меня вопрос  smile 
Помнишь ты говорил, про Application->ProcessMessages()? Так вот это не совсем то, что мне нужно. Мне нужно, чтобы можно было отменить процесс поиска. Как это сделать?

Автор: Anikmar 10.2.2007, 01:20
Цитата(Superklug @  10.2.2007,  01:16 Найти цитируемый пост)
Мне нужно, чтобы можно было отменить процесс поиска. Как это сделать? 

Имеется в виду поиск в БД?

 А какая БД используется?

Автор: Superklug 10.2.2007, 01:51
Цитата(Anikmar @  10.2.2007,  01:20 Найти цитируемый пост)
Имеется в виду поиск в БД?

 А какая БД используется? 

Нет, БД не использую. Может быть и нужно, но я не умею... smile А это важно? Я думаю все намного проще. Как сделать чтобы реакция на нажатие кнопки "Отмена" наступала сразу, а не после окончания процесса?

P.S. Что-то мы не в той теме об этом говорим...

Автор: Anikmar 10.2.2007, 02:03
Цитата(Superklug @  10.2.2007,  01:16 Найти цитируемый пост)
Помнишь ты говорил, про Application->ProcessMessages()? Так вот это не совсем то, что мне нужно. Мне нужно, чтобы можно было отменить процесс поиска. Как это сделать? 

Вам уже был совет, поэтому я уточнил.

Цитата(Superklug @  10.2.2007,  01:51 Найти цитируемый пост)
Нет, БД не использую. Может быть и нужно, но я не умею...  А это важно? Я думаю все намного проще. Как сделать чтобы реакция на нажатие кнопки "Отмена" наступала сразу, а не после окончания процесса?

Пользуйтесь вышеприведенным советом. В процессе поиска опрашиваете некий внешний раздражитель (нажатие на клавишу, мышьку, щелчок на кнопке) - если случилось прерывайте поиск. Опрашивать следует в самом внутреннем цикле.

Автор: _Evrey_ 10.2.2007, 17:50
Для того чтобы предотвратить цикл необходимо выставить глобальную переменную, и в цикле проверять, если значение изменилось то выход, например...
Код

bool is_exit = false;
for(int i=0;i<100000;i++)
{
  if(is_exit)
    break;
 for(j=0;j<1000000;j++)
 {
   if(is_exit)
     break;
  while(true)
  {
    if(is_exit)
      break;
    Application->ProcessMessage(); // Это необходимо для того чтобы основное приложение, принимала 
                                                        // события.
    // Производятся какие то вычисления...
  }
 }
}

............

void __fastcall Form1::Button1Click(Object *Sender)
{
 is_exit = true;
}

Проверять выход лучше всего вначале цикла.. 

Автор: Toska 27.10.2007, 19:56
тут были выложены исходники.... 
ссылка устарела :wack 

выложите пожалуйста снова  smile 

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)