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

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

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

Отправить личное сообщение для mr.Anderson Посмотреть профиль Найти все сообщения от mr.Anderson
 
Регистрация: 23.04.2009
Сообщений: 2

Генетика для составления кроссворда
Поставлена задача следующего плана.

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

Если я правильно понял, здесь лучше использовать генетический алгоритм. Почитал про них в википедии, но, честно говоря, мало что понял. Подскажите, как можно применить генетику к моей задаче?
  #2  
Старый 25.04.2009, 00:17
Аватар для pavlinux
Пользователь

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

1. Делаешь нулевую матрицу MxN = {0}
2. слова помечаешь 1
3. пересечения -1 (иль наоборот)
4. делаешь функию обхода по строкам
5. ...................................по столбцам
6. ......................... cравнение ( x < 0 )
7. берёшь эл-т [1; 1] и почесал...

вычисляешь длину строки (столба), на основании этого ищешь слово (по рандому) или наоборот берешь слово ищешь строку (стольб.)

Если есть задача о том что количество слов и знаков равно количеству строк и стобцов и символов и однозначно известно что они туда входят
  #3  
Старый 25.04.2009, 00:59
Новичок

Отправить личное сообщение для mr.Anderson Посмотреть профиль Найти все сообщения от mr.Anderson
 
Регистрация: 23.04.2009
Сообщений: 2

Не совсем понял. Сделали матрицу заданного размера, то, что некоторые клетки могут быть выброшены пользователем - это учитывать как-то? Слова помечаем единицами, ну, допустим, изначально ведь матрица пуста. Теперь обход по строкам... Пошли по строкам... А ищем-то что? Матрица пустая. Везде нули. Что делаем-то? ПОясните поподробнее, пожалуйста.
  #4  
Старый 10.12.2010, 01:52
AlekseyVoronezh

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

кроссворд
Здравствуйте, передо мной стоит аналогичная задача. Разработка генератора кроссвордов на заданном пользователем поле.
Пока что решил эту задачу обычном поиском в ширину,но скорость генерации просто удручающая. Набрел на эту тему на форуме и очень заинтересовался.
pavlinux или кто то еще разбирающийся в генетическом алгоритме ,прошу помочь и объяснить по-подробнее.
Иные методы так же с радостью приму к сведению. Так же подскажите, какой вариант предпочтительнее -сразу вставлять слова в квадратную (прямоугольную) матрицу или же сначала рандомно выделить сеть полей под слова,а уже потом подбирать под них слова. Извиняюсь за тавтологию .
Заранее большое спасибо.
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
решение линии японского кроссворда iposov Задачи 1 14.10.2006 03:22