Представление в пространстве состояний. Стратегии поиска в пространстве состояний.

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

Рассмотрим пример. Задача состоит в выработке плана переупорядочивания кубиков, поставленных друг на друга, как показано на рисунке. На каждом шагу разрешается переставлять только один кубик. Кубик можно взять только тогда, когда его верхняя поверхность свободна. Кубик можно поставить либо на стол, либо на другой кубик. Для того, чтобы построить требуемый план, мы должны отыскать последовательность ходов, реализующую заданную трансформацию.

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

· поставить А на стол или

· поставить А на С, или

· поставить С на А.

Ясно, что альтернативу "поставить С на A" не имело смысла рассматривать всерьез, так как этот ход никак не влияет на ситуацию.

Как показывает рассмотренный пример, с задачами такого рода связано два типа понятий:

1. Проблемные ситуации.

2. Разрешенные ходы или действия, преобразующие одни проблемные ситуации в другие.

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

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

Поиск в ширину исследует пространство состояний по уровням, один за другим. И только если состояний на данном уровне больше нет, алгоритм переходит к следующему уровню. При поиске в ширину на графе на рисунке состояния рассматриваются в таком порядке: A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U.

 

Поиск в ширину осуществляется с использованием списков open и closed, позволяющих отслеживать продвижение в пространстве состояний. Список open содержит сгенерированные состояния, потомки которых еще не были исследованы. Порядок удаления состояний из списка open определяет порядок поиска. В список closed заносятся уже исследованные состояния.

На каждой итерации генерируются все дочерние вершины состояния X и записываются в open. Список open действует как очередь и обрабатывает данные в порядке поступления (первым поступил – первым обслужен). Это структура данных FIFO. Состояния добавляются в список справа, а удаляются слева. Т.о. в поиске участвуют состояния, которые находятся в списке open дольше всего, обеспечивая поиск в ширину. Дочерни состояния, которые были уже записаны в списки open или closed, отбрасываются.

1. open = [A]; closed = []

2. open = [B, C, D]; closed = [A]

3. open = [C, D, E, F]; closed = [B, A]

4. open = [D, E, F, G, H]; closed = [C, B, A]

5. open = [E, F, G, H, I, J]; closed = [D, C, B, A]

6. open = [F, G, H, I, J, K, L]; closed = [E, D, C, B, A]

7. open = [G, H, I, J, K, L, M]; (так как L уже в open); closed = [F, E, D, C, B, A]

8. open = [H, I, J, K, L, M, N]; closed = [G, F, E, D, C, B, A]

И так далее, пока или U найдено, или open[].

При поиске в глубину после исследования состояния сначала необходимо оценить все его потомки и их потомки, а затем исследовать любую из вершин-братьев. Поиск в глубину по возможности углубляется в область поиска. Если дальнейшие потомки состояния не найдены, рассматриваются вершины-братья. Поиск в глубину исследует состояние графа на рисунке в таком порядке: A, B, E, K, S, L, T, F, M, C, G, N, H, O, P, U, D, I, Q, J, R.

Алгоритм. В этом алгоритме состояния-потомки добавляются и удаляются с левого конца списка open, т.е. список open реализован как стек магазинного типа или структура LIFO (последним пришел – первым обслужен). При организации списка open в виде стека предпочтение отдается самым “молодым”.

1. open = [A]; closed = []

2. open = [B, C, D]; closed = [A]

3. open = [E, F, C, D]; closed = [B, A]

4. open = [K, L, F, C, D]; closed = [E, B, A]

5. open = [S, L, F, C, D]; closed = [K, E, B, A]

6. open = [L, F, C, D]; closed = [S, K, E, B, A]

7. open = [T, F, C, D]; closed = [L, S, K, E, B, A]

8. open = [F, C, D]; closed = [T, L, S, K, E, B, A]

9. open = [M, C, D], as L is already on closed; closed = [F, T, L, S, K, E, B, A]

10. open = [C, D]; closed = [M, F, T, L, S, K, E, B, A]

11. open = [G, H, D]; closed = [C, M, F, T, L, S, K, E, B, A]

И так далее пока не будет обнаружено состояние U или open[].

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

 

Генетические алгоритмы.

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

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

В каждом поколении генетического алгоритма реализуется:

1. Формирование начальной популяции. Как правило, начальная популяция формируется случайным образом. При этом гены инициализируются случайными значениями.

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

- Рулеточная селекция. В данном варианте селекции вероятность i -й особи принять участие в скрещивании пропорциональна значению ее приспособленности и равна .Процесс отбора особей для скрещивания напоминает игру в «рулетку». Рулеточный круг делится на сектора, причем площадь i -го сектора пропорциональна значению . После этого n раз «вращается» рулетка, где n – размер популяции, и по сектору, на котором останавливается рулетка, определяется особь, выбранная для скрещивания.

