Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 347
Текст из файла (страница 347)
Но это утверждение так и не было доказано. Ученые, пытающиеся найти ответ на вопрос о том, эквивалентны ли классы Р и )хР, выделили подкласс класса ХР, называемый ех )хР-полными задачами. В этой формулировке слово "полный" означает "являющийся наиболее ярким представителем" и поэтому указывает на самые трудные задачи из класса ХР. Было доказано, что либо все ХР-полные задачи принадлежат к классу Р, либо ни одна из них к нему не относится. Таким образом, данный класс представляет определенный теоретический интерес, но он важен также с точки зрения практики, поскольку известно, что 1291 Математические основы многие серьезные задачи являются Х Р-полными.
В качестве примера можно указать задачу установления выполнимости: если дано высказывание пропозициональной логики, то есть ли такой вариант присваивания истинностных значений пропозициональным символам в высказывании, при котором оно становится истинным? Если не произойдет чудо и не совпадут друг с другом классы Р и ХР, то нельзя будет найти алгоритм, который позволяет решить все задачи установления выполнимости за полиномиальное время. Но исследователей в области искусственного интеллекта в большей степени интересует то, существуют ли алгоритмы, действующие достаточно эффективно при решении типичных задач, выбранных с помощью заранее заданного распределения; как было показано в главе 7, существуют алгоритмы наподобие Ха 1 1<ЯАТ, которые действуют вполне успешно при решении многих задач. Класс <в.
ко-ХР является комплементарным (дополнительным) по отношению к классу ХР; это означает, что для каждой задачи принятия решения из класса ХР существует соответствующая задача в классе ко-ХР, на которую может быть дан положительный или отрицательный ответ, противоположный ответу на задачу класса ХР. Известно, что Р является подмножеством и ХР, и ко-ХР, кроме того, считается, что к классу ко-ХР относятся некоторые задачи, не входящие в класс Р. Такие задачи называются 'в. ко-ХР-полными и являются самыми трудными задачами в классе ко-ХР.
Класс №Р (произносится как "шарп Р", или "диез Р") представляет собой множество задач подсчета количества вариантов, соответствующих задачам принятия решения из класса ХР. Задачи принятия решения имеют однозначный (положительный или отрицательный) ответ; примером задачи такого типа является следующая: "Существует ли решение для данной формулы 3-ЯАТ?" Залачи подсчета количества вариантов имеют целочисленный ответ, например: "Сколько решений существует для данной формулы 3-$АТ?" В некоторых случаях задача подсчета количества вариантов намного труднее по сравнению с соответствующей задачей принятия решения. Например, принятие решения о том, имеет ли двухдольный граф идеальное паросочетание, может быть выполнено за время 0( ж) (где ь' — количество вершин; я — количество ребер графа), тогда как задача подсчета того, какое количество идеальных паросочетаний имеется в этом двухдольном графе, является №Р- полной.
Это означает, что она не менее трудна, чем любая задача из класса №Р, и поэтому по меньшей мере столь же трудна, как и любая задача ХР. Исследователи определили также класс задач РВРАСЕ; таковыми являются задачи, для которых требуется обьем пространства, определяемый полиномиальной зависимостью, даже при их прогоне на недетерминированной машине. Считается, что РБРАСЕ-трудные задачи решаются хуже по сравнению с ХР-полными задачами, но не исключено, что в ходе дальнейших исследований может быть установлено, что класс ХР эквивалентен классу РБРАСЕ, и также то, что класс Р эквивалентен классу ХР.
А.2. ВЕКТОРЫ, МАТРИЦЫ И ЛИНЕЙНАЯ АЛРЕВРА В математике сформулировано определение Ж вектора как элемента векторного пространства, но мы будем использовать более конкретное определение: вектор— это упорядоченная последовательность значений. Например, в двухмерном пространстве могут быть определены такие векторы, как я=<3, 4> и у=<0, 2>. В этом 1292 Приложение А приложении соблюдаются обычные соглашения об обозначении в нем векторов с помощью полужирных символов, хотя некоторые авторы отмечают имена векторов с помощью стрелок или знаков надчеркивания: х или у.
Элементы вектора обозначаются с помощью подстрочных индексов: а =< з1, г2, ..., з„>. Двумя фундаментальными операциями над векторами являются векторное сложение и скалярное умножение. Векторное сложение х+у — зто поэлементная сумма: х+у=<3+О, 4+2>=<З, 6>, а скалярное умножение — это операция умножения каждого элемента на некоторую константу: 5х= 5хЗ, 5х4 = 15, 20>. Длина вектора обозначается как ~ х ~ и вычисляется путем извлечения квадратного корня из суммы квадратов элементов: !х! =з~ (3~44427=5.
точечное произведение (называемое также скалярным произведением) двух векторов, х у, представляет собой сумму произведений соответствующих элементов; иными словами, х у=2.' х у„ или в данном конкретном случае: х у= 3хО+ 4х2 = 8. Векторы часто интерпретируются как направленные отрезки прямых (напоминающие стрелки) в и-мерном евклидовом пространстве. В таком случае операция сложения векторов эквивалентна совмещению конца одного вектора с началом другого, а точечное произведение х у эквивалентно выражению [х [ ~ у! совО, где  — угол между х и у. 'ъ. Матрица — это прямоугольный массив значений, упорядоченных по строкам и столбцам.
Ниже показана матрица як С раЗмераМи 3х4. с И11 1 П1 2 ПЗ 3 П1,4 222,1 а32,2 2132,3 п2,4 П3,1 1113,2 223,3 П3,4 Первый подстрочный индекс терма За,; определяет строку, а второй — столбец. В языках программированиятермяк, 3 частозаписываетсякакт[1, 3) илию[1) [3 ) . Сумма двух матриц определяется путем сложения соответствующих элементов, поэтому (ян.п) 1 )=я3„;4-п„,. (Если матрицы я3 и и имеют разные размеры, то их сумма не определена.) Можно также определить операцию умножения матрицы на скаляр: ( сза) 1,= Ст1, Операция умножения матриц (получения произведения двух матриц) является более сложной. Произведение яЗп определено, только если х3 имеет размеры ахЬ, а и — размеры Ьхс (т.е.
вторая матрица имеет количество строк, совпадающее с количеством столбцов первой матрицы); результатом является матрица с размерами ахс. Это означает, что операция умножения матриц не коммутативна— в общем случае хЗп44ппк Если матрицы имеют приемлемые размеры, то результат их умножения являются следующим: (я3п) З,к = ~ т',ЗПЗ,к ) Единичная матрица х имеет элементы х... равные 1, если з=3', и равные 0 в противном случае.
Она обладает таким свойством, что яЗХ = За при всех ы. Транспозиция матрицы хь которая записывается как т', образуется путем превращения строк в столбцы и наоборот, или, более формально, путем выполнения операции 2 й =За 1293 Математические основы Матрицы используются для решения систем линейных уравнений с помощью процедуры, называемой алгоритмом 'а. удаления элементов Гаусса-Джордана, который характеризуется показателем 0(п') .
Рассмотрим следующее множество уравнений, для которого можно найти решение в терминах х, у и ьч +2х+у-я=8 -Зх — у + 2з = -11 -2х + у + 2з = -3 Эту систему уравнений можно представить в виде следующей матрицы: х у г с с 2 1 -1 8 -3 -1 2 -11 ) -2 1 2 -3 Здесь строка х у з с не входит в состав матрицы; она служит лишь в качестве напоминания, к чему относится каждый столбец. Известно, что если обе стороны уравнения будут умножены на константу или если это уравнение будет сложено с другим уравнением, то полученное уравнение останется действительным. Метод удаления элементов Гаусса — Джордана действует по принципу повторного выполнения подобных операций таким образом, чтобы вначале была удалена первая переменная (х) из всех уравнений, кроме первого, а затем эти действия продолжались в форме удаления (-й переменной из всех уравнений, кроме (-го, для всех 31 Удалим х из второго уравнения, умножив первое уравнение на 3/2 и сложив его со вторым.
В результате будет получена следующая матрица: Продолжая аналогичные действия, удалим х, у и з и получим следующее: (!!! Я Таким образом, решением является х=2, 3 — 3, х=-1 (проверьте это решение!). А.З. РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ Вероятность — это мера, заданная на множестве событий, которая удовлетворяет трем приведенным ниже аксиомам. 1. Мера каждого события находится в пределах от 8 до 1. Это утверждение записывается как 0<Р(д'=еь) <1, где д — случайная переменная, представляющая событие; е, — возможные значения В. Вообще говоря, случайные переменные обозначаются прописными буквами, а их значения — строчными. 2.
Мера всего множества равна 1; это означает, что Р(Д=е )=1 1=1 1294 Приложение А 3. Вероятность объединения несовместимых событий равна сумме вероятностей отдельных событий; это означает, что Р(е=еме=е,) =Р(е=е,) +Р(е=е,), где е, и е, являются несовместимыми. Вероятностная модель состоит из пространства выборок взаимоисключающих возможных результатов, наряду с вероятностной мерой для каждого результата. Например, в модели погоды на завтра результатами могут быть еиппу (солнце), с1оис(у(облачность), хаусу(дождь) и эпоху (снег).
подмножество этих результатов представляет собой событие. Например, событие выпадения осадков — это подмножество (хаупу, эпоху) . Для обозначения вектора значений <Р(е=е,), ..., Р(е=е„) > используется терм Р (В) . Кроме того, Р( е,) применяется как сокращенное обозначение для Р(В=е,), а Р(е) служит для обозначения Х П Р(Е=е,) . 1=1 Условная вероятность Р(В ~(/)) определяется как Р(В г~ л) /Р(л) . Переменные /) и Вявляются условно независимыми, если Р(В~А) =Р(В) (или, равным образом, если Р(л ~ в) =Р(л) ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
