Алгоритмы поиска решения и представление знаний

Первый этап развития ИИ был связан с разработкой методов решения задач — алгоритмов поиска решения и построения логического вывода. В настоящее время это уже достаточно проработанный и изученный вопрос. Основные классические результаты изложены в гл. 3.

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

Труднорешаемые задачи. Мифы и реальность^[1][2]

С осознанием понятия «алгоритм» и появлением первых вычислительных машин возникло естественное искушение запрограммировать (алгоритмизировать) как можно большее количество задач, имеющих компактное и однозначно понимаемое описание (в пределе — все подобные задачи). Каждая из таких задач имеет конечное число параметров. Прекрасным примером здесь может служить известная в математике задача коммивояжера. Формулировка задачи коммивояжера чрезвычайно проста: имеется N городов, каждый из которых соединен дорогами со всеми остальными. Коммивояжер должен посетить все города (без повторных заходов) но наикратчайшему маршруту. На языке теории графов это означает поиск гамильтонова цикла наименьшей длины в полном графе с заданными длинами ребер.

Нетрудно заметить, что параметрами в данном случае выступают число городов N и N • (N — 1)/ 2 длин дорог между городами — всего N + N? (N — 1) / 2 ~ N² параметров. Обозначим общее число параметров через М. Важно отметить, что если значения параметров не фиксированы и требуется найти алгоритм решения для всех допустимых значений параметров, то задача называется массовой, в противном случае она называется индивидуальной. Если общее число операций, необходимых для решения задачи с общим числом параметров Л/, мажорируется некоторым полиномом /(А/) степени К (это обозначается так: 0(М^К)), то задача называется полиномиально разрешимой. Выделяется два класса массовых задач: алгоритмически решаемые за полиномиальное относительно числа параметров время (класс этих задач обозначается V) и задачи, для которых полиномиального алгоритма нет или он неизвестен. Такие задачи называются труднорешаемыми (класс обозначаетсяМР). Для задачи коммивояжера (массовой) не известен общий алгоритм решения с полиномиальным временем, эта задача является труднорешаемой.

Ясно, что ответ в задаче коммивояжера можно найти, перебрав все возможные варианты, но в данном случае их ЛП (число различных перестановок N городов). Как известно из математического анализа (формула Стирлинга), функция ЛП (факториал) растет быстрее, чем функция е^Л'(^{экспонента})>^а любая показательная функция растет быстрее, чем любой полипом. Остановимся па этом несложном математическом факте чуть подробнее, поскольку его необходимо ясно осознавать, чтобы «чувствовать» природу труднорешаемых задач.

Утверждение состоит в следующем: не существует степенной функции М" (а значит, не существует и полинома), которая мажорирует показательную функцию Ь^м. Даже если величина а мала, а величину b мы возьмем очень большую, то все равно, начиная с некоторого М, окажется, что Ь^м > М°. Введение любых коэффициентов сохраняет качественную картину. Для примера на рис. 1.8 приведены графики функций 10M¹⁰ (серый пунктир) и 0,1е^Л/ (сплошная линия). Видно, что начиная с М = 42 показательная функция стремительно обгоняет степенную.

Обратите внимание, значения этих функций велики (порядка 10¹⁷) даже для небольших значений М. Напомним, что в задаче коммивояжера Мпропорционально квадрату числа городов N. Если N= 1000, то значение М будет порядка 1 000 000, а число шагов перебора будет столь велико, что даже не поместится в разрядную сетку компьютера.

Рис. 1.8. Сравнение показательной и степенной функций:

——ЮМ¹⁰;—0Ле^м

Некоторые «специалисты», опираясь на соображения, подобные приведенному выше примеру, полагают, что программированием задач, относящихся к классу Л/Р, вообще не стоит заниматься. 11а наш взгляд, это мнение является глубоко ошибочным! В обоснование нашей позиции приведем лишь несколько соображений:

• • только массовую задачу (т.с. совокупность всех индивидуальных) можно относить (или не относить) к классу HP, при этом вполне возможно, что «трудно решается» только небольшой подкласс индивидуальных задач или вовсе единственная. Удалив эти «трудные» случаи из рассмотрения, т. е. сузив «массовость проблемы», можно попытаться отыскать эффективный алгоритм;
• • в некоторых случаях возможно ограничиться приближенным решением, нахождение которого может быть обеспечено за полиномиальное время. Скажем, рассмотрим для задачи коммивояжера такой элементарный алгоритм: начать с любого города и все время ехать в ближайший, который еще не посещен. Этот алгоритм работает быстро, но он совершенно не гарантирует нахождения действительно наикратчайшего пути. Однако можно убедиться с помощью вычислительных экспериментов, что во многих случаях этот алгоритм будет давать решения, довольно близкие к оптимальному;
• • иногда удается ограничиться конкретным значением числа параметров Л/, причем оно не очень велико. Скажем, для приведенного на рис. 1.9 примера экспоненциальный алгоритм в диапазоне от 0 до 42 эффективнее полиномиального.

