моделей интеллектуальной активности никуда не денешься, по крайней мере в выборах, сравнениях.
Лекция 4
РЕШЕНИЕ ЗАДАЧ.
Решение задач с проблематики искусственного интеллекта стоит на первом месте. Начнем с простых вариантов. Этих простых версий отложилось три:
Первая – это то, что относится к пространству состояний, лабиринтам каким-то. Решение задач методом пространства состояний.
Вторая - это методы решения задач на ИЛИ – графах. Когда задачу сводят к простым подзадачам.
Третье – это решение задач методом решения теорем.
2.1 Метод пространства состояний.
Для решения должен быть задано то, что мы называем лабиринт. И у вас перед глазами должна стоять сеть из вершин и дуг, а что это за вершины и дуги, вопрос второй. На самом абстрактом уровне там и цен нет, а есть просто вершины и связи. Если вы хотите этим методом решить задачу, вы должны перейти к этому методу в формулировке задачи. Должен быть какой-то постой формализм. Есть вершины, и если лабиринт конечный, их конечное множество, если нет, то бесконечное множество. Если бесконечное, то вам должен быть задан закон этого множества, а закон простой, что бы уметь проверять, принадлежит ли данная вершина множеству, данному пространству. Т.е. для любой вершины вы должны проверить, принадлежит она сети или нет, а какое у вас множество – это вопрос второй. Если она принадлежит, значит к ней маршруты есть. Кроме множества состояний, должны быть заданы начальные, может быть не одна. Вы можете идти к одной цели с разных позиций. В принципе у вас разные постановки задач могут быть. Должны быть и дуги. Для любых двух вершин должны быть определены переходы, даже если граф
бесконечный, это не означает, что нельзя определить кто с ним рядом, и как перейти к тем кто рядом. Т.е. если граф связный, переходы должны быть заданы. В простой постановке задачи, если заданы вот эти 1,2,3, то необходимо найти любой путь от любой изначальной до конечной. Начальная и конечная вершины могут быть заданы и признаками, т.е. теми условиями, которыми они должны удовлетворять. Очень часто мы конечную вершину знаем только по признакам, по условиям каким-то. Если вы определили исходные, если вы определили конечные, то вас интересует в пространстве состояний любой путь от любой начальной, до любой конечной, это в общем случае. Если путей много, то говорят: задача имеет несколько вариантов решения. Когда вас не интересует цена перехода, цена решения, то вас устраивает любое из них. Какое нашли первым, значит оно вас и устраивает.
Для примера здесь показана игра в пятнадцать, но она упрощена до игры в восемь. Я взял и конкретную конфигурацию фишек там указал, как эта конфигурация получилась, вопрос десятый. Самое главное, что это и есть та вершина S. Вообще там вершины, это конфигурации чисел какието. Я думаю какие же действия я могу применять, т.е. какие переходы вообще возможны. Реальность такова, что я передвигаю квадратик с фишкой, который могу передвинуть. Я не все могу передвинуть, а только те которые около пустого места. В данной ситуации, это 6 и 8. Т.е. два у меня состояния, два перехода, которые могут быть. Я нахожусь в точке S и у меня два пути к S1 и к S2, а за ними стоят поля с вполне конкретной конфигурацией. у меня образовалось новое состояние, если я здесь мог две применить, два перехода, то здесь уже по три каждой. Далее пойдет ветвление из вершин, которые исходят из вполне конкретной конфигурации, из исходного состояния, оно одно. Возникает вопрос, цель какая? Цель я могу обозначить двумя способами. Первый – это я могу указать просто конфигурацию, несколько конфигураций, но я могу задать и свойством искомое состояние. Но я ищу здесь не конкретную конфигурацию, я ищу упорядоченное, либо по строкам, либо по столбцам размещение фишек. Определив порядок, я к нему буду идти. Моими операторами, моими действиями, используя которые я перехожу из состояния в состояния, является следующее. У меня было состояние Sn , если я применяю к нему оператор "влево", то я получаю Sm, вправо, вверх и вниз, всего четыре оператора. Дуг может быть сколько угодно, а вот действий, которые определяют переход четыре. В каждом положении, к тому же, применим определенный набор операторов, а не все. Он позволяет перейти в другие состояния. У меня множество состояний – это множество комбинаций чисел, сходное вот такое, конечное – упорядоченное с началом в правом верхнем углу. Действия – вправо, влево, вверх, вниз. Решай задачу. В конце концов каждый соберет эту упорядоченную комбинацию, а решение – это путь. Это значит будет цепочка действий из базовых операторов, которые действуют на вполне конкретные состояния. Если вы будите вести регистрацию своих шагов, то
по сути дела это будет ваш вариант решения. Этих решений много, и каждый решает эту задачу по своему. Можно соревноваться на скорость, кто быстрее, тот победил, значит метод решения его более выгодный.
Это идейная сторона, а если мы хотим робота учить, что бы он так решал задачи, если их можно представить в пространстве состояний, то ему нужно давать систематические процедуры обобщенные и какие-то обобщенные описания представления. В этом случае надо с позиции программирования строить различные версии переходов. Запрограммировать это, для вас не сложно. Это простая задача, значит ее решали сотни программистов. Значит, есть хорошие решения, а есть плохие. Попадете ли вы в то решение, которое называют классическим, или распространенным, или которое роботу передадут, это вопрос. Эти задачи решают, используя комбинаторику, и чтобы не промахнуться, в любом случае. Чтобы не промахнуться используют т.н. полный перебор. Есть разные стратегии. Классика и опыт комбинаторики у разных людей разный. Человек ничего не может делать, кроме комбинаторики, и вы всю свою жизнь комбинировали. Чтобы не зависеть от субъективного опыта и строят алгоритмы полного перебора. На слайде показано, что там где находятся эти вершины, легче всего понимать, как область, которую придется сканировать, а что за механизм сканирования, вопрос второй. Классических сканирований не так и много.
Первое – это перебор в ширину, я иду строка за строкой по области сканирования, чтобы ни чего не упустить, сверху вниз, слева на право, пока везде все не "увижу". Я не мечусь от точки к точке, а я начинаю сверху до низу идти. Сначала надо область сканирования каким-то образом выделить и по ней надо идти шаг за шагом.
Второе – это перебор в глубину. Для перебора в ширину я рисую дерево в низ, и слой за слоем перехожу по этим вершинам, пока не дойду. Шаг у меня – это переход очередной по вершинам, перешел, у меня вот фронт есть. Я снова переход у меня другой фронт. Я иду фронт за фронтом. На дереве все прозрачно, сверху вниз. Перебор в глубину – я по одной ветви углубился, дошел до низа, потом возвращаюсь назад и снова вниз иду. Любому человеку с детства приходиться использовать и то и другое, или в каких-то комбинациях. Это вообще стратегии в
комбинаторном поведении, когда вы сталкиваетесь с задачей. Промахнуться я не хочу, предо мной стоит выбор в глубину или в ширину.
Ядолжен выбрать. Это уже оказывает влияние на психику и на внешнее проявление человека. Например, человек, который решает задачи методом в ширину это педант. Он не хочет рисковать, он перебирает все варианты, но их, таких людей мало, больше решают методом в глубину, а вообще то больше тех, кто и так и так. Человеку хочется быстрее. Перебор в ширину, перебор в глубину – это систематические процедуры, в которых почти не возможно промахнуться. Если есть классические переборы, то их многократно программировали, значит там есть классика ну, и мы с этой классикой начнем знакомиться. Сначала подойдем к классике поближе. НЕ бросайтесь на любую задаче сразу же. Сначала нужно все продумать, и в первую очередь с позиции тех структур данных, с которыми вам придется работать. Только когда у вас все встанет на свои места, тогда начинайте думать и действовать. Вот у нас задача на комбинаторику. Есть граф, мы систематически идем по нему, но если я возьму любой момент времени, это значит, что я не дошел пока. И значит все множество вершин, с которыми я имею дело разделились на три множества, которые мы уже прошли, и там ничего нет; вторые – это те вершины на фронте которых я сейчас нахожусь, до которых я дошел, из которых я могу смотреть дальше.
Ядошел до этого множества в рассуждениях, а не в конкретном маршруте. Это потенциальные альтернативы от куда я могу идти. Через каждую из этих вершин проходит какой-то путь. Значит, я эти вершины прошел, там у меня решения нет. Я с этих вершин смотрю, где путь. А вот с этими вершинами я еще не сталкивался. Вот классические переборы в ширину так и действуют. Они говорят, пусть у меня три структуры данных, которые отражают текущее состояние работы. Вообще то у меня есть структуры данных, которые весь лабиринт задают. Это исходное множество вершин и конечное множество вершин. Но внутренних структур данных три. В классических алгоритмах в соответствии с этими тремя группами вершин и заводят внутренние структуры.
На следующем слайде показан перебор в ширину, рассмотрим его детальнее. Есть какой-то реальный граф. Он толи дерево, толи граф, вопрос пока открытый. Мне его нужно представить этот граф. Я могу представит этот граф по-разному, ноя его представляю во такой структурой данных табличной. Первый столбец – это родительская, а дальше в строке идут дочерние. Можно было задать по другому. В зависимости какие задачи решаются на графах используются различные представления всего графа целиком. Есть исходная вершина S0, с которой я должен идти. Те внутренние структуры данных, я их сейчас вам выведу, но там будут и конечные вершины. Две из этих структур данных – это два списка, вершин, которые я уже узнал, что они не являются целевыми, которые я уже прошел. Я ту вершину, которая является исходной, заношу в список открытых вершин, с которыми я начинаю работу, из которых я хочу смотреть дальше. Для того, что бы смотреть
дальше, я обращаюсь к таблице. Я нахожу нужную строку, для этой родительской вершины, я ее вызываю для того, чтобы сравнить с конечной, с целевой. Я сравниваю, есть ли там конечная или нет. И если конечных нет я их заношу в список открытых, а ту вершину, которую я рассмотрел, я заношу ее в список закрытых. Я начинаю разбрасывать все свои вершины по внутренним своим структурам данных, таких структур данных у меня три, Список открытых, список закрытых и список вершин, которые я анализирую на соответствие цели. В списке открытых находятся те вершины, из которых я еще не смотрел, вершины фронта. Но здесь есть вершины которые только в таблице находятся, те которые я не смотрел. Процедура следующая. Я беру вершину, которая находится в начале списка, ищу строку соответствующую, вызываю строку, сравниваю на цель. Если цели нет, значит я должен продолжать поиск. Я их заношу в список открытых, а ту вершину, которую я просмотрел, я заношу в список закрытых. Это первый шаг. Эту вершину я забрал, ее там нет. И теперь я должен брать очередную вершину, у меня S1, а потом S2. Т.е. если я беру последнюю, которая у меня осталась в списке открытых, я иду по сути дела по переборам в ширину, до тех пор пока я не попаду на цель. В конце концов у меня сформировался список закрытых, я все перебрал и цель нашел. Я должен остановиться, если цель нашел. Но это не означает, что уже записан путь, который от начала до конца. Теперь начинается вторая часть задачи – сборка пути. Этот путь весь есть в закрытом списке, он в списке закрыт. У меня есть список закрытых, где у меня лежат все вершины, но там есть и лишние вершины. Теперь я должен построить путь, хорошо бы, если бы я не лазил в эту исходную базу, таблицу, и хорошо, если бы кроме списка закрытых мне ничего использовать не надо было. Это сделать достаточно просто, если я начну на каждую вершину фиксировать, изменю внутренне представление, и фиксировать ее родительскую. Вот, например, i-ая вершина у меня храниться в вот такой форме: i-ая вершина, а рядом с ней ее родительская. Я выбираю представление, которое мне окажется проще для решения задачи. Для решения задачи внутренне представление проще сделать составным, что бы там хранилось не только имя вершины, но и имя родительской вершины. Конечное представление, конечная – в первом поле, родительская в втором. Я ищу родительскую, по ее родительской ищу дальше, и так далее, пока я не дойду до исходной вершины. Можно было не делать внутренне представление, но тогда бы пришлось использовать всю ту таблицу. Но в классическом плане, так не делают, там усложняют внутренне представление, что бы упростить программирование и сократить объем данных.
Поэтому задачу делят на две части: сначала отвечают на вопрос "Есть путь или нет?", а потом, когда путь найдут, начинают строить путь. Но все у нас просто если дерево, если сеть сложнее, начинаются возвраты. Я должен предусмотреть фильтр, если у меня есть возврат, отбрасывать, его не рассматривать. В любом случае, дерево или сеть, одно решение, на
две подзадачи разбил. Что бы предотвратить зацикливаний, поступают следующим образом, если какая – то вершина уже попадала в списки открытых, ее туда не включать, а все остальное как на дереве.
Программируется этот алгоритм просто, тяжелее представить вершины. Они же у нас именами заданы. А ваша задача, если про фишки, то у нее внутренне представление богаче. Это всего лишь говорит нам о том, что внутреннее представление богаче, не эти два поля, а шире, но эти два поля есть обязательно, с именем и родительской.
Полный перебор в ширину мы в общем разобрались. Он совершенно просто настраивается в перебор в глубину, если мы сделаем кое-какие изменения. У полного перебора в глубину, у него есть проблемы. Эти проблемы наружу выходят, связанные с тем, что граф бесконечный. Если перебор бесконечен, перебор в ширину будет шаг за шагом идти к вашему решению, а этот сразу по одной ветке в бесконечность ушел. Такого допускать нельзя. Человек знает, решение находиться где-то недалеко. Недалеко понятие относительное. Есть проблема, по ветке я могу уйти. Раз я могу уйти в бесконечность, надо рвать силовым способом. Это значит дальше, например, чем на сто шагов не идти. Количество шагов определяется субъективно, но любой специалист обладает оценками. Он догадывается, что без доказательства, решение находиться не дальше, чем на 100 шагов, например. Но это же не бесконечное число шагов, а не бесконечное. Для того, чтобы воспользоваться полным перебором в глубину на бесконечных графах их приходиться резать. И на определенной глубине проводить линию. Такого рода способы уменьшить объемы комбинаторики называют эвристиками. Значит эвристику предложил человек. Эвристика – это то, что сокращает перебор. Мы перебор сократили, ограничили, но вообще-то рискуем, что решение не найдем. Например, что вероятность того, что не найдем 0.5%, а того что найдем 99.5%, так я обрежу. Ну не нашел, значит границу провел не там, тогда давай еще увеличим на 10, например. Глубина измеряется в переходах, ее подсчитать легко. А все остальное сохраняется, что относиться к спискам открытых, закрытых. Только одно меняется, куда и как записывать. Мы инвертируем список, записываем в конец, а начало считаем то, что в конце. Т.е. я беру не в начале списка, а в конце. Представьте что этот стек. В стек у меня падают вершины, но перед тем как они упадут, они перевернуться по своей индексации дочерних вершин. Если я буду делать два таких действия, то это у меня стал не перебор в ширину, а перебор в глубину. С кодом вершины, если я хочу проводить оценку, пересек я границу или нет, я должен завести поле и считать в глубину. А по этому значению сравнивать с граничным. Т.е. я усложнил внутренне представление, включил проверку на границу, изменил порядок записей в списке открытых, и порядок выборки из этого списка. Я не менял все связанное с построением пути. У полного перебора в глубину есть те же проблемы с возвратами.