Главная · Карта сайта · Поиск · Статьи · Компьютерные курсы · Обучающие программы · Открытые проекты · Веб-программирование · Создание интернет-сайта · Полезные ссылки · Глоссарий · Контакты · Декабрь 09 2016 22:15:47
Последнее опубликованное

Что такое Model-View-Controller
Pattern Model-View-Controller

Как создать свой веб-сайт
Как создать свой сайт в интернете

Разное
Статистика

Генератор кроссвордов crossWORDcraft™. Описание алгоритма


Задачи полного перебора

О программе
Описание проекта

Генератор кроссвордов crossWORDcraft. Описание алгоритма

Метод полного перебора, его применение и вычислительная сложность.

К алгоритмам полного перебора обращаются тогда, когда нет других способов решить определенную задачу. Например, никому в голову не придет решать квадратное уравнение перебором всех возможных значений, даже если известно, что решением являются целые числа. Полный перебор – это решение “в лоб”, построенное на подстановке и проверке всех возможных вариантов из области допустимых значений. На словах в решении задачи полного перебора нет ничего сложного, но на деле алгоритмы, которые действительно ищут и находят решения подобным способом за “приемлемое время” довольно таки непростые. К наиболее популярным задачам, решение которых методом полного перебора рассматривают в школах и ВУЗах (в рамках дисциплин, связанных с комбинаторикой и программированием) можно отнести заполнение прямоугольной области фигурками из тетриса, поиск выхода из лабиринта, задачу о рюкзаке, поиск связанных областей и т.п. Многие задачи на графах также можно решать с помощью полного перебора, хотя для их решения придуманы специальные методики – оптимальные с точки зрения количества операций алгоритмы, которые осуществляют поиск решений на порядки быстрее, чем обычный полный перебор. К таким задачам относят поиск кратчайшего маршрута между вершинами (алгоритм Дейкстры) или поиск максимального пропускного потока в графе. Если обобщить все вышесказанное, то для решения некоторой задачи методом полного перебора нужно разработать алгоритм перебора всех возможных кандидатов на решение и реализовать процедуру проверки корректности решения для каждого из них.

Вычислительная сложность алгоритмов полного перебора оценивается по следующей обобщенной формуле:

O(N!/(N-R)!)

, где N – количество элементов в области поиска решений, а R – количество элементов, образующих одно целое решение задачи. Если вернуться к задаче поиска всех вариантов заполнения кроссворда, то ее сложность, в самом простом варианте, можно оценить так:

N*(N-1)*… *(N-(W-1))

, где N – количество слов в словаре, а W – количество шаблонов слов в кроссворде. На каждом последующем шаге предстоит перебрать на одно слово меньше, чем на предыдущем, поскольку повторяться в выборе слов нельзя. А это и есть не что иное, как N!/(N-W)! Естественно, что слов в словаре должно быть не меньше, чем их шаблонов в кроссворде, иначе решений вообще нет. Если слов в кроссворде более десятка, а в словаре для его заполнения, например, более тысячи слов, то общее число вариантов, которые нужно перебрать для поиска всех решений впечатлит количеством разрядов даже “видавших виды” суперкомпьютеры. Из всего это следует одно, что если задача не решается никак, кроме полного перебора, то алгоритм этого полного перебора должен быть “оптимальным”. Слово “оптимальный” я взял в кавычки, поскольку строгое доказательство оптимальности таких алгоритмов задача еще более сложная, чем разработка самих алгоритмов. В контексте этой статьи вместо термина “оптимальный” я буду использовать термин “удовлетворительный”. Удовлетворительным будем считать тот алгоритм, который находит хотя бы одно решение задачи за удовлетворительное для пользователя время. Этот термин “размыт” и имеет мало общего с точными науками, к коим относится алгоритмизация, но в нашем случае выбирать не приходится.

Итак, в этой статье я хочу описать ряд приемов, которые я использовал в программе crossWORDcraft, для того чтобы алгоритм заполнения шаблона кроссворда можно было назвать хотя бы удовлетворительным. Я не считаю свой алгоритм ни “оптимальным” ни даже “хорошим”, но при выбранной архитектуре решения я пока не смог придумать ничего лучше. Под выбранной архитектурой я понимаю конкретную организацию хранения шаблона кроссворда, массива шаблонов слов, их пересечений и самого словаря. Буду рад, если кто поделится своими соображениями, как усовершенствовать этот алгоритм, или предложит свой вариант.

Оптимизация алгоритма полного перебора