- Селекция усечением. При отборе усечением после вычисления значений приспособленности для скрещивания выбираются лучших особей, где l – «порог отсечения», 0 < l < 1, n – размер популяции. Чем меньше значение l, тем сильнее давление селекции, т.е. меньше шансы на выживание у плохо приспособленных особей. Как правило, выбирают l в интервале от 0,3 до 0,7.

- Турнирный отбор. В случае использования турнирного отбора для скрещивания отбираются n особей. Для этого из популяции случайно выбираются t особей, и самая приспособленная из них допускается к скрещиванию. Говорят, что формируется турнир из t особей, t размер турнира. Эта операция повторяется n раз. Чем больше значение t, тем больше давление селекции. Вариант турнирного отбора, когда t = 2, называют бинарным турниром. Типичные значения размера турнира t = 2, 3, 4, 5.

3. Скрещивание. Отобранные в результате селекции особи (называемые родительскими) скрещиваются и дают потомство. Хромосомы потомков формируется в результате обмена частями хромосом между родительскими особями.

4. Формирование нового поколения. В результате скрещивания создаются потомки, которые формируют популяцию следующего поколения. Отметим, что обновленная таким образом популяция не обязательно должна включать одних только особей-потомков. Можно включить в новую популяцию наиболее приспособленные родительские особи (элитные особи). Использование элитных особей позволяет увеличить скорость сходимости генетического алгоритма.

5. Мутация. Оператор мутации используется для внесения случайных изменений в хромосомы особей. Это позволяет «выбираться» из локальных экстремумови, тем самым, эффективнее исследовать пространство поиска. Вероятность применения мутации невысока.

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

Наиболее популярное применение генетических алгоритмов - оптимизация многопараметрических функций. Многие реальные задачи могут быть сформулированы как поиск оптимального значения, где значение - сложная функция, зависящая от некоторых входных параметров. В некоторых случаях, представляет интерес найти те значения параметров, при которых достигается наилучшее точное значение функции. В других случаях, точный оптимум не требуется - решением может считаться любое значение, которое лучше некоторой заданное величины. В этом случае, генетические алгоритмы - часто наиболее приемлемый метод для поиска "хороших" значений. Сила генетического алгоритма заключена в его способности манипулировать одновременно многими параметрами, эта особенность ГА использовалось в сотнях прикладных программ, включая проектирование самолетов, настройку параметров алгоритмов и поиску устойчивых состояний систем нелинейных дифференциальных уравнений.

Базы данных:

Теория нормализации.

Под нормализацией отношения подразумевается процесс приведения отношения к одной из так называемых нормальных форм (или в дальнейшем НФ).

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

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

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

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

Процесс нормализации – последовательное преобразование исходной БД к НФ, при этом каждая следующая НФ обязательно включает в себя предыдущую (что, собственно, и позволяет разбить процесс на этапы и производить его однократно, не возвращаясь к предыдущим этапам).

Всего в реляционной теории насчитывается 6 НФ:

1. Первая нормальная форма (1NF):

- запрещает повторяющиеся столбцы (содержащие одинаковую по смыслу информацию);

- запрещает множественные столбцы (содержащие значения типа списка и т.п.);

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

2. Вторая нормальная форма (2NF):

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

3. Третья нормальная форма (3NF):

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

4. Нормальная форма Бойса — Кодда (BCNF):

Требует, чтобы в таблице был только один потенциальный первичный ключ. Чаще всего у таблиц, находящихся в третьей нормальной форме, так и бывает, но не всегда. Если обнаружился второй столбец (комбинация столбцов), позволяющий однозначно идентифицировать строку, то для приведения к нормальной форме Бойса-Кодда такие данные надо вынести в отдельную таблицу.

5. Четвёртая нормальная форма (4NF):

Для приведения таблицы, находящейся в нормальной форме Бойса-Кодда, к четвертой нормальной форме необходимо устранить имеющиеся в ней многозначные зависимости. То есть обеспечить, чтобы вставка / удаление любой строки таблицы не требовала бы вставки / удаления / модификации других строк этой же таблицы.

6. Пятая нормальная форма (5NF):

Форма, в которой устранены зависимости соединения (таблицу разбивают еще на 3 и более). В большинстве случаев практической пользы от нормализации таблиц до пятой нормальной формы не наблюдается.

На практике, как правило, ограничиваются 3НФ, ее оказывается вполне достаточно для создания надежной схемы БД.

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