Дорый день. 

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

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

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

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

А как слова могут быть расположены на этом квадрате?

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

Есть исходники данной игры написанна на Делфи, скорость заполнения всего поля 5 Х 5 при словаре 9237 слов примерно 2 минуты 5 секунд, начальное слово парта....
вот ссылка на исходники .
Когда в нее играли победить ее было непросто, если честно играть...

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

Это сообщение отредактировал(а) nerezus - 7.2.2007, 14:51

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


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


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


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

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

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

 Сортировка по алфавиту рулит )

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


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


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

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


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

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

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

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

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


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

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


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

В принципе правильно   
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];
Так сохранял массив, потом его востанавливал, необходимо для того чтобы поле после подстановки букв имело первоначальный вид... 

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

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

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

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

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

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

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


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

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

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

тут были выложены исходники.... 
ссылка устарела :wack 

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