Граф мы представляем в выгодной для вас форме в виде сети. Поиск решения сводится к методу поиска пути. Различные варианты переборов. Классические алгоритмы тем хороши, что он легко перенастраивается на любую другую версию переборов, в частности на перебор в глубину.

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

Одна из интеллектуальных особенностей человека связана именно с оцениванием. В пространстве состояний простые оценки тогда, когда у вас цена дуги есть. Если цена дуги однотипная по всему графу, то ее можно складывать. Т.е. на привычном для нас графе появляются еще и числа. Эти числа могут показывать расстояние, приведенное расстояния, время перемещения, стоимость билета.

Значит, если внутреннее представление вершины усложним, оно может быть очень богатым вообще – то, это значит мы навесили какой-то тэг. Одного имения для описания мало, для той же игры в «Восьмерку» нам необходим, как минимум двухмерный массив. На каждую вершину просматривается поле, а в этом поле результат, как мы складываем в дугах (чтобы дойти до граничной вершины при переборах в глубину), так и здесь мы можем оценивать стоимость пройденного пути. А если появляется число, значит надо сравнивать обязательно. Возникает вопрос, когда сравнивать? Или построить все маршруты, а из них выбрать оптимальный, или сравнивать по ходу перебора. Маршрутов может быть бесконечное множество или просто очень много. Нет смысла в этом множестве искать максимальное или минимальное, лучше сравнивать и оценивать по ходу перебора. Давайте возьмем ту, до которой пройден минимальный путь, основания для этого есть.

Если выбираем по минимуму стоимости, то 2 положительных момента: сравнение вариантов проводиться косвенно, первый путь который я найду и будет путем минимальной стоимости. Очевидно, что нам понадобиться дополнительная процедура подсчета пути.

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

Переборы с эвристиками.

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

проваливается, т.е. число точек для которых необходимо найти оптимальный путь).

А ДАЛЬШЕ НЕТ 

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

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

пошли уже ветки на составляющие. Здесь тоже легко берется интеграл, видите здесь я «или» версии не рассматриваю, одну версию беру x2+x-2 интеграл через сумму, я возьму. От x2 я могу посчитать интеграл и от х тоже. Как альтернативы «или» здесь не приведены, но для демонстрации как факт альтернативы есть. Вот такой пример имеется на уровне слайдов.

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

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

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

Классическая компьютерная игра – это когда есть 2 противника. В классической игре все действия заранее оговорены, поэтому у каждой игры есть конечный набор базовых ходов, бесконечные вариации комбинаций. Набор базовых ходов известен и одному, и другому игроку. Если одному игроку неизвестен, это уже не игра получается (он не может предугадать ходы противника). В таких случаях говорят о частных случаях игр, когда слово «игра» употребляется как синоним. Для классической игры также известно конфигурация и состояние игры, когда кто-то выиграл, а когда кто-то проиграл. Если один выигрывает, другой обязательно

проигрывает, хотя есть случаи когда никто не выигрывает. Но не бывает вариантов, когда оба игрока выигрывают.

Если исходить из такого понимания игры и брать игроков за А и В. Беру я А, смотрим А стоит перед выбором между множеством доступных ему ходов (пусть их два, как на картинке), он может выбрать один, либо второй. После такого как А сделает свой ход инициатива уйдет у него из и рук и перейдет к В. У В также два варианта его хода. Значит А может предусмотреть потенциальный ответ В на свой первый ход. Более того, он потенциально может и далее смотреть на определенную глубину. Он может смотреть на какую угодно глубину, но кончится это тем, что он должен выбрать один из 2 ходов. Значит перед игроком, смотрящим на глубину, стоит вопрос оценивания. Ему приходится оценивать возможные ответы противника, для того чтобы выбрать наиболее приемлемый с точки зрения потенциального выигрыша ход. Это значит в этой структуре работают еще и оценки – оценки возможного ответа причем на определенную глубину. Имейте ввиду если нет оценки игра становится не интересной. В игре должен присутствовать интеллект, хитрость, сила игрока, интерес. Надо предусматривать кто сильнее, кто хитрее как игрок.

На самом деле прогнозирование возможных вариантов развитие игры

– представляется и/или–графом. У нас на лицо и/или – граф, на нем вы можете смотреть в глубину до определенной границе, на этом графе есть хорошие вершины, есть плохие. Необходимо вести пересчеты для того чтобы выбрать правильный ход. Когда вы повели оценки, сделали ход, вы упустили инициативу. А В тоже стоит перед таким же деревом. А от В отличается вот чем: 1) способностью просматривать на разную глубину; 2) своими механизмами оценивания. Ходы у них известны, поэтому они не отличаются ходами.

Если вы игрок, который играет в какую либо игру уже 20 лет – значит у вас накоплен огромный опыт. И совсем не очевидно, что у вас одинаковые способности в комбинаторике и одинаковые механизмы оценивания. Таким образом, вам придется столкнуться с переборами на и/или-графе с оценкой, оценка ползет по дереву вдоль снизу вверх.

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

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

Игр тьма тьмущая и программируют их с утра до вечера все кому не лень, появляются новые версии старых игр, а все потому что компьютеры становятся лучше, и появляются новые оценки, механизмы и стратегии.

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