В различных областях дискретной математики, комбинаторики, логики и т. п. известно множество задач, принадлежащих к числу наиболее фундаментальных, для которых, несмотря на все усилия, нс удалось найти алгоритмов решения, имеющих трудоемкость, ограниченную функцией, полиномиально зависящей от числа параметров М. Более того, если бы удалось отыскать эффективный алгоритм решения хотя бы одной из этих задач, то из этого немедленно следовало бы существование эффективных алгоритмов для всех остальных задач данного класса. На этом основано общепринятое мнение о том, что таких алгоритмов не существует^[3]. Построение эффективного алгоритма для них совершенно невероятно.

Вывод из этих наблюдений состоит в том, что диагноз «труднорешаемая задача» не является основанием для пессимизма, а является поводом для более тщательного анализа контекста задачи.

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

Гораздо более продуктивным методом, позволяющим уменьшить трудоемкость поиска решения, является повышение эффективности представления знаний. Если выбор изощренного представления позволяет уменьшить объем базы знаний, то тот же стандартный алгоритм поиска становится значительно эффективнее в том смысле, что расширяются границы его применимости. Поясним это с помощью модельного числового примера, сравнивающего два гипотетических способа представления знаний. Пусть одна и та же задача в первом представлении имеет размер п, а во втором — п/2. Пусть переборный алгоритм один и тот же и имеет трудоемкость 2^k, где k — размер задачи. Пусть, при этом, более компактное представление дается не даром: каждый шаг перебора выполняется в 10 раз дольше и еще 100 ед. времени безвозвратно теряется на предварительную обработку. Фактически, мы сравниваем две функции: 2″ и 100 + 10 • 2^п/². При малых п первая функция меньше, но после п = 8 вторая функция становится меньше, и ее преимущество только возрастает с ростом п (рис. 1.9). Даже небольшой выигрыш в значении аргумента показательной функции перевешивает все другие проигрыши.

Рис. 1.9. Сравнение трудоемкости поиска в зависимости от компактности базы знаний:

—?- - — 2^W; —а—Ю0+ 10−2″ /²

Выигрыш становится еще более впечатляющим, если удается найти существенно более компактное по сравнению с «лобовым» представление. Рассмотрим реальный пример — задачу восьми ферзей.^[4] Распространим ее на доску произвольного размера п х п. Очевидным представлением данных задачи является шахматная доска с ферзями в п позициях — матрица п х п с единицами в нужных элементах. Однако при внимательном рассмотрении ту же задачу можно описать вектором длины п с числом из диапазона …п в каждом элементе. Номер элемента вектора при этом будет соответствовать горизонтали шахматной доски, а значение элемента — вертикали (или наоборот). Рассуждая по аналогии с предыдущим примером, мы должны сравнить уже другие функции: 2^п и 0 + /?2^" — предварительной обработки не требуется (рис. 1.10). В этом случае вторая функция становится меньше уже после п > 4, и рост первой функции по сравнению со второй существенно больше, нежели в первом случае (даже с учетом заведомого завышения — первым сомножителем при втором слагаемом должно быть не п, а некоторая константа).

Рис. 1.10. Сравнение трудоемкости поиска — вариант 2:

2″;—А—0 + п2^

Компактность базы знаний — определяющий фактор эффективности искусственно-интеллектуальной системы и, следовательно, границ ее применимости. Именно это обстоятельство определяет структуру данной книги. Главы структурированы по методам представления знаний, а не по методам поиска решения. При решении любой задачи в интеллектуальной области сначала следует выбрать представление знаний, потом подобрать подходящий алгоритм поиска решения. Дело в том, что если выбрано неудачное представление знаний, то никакие ухищрения с алгоритмами нс помогут. Если же изобретено особо удачное представление знаний, то, скорее всего, самый обычный алгоритм поиска решения даст вполне удовлетворительные результаты.

• [1] Это число непустых подмножеств множества из п элементов, см.: Новиков Ф. Л. Дискретная математика: учебник для вузов. СПб.: Питер, 2011.
• [2] Многие формулировки и рассуждения в этом отступлении изложены неформально (содержательно). Мы не преследуем цели дать читателю детальное представление о проблеметруднорешаемых задач, а хотим лишь только сформировать общее представление о важностии сложности упомянутой области. За подробностями мы направляем к монографии: Гэри М. уДжонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982.
• [3] Эта точка зрения общепринята, но не доказана. Более того, проблема <<�Р * HP ?"названа первой среди семи математических «проблем тысячелетия». За решение любойиз этих проблем институт Клея предлагает 1 млн долл. США. Пока из семи проблем решенатолько третья — гипотезу Пуанкаре доказал Г. Перельман в самом начале XIX в.
• [4] Задача восьми ферзей: расставить на шахматной доске восемь ферзей так, чтобы онине били друг друга.