Оптимизация любого алгоритма должна проходить, как минимум, по двум направлениям: в направлении минимизации количества элементарных операций и в направлении оптимизации скорости выполнения этих элементарных операций. Второе направление в основном связано с оптимизацией используемых структур данных и операций доступа к ним. Наиболее популярными методами сокращения времени выполнения элементарных операций являются кэширования часто используемых данных, откладывание инициализации и различного рода вычислений до момента, когда в них появится необходимость, побитное сравнение и т.п. Нужно понимать, что расход памяти и скорость выполнения операций – это две противоположные характеристики. За счет создания дополнительных "хитрых" структур данных в оперативной памяти можно увеличить быстродействие и наоборот: если не сохранять результаты промежуточных вычислений и стараться все необходимые расчеты каждый раз производить заново, то можно выиграть в объемах памяти, но существенно проиграть в скорости работы программы. Признаюсь, особых изысканий, связанных с этого рода оптимизациями я не проводил, просто старался не делать лишних движений и ненужных действий.

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

Как только найдены решения для всех элементов – найдено все решение. Дальше, алгоритм сохраняет вариант решения и продолжает искать другие. В ходе анализа рекурсивного алгоритма полного перебора очень важно уметь давать оценку, содержит ли текущая ветвь рекурсии решения, или ее можно отсечь. Например, стоит ли пытаться расставлять остальные слова в кроссворде, когда вы наткнулись на неразрешимое пересечение: в словаре нет слов нужной длины для подстановки в шаблон с соблюдений условий пересечения. Анализ и отсечение заведомо “безрезультатных” ветвей рекурсии называется методом ветвей и границ. Оптимизация алгоритмов полного перебора может проводиться с использованием эвристического подхода к решению задачи. Этот подход связан с набором предположений, правильность которых доказать или сложно или формально невозможно, но следование им позволяет находить решения достаточно быстро. Напомню, что цель предпринимаемой оптимизации - как можно скорее найти хотя бы одно решение, а не все варианты заполнения кроссворда. Таким образом, оптимизация рекурсивного алгоритма полного перебора, направленная на минимизацию количества элементарных операций (операций сравнения, выбора и т.п.) осуществляется за счет применения двух подходов:

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

Оптимизация алгоритма генерации кроссворда

В двух словах представленный алгоритм делает следующее: сначала расставляет слова в одном направлении – первая линия (GenerateFirstLine), а потом пытается расставить слова в другом направлении с учетом пересечений – вторая линия (GenerateSecondLine). Понятно, что в ходе заполнения первой линии не нужно учитывать никакие пересечения, а достаточно просто подбирать слова соответствующей шаблону длины.

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

Представленный алгоритм является рекурсивным: на каждом шаге осуществляется поиск подходящего варианта для конкретного шаблона слова и, если поиск удачен, осуществляется переход к следующему шаблону. Решения для последовательности шагов в рамках одной линии слабо зависимы, поскольку связаны только проверкой, не использовано ли конкретное слово из словаря при заполнении шаблона на предыдущих шагах (заполнение нескольких шаблонов слов одним и тем же значением запрещено!). Но шаги второй линии очень и очень зависят от найденных решений первой линии…

Вторая оптимизация - эвристический подход. Делаем предположение, что если шаблоны слов, заполняемых на первой линии отсортировать по возрастанию, а шаблоны слов второй линии – по убыванию длины, то это поможет быстрее найти первый готовый вариант заполненного кроссворда. Мотивация следующая:

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

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

Третья оптимизация - метод ветвей и границ. Если поиск значения для шаблона слова в рамках второй линии не приносит результата, на предыдущем шаге заполнялся шаблон той же линии (той же ориентации), то нет никакого смысла возвращаться на предыдущий шаг рекурсии, если длина предыдущего шаблона больше (помним, что длины шаблонов отсортированы по убыванию). Смысла в этом нет, поскольку в данном случае все предыдущие решения второй очереди независимы с решением для текущего шаблона слова. Имеет смысл вернуться к тому шаблону первой очереди, с которым есть пересечение. Если пересечений несколько, то выбираем ближайший шаг рекурсии – шаблон с наибольшей ординатой.

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

Компьютерные курсы и курсы программирования
Основы программирования

Курс для начинающих программистов на C# и VB.NET.

SQL 25™

Построение SQL запросов и работа с базой данных.

C# Quick Guide™

Программирование на C#. Краткое руководство.

RegEx

Применение регулярных выражений.

Plug-in архитектура

Примеры программной Plug-in архитектуры.

XML и его расширения

Язык разметки XML и его расширения с примерами.

HTML и разметка гипертекста

Языки HTML, XHTML и CSS с примерами разметки.

Основы веб-дизайна

Основы веб-дизайна: решения типовых задач верстки.

Программирование на PHP

Руководство по программированию на PHP для начинающих.

Справочные материалы

Шаблоны проектирования
Каталог шаблонов проектирования программных компонентов.

Рефакторинг кода
Каталог приемов рефакторинга программного кода.

Гость
Имя

Пароль



Забыли пароль?
Запросите новый здесь
.
Coding Craft. Все права защищены © 2011. Проект Инициативного Народного Фронта Образования - ИНФО-проект.