На нашей военной кафедре преподаватель Ямпольский защищал диссертацию «Командно-штабные военные игры».

Игры стоит программировать. Игры это приложение искусственного интеллекта, в основном из-за оценивания и предсказывания.

Типовые стратегии оценки.

Одна из них минимаксная стратегия. На слайде пример когда два игрока А и В, у каждого из них всего лишь по 2 хода. Если А выбирает первый ход – значит он дает возможность для В ответить ходом В1 и В2. Игра в два хода: один ход делает А, отвечает В. Определим цену игры, например рубли. Таким образом, мы можем узнать, что мы выиграем в зависимости от хода В. Перед нами стоит задача выбрать ход А1 или А2, учтем что В хочет выиграть как можно больше. Значит надо сделать ход А1. Стратегия минимаксная, т.е. нам надо выбрать максимальное из минимальных, В всегда будет отвечать минимальным, поэтому берем каждую строку и ищем там минимум и выбираем максимальный из минимумов. Запомните В не промахивается, вот вы можете ошибиться, а он нет. К любому противнику надо относится с уважением. Стратегия является базовой и прозрачной, она является основанием для многих игр. В любой игре приходиться думать о стратегии, о тактике, об оперативных действиях. Если игра серьезная придется смотреть на глубину на 4, использовать мягкие оценки, а тактику смотреть на 6 ходов, использовать оценки пожестче, оперативные действия смотреть на 4 и использовать совсем жесткие оценки, и еще придется синтезировать общую оценку. На уровне стратегии надо помнить, что партнер стремиться минимизировать свой проигрыш, а его противник стремиться максимизировать свой выигрыш.

Вернемся к универсальному решателю проблем (УРП) с которым работали Саймон, А.Ньюэллом и Дж.Шоу. В УРП много чего намешано, там приходится проводить различные переборы. Но есть вполне конкретная оперативная стратегия – стратегия оперативных действий,

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

Основная цель – перейти от А к В, а что стоит за А или за В нас не волнует. Скажем, что А и В принадлежат к пространству состояний. A = S0

– начальное состояние, а B =Sk – конечное..

Первая цель – преобразовать А в В. И преобразовать А в В с вполне конкретной подчиненной целью – это уменьшить различие между А и В, а не увеличить его. Здесь придется столкнуться с тем что за А и В стоит абсолютно любая величина, может стоять что угодно.

В задаче трассировки, например, А – полная картина текущей конфигурации поля со всеми проводниками, контактами, запретами и т.д.

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

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

1.сопоставить с целью определения различия

2.уменьшить различие хотя бы на чуть чуть

3.процедура должна рекурсивно вызвать сама себя

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

Qn и я должен выбрать один из них. В первую очередь мы должны проверить применимость оператора. Применить оператор – это у нас третья цель. Мы начинаем сравнивать условия, для нахождения различия и для того чтобы уменьшить различие между тем реальным рассогласованием на новый вектор. И самое главное уменьшить различие D заменой А на А’. И опять рекурсивный вызов целей. Потом применяем оператор Q, который у меня уже оказалось подходить к А’, для того чтобы сформировать выходной вектор А’’. Далее посмотрим рекурсии: преобразовать – преобразовать, уменьшить различие – уменьшить

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

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

Посмотрим примеры:

1). Надо преобразовать А к В, пусть различие D есть! Здесь цепочка дослежина до конца, то что и для выбора оператора пришлось тоже применить тот же самый алгоритм что бы получить А’ – новые состояния и по этому дереву возвратится обратно. Дерево для того чтобы вы могли рекурсивные возвраты проследить. Существует такая цепочка рекурсивных вызовов на предложения, что различия D есть, есть оператор Q, и для него приходиться искать различие тоже. И все это вернется к состоянию А’’, для которого я должен применить различие.

2). Конкретная задача на УРП. Задача об обезьяне и банане. Есть ограниченная площадь (клетка), там находится обезьяна М и ящик S, банан висит где-то. Обезьяна может сорвать банан, если передвинет ящик под банан, встанет на ящик и сорвет банан. Обезьяна может это сделать, так показывает практика. Но нам то это придется запрограммировать. Это значит вам придется создать структуру данных и на клетку, и на обезьяну, как мы трассу проводили, так и здесь. Разбить, сетку навесить, M и S – поместить, банан подвесить. Ясно только одно, что должна происходить конкретная цепочка преобразований. Придется, программируя, вводить какие-то индикаторы или коды для M и S и банана. Предусмотреть множество мест, в том числе предикаты какие-то на S. Какие-то предикаты переменные. Какой-то определенный набор действий придется программировать. Набор базовых действий придется программировать и у каждого действия есть условия его выполнимости. Например «подняться», место обезьяны должно совпадать с местом ящика. Например, действие такое – место обезьяны M оказалось над S. Вообще то ящик S может подходить в любом месте и, обезьяна на него залезла. Значит процедура должна разрешать обезьяне залазить на ящик, а выгодно это или нет не нам решать. Самое главное – программируя, придется вести базу по многим позициям: базу структур данных, базу мест, базу типовых действий.