| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Центр помощи > [Алгоритм] Крисс-кросс |
| Автор: mr.Anderson 5.4.2009, 20:35 |
| Собственно задача. Есть список слов, требуется по нему составить максимально связную кроссвордную сетку. Крисс-кросс отличается от кроссворда только тем, что не содержит нумерации и вопросов к кроссворду, отсюда сетка крисс-кросса всегда имеет одно решение. А вот вариантов сетки по заданному списку слов может быть много. Прошу помочь хотя бы мыслью в методике решения задачи. Составить сетку не особая проблема, я думаю, а вот как сделать ее максимально связной? Были мысли подсчитать, сколько раз, в каких словах и на каких позициях встречается каждая из букв русского алфавита, но что это даст? |
| Автор: zim22 5.4.2009, 20:51 |
| гугл помимо всего прочего выдал такую фразу: The solving of „criss-cross“ crossword using genetic algorithm |
| Автор: mr.Anderson 6.4.2009, 18:17 |
| Гм... Суть в том, что эта задача позиционируется как обычная лабораторная работа, по теме "перебор", то есть методика решения, как сказал препод, простой полный перебор. Просто я не могу понять, что в этом полном переборе и как конкретно мы должны считать. |
| Автор: zim22 6.4.2009, 20:19 | ||
я думаю, что необходимо генерировать варинты кроссводной сетки и считать количество пересечений каждого слова с другими словами. тот вариант кроссвордной сетки, в котором общее число пересечений всех слов со всеми словами будет максимально - и есть максимально-связная сетка. |
| Автор: mr.Anderson 6.4.2009, 21:04 |
| А как выполнить этот подсчет? Я просто не понимаю как считать... |
| Автор: zim22 6.4.2009, 21:09 | ||
так вы можете составить сетку или нет? во время составления сетки разве вы не определяете пересечения слов? *** каждое слово можно рассматривать как объект/структуру, содержащую внутри себя информацию об ссылках на другие слова, с которыми данное слово связано. останется лишь подсчитать общее количество ссылок. |
| Автор: mr.Anderson 6.4.2009, 21:09 |
| Точнее даже не так, не понимаю, как построить все возможные варианты сетки. |
