ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Eugene Kilachkoff                    2:5020/400     30 Nov 2002  19:16:41
 To : Igor Zakhrebetkov
 Subject : Re: венгерские кроссв  о  рды
 -------------------------------------------------------------------------------- 
 

 Igor Zakhrebetkov пишет:
 
 > По уму - не знаю. Я в свое время писал прогу, показывающую наличие слова
 > в заданной матрице букв. Если позиция слова в матрице - единственная, его
 > можно в ней "закрепить", чтобы не использовать эти буквы в других поисках.
 
 Это больше похоже на отгадывание. Интересует же обратная задача.
 Кстати, попутный вопрос. Есть ли быстрый способ обнаруживать запрещенные 
 комбинации ? Я делал опять же в лоб, простым сравнением с образцом.
 Под запрещенными комбинациями я понимаю появление областей, которые 
 невозможно полностью заполнить словами.
 
 Пример:
 1)
 XXX
 X.X
 XXX
 
 2)
 XXXX
 X..X
 XXXX
 
 3)
 XXXXX
 X...X
 XX.XX
 XXXXX
 
 Как вообще отличать эти области от других ? Может есть какие-то 
 характерные признаки ? Можно ли предсказать появление таких областей на 
 ранних шагах ? Сравнением с образцом можно отловить "плохую" комбинацию 
 непосредственно тогда, когда в нее упрешься, что весьма неоптимально. 
 Тем более, что один шаг - это изменение расположения одного слова в 
 одном месте. Если не обращать внимания на расположение первой буквы 
 слова, то получаем, что вторую можно расположить 4-мя способами, третью 
 - тремя, четвертую и последующие - тоже тремя или чуть меньше в 
 зависимости от расположения предыдущих. Hехилый получается комбинаторный 
 взрывчик ?
 
 Вопрос второй. Иногда встречаются ситуации, когда изменение расположения 
 слова, расположенного на каком-то очень старом шаге решает проблему 
 плохой комбинации. Как отлавливать такие ситуации (это не всегда 
 очевидно даже человеку) ? И что потом делать ? Можно запоминать текущее 
 состояние, пытаться строить какие-то оценки, но ИМХО это все как-то 
 неустойчиво что-ли...
 
 Что еще сюда можно прикрутить ? Клеточные автоматы ? Hапрашиваются ГА, 
 но надо придумать хорошее представление раскладки слов. Что брать в 
 кач-ве оценочной функции ? Здесь необходимо учитывать тот факт, что 
 слова должны быть искривлены и перепутаны. Кроссворд, в котором слова 
 расположены змейкой, это вообще не кроссворд ;-)
 
 --- ifmail v.2.15dev5
  * Origin: home (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор