Библиотека    Новые поступления    Словарь    Карта сайтов    Ссылки





назад содержание далее

Часть 9.

<4.3. ><Использование ><эвристик ><в ><играх>

<><В ><то ><время ><две ><противоположные ><концепции ><вызвали ><многочисленные ><споры. ><Лучшие ><игроки ><различали ><два ><принципиальных ><типа ><Игры ><- ><формальный ><и ><психологический.>

<- ><Герман ><Гессе ><(Hermann ><Магистр ><Луди ><(Игра ><в ><бисер)>

<4.3.1. ><Процедура ><минимакса ><на ><графах, ><допускающих ><полный ><перебор>

<Игры ><всегда ><были ><важной ><прикладной ><областью ><для ><эвристических ><алгоритмов. ><Игры ><для ><двух ><человек ><более ><сложны, ><чем ><простые ><головоломки ><из-за ><существования ><"враждебного" ><и, ><по ><существу, ><непредсказуемого ><противника. ><Такие ><игры ><не ><только>

<><Глава ><4. ><Эвристический ><поиск>

<169>

><<обеспечивают ><некоторые ><интересные ><возможности ><для ><развития ><эвристик, ><но ><и ><создают ><большие ><трудности ><в ><разработке ><алгоритмов ><поиска.>

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

<Игра ><"ним" ><(nim) ><- ><это ><одна ><из ><игр, ><пространство ><состояний ><которой ><допускает ><>исчерпывающий< ><поиск. ><В ><этой ><игре ><на ><стол ><между ><двумя ><противниками ><выкладывается ><не­><которое ><число ><фишек. ><При ><каждом ><ходе ><игрок ><должен ><разделить ><"кучку" ><фишек ><на ><два ><непустых ><набора ><разных ><размеров. ><Например, ><6 ><фишек ><можно ><разделить ><на ><группы ><5 ><и ><1 ><или ><4 ><и ><2, ><но ><не ><3 ><и ><3. ><Первый ><игрок, ><который ><не ><сможет ><больше ><сделать ><ход, ><>проигрывает<. ><Для ><разумного ><числа ><фишек ><в ><пространстве ><состояний ><этой ><игры ><можно ><>реализовать< ><полный ><перебор. ><На ><рис. ><4.13 ><показано ><пространство ><состояний ><для ><7 ><фишек.>

<В ><играх, ><не ><допускающих ><исчерпывающего ><описания ><пространства ><состояний, ><>основная< ><трудность ><заключается ><в ><предсказании ><действий ><противника. ><Простой ><способ ><учесть ><такие ><действия ><- ><предположить, ><что ><ваш ><противник ><использует ><те ><же ><самые ><знания ><о ><пространстве ><состояний, ><что ><и ><вы, ><и ><применяет ><эти ><знания ><для ><своей ><победы. ><Хотя ><это ><предположение ><имеет ><свои ><ограничения ><(которые ><будут ><обсуждаться ><в ><подразделе ><4.3.2), ><оно ><дает ><разумную ><основу ><для ><предсказания ><поведения ><противника. ><Метод ><минимакса ><реализует ><поиск ><в ><игровом ><пространстве ><с ><учетом ><этого ><предположения.>

<>

<Рис. ><4.13. ><Пространство ><состояний ><для ><одного ><из ><вари><антов ><игры ><"ним". ><В ><каждом ><состоянии ><семь ><фишек ><>делятся< ><на ><несколько ><кучек>

<><170>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<Назовем ><противников ><в ><игре ><и ><МАХ. ><Эти ><имена ><выбраны ><по ><следующим ><>причинам<: ><МАХ ><представляет ><игрока, ><пытающегося ><выиграть, ><или ><максимизировать ><свое ><преимущество, ><- ><противника, ><который ><пытается ><минимизировать ><счет ><своего ><оппонента. ><Предполагается, ><что ><использует ><ту ><же ><самую ><информацию ><и ><всегда ><пы­><тается ><достичь ><наихудшего ><для ><МАХ ><состояния.>

<При ><реализации ><стратегии ><минимакса ><пометим ><каждый ><уровень ><в ><области ><поиска ><именем ><игрока, ><выполняющего ><очередной ><ход: ><или ><МАХ. ><В ><примере ><на ><рис. ><4.14 ><первый ><ход ><делает ><Каждому ><листовому ><узлу ><присвоим ><значение ><1 ><или ><0, ><в ><>зависимости< ><от ><победителя: ><МАХ ><или ><В ><процессе ><реализации ><процедуры ><минимакса ><эти ><значения ><передаются ><вверх ><по ><графу ><согласно ><следующему ><правилу.>

<Если ><родительское ><состояние ><является ><узлом ><МАХ, ><то ><ему ><присваивают ><>максимальное< ><значение.>

<Если ><родительское ><состояние ><- ><узел ><то ><ему ><присваивают ><минимальное

><значение.>

<Значение, ><связываемое ><таким ><образом ><с ><каждым ><состоянием, ><отражает ><наилучшее ><со><стояние, ><которого ><этот ><игрок ><может ><достичь ><(принимая ><во ><внимание ><действия ><>противника< ><в ><соответствии ><с ><алгоритмом ><минимакса). ><Таким ><образом, ><полученные ><значения ><ис­><пользуются ><для ><того, ><чтобы ><выбрать ><наилучший ><среди ><возможных ><шагов. ><Результат ><применения ><алгоритма ><минимакса ><к ><графу ><пространства ><состояний ><для ><игры ><"ним" ><>показан< ><на ><рис. ><4.14.>

<Значения ><вершинам ><присваиваются ><снизу ><вверх ><на ><основе ><принципа ><минимакса. ><>Поскольку< ><любой ><из ><возможных ><первых ><шагов ><ведет ><к ><вершинам ><со ><значением ><1, ><второй ><игрок, ><МАХ, ><всегда ><может ><победить, ><независимо ><от ><первого ><хода ><может ><побе­><дить ><только ><в ><том ><случае, ><если ><МАХ ><допустит ><ошибку. ><На ><рис. ><4.14 ><видно, ><что ><может ><выбрать ><любой ><из ><возможных ><вариантов ><первого ><хода ><- ><все ><они ><открывают ><возможные ><пути ><победы ><МАХ, ><отмеченные ><на ><рисунке ><полужирными ><линиями ><со ><стрелками.>

<Хотя ><существуют ><игры, ><где ><возможен ><полный ><перебор, ><все ><же ><наиболее ><интересными ><являются ><случаи, ><в ><которых ><он ><неприменим. ><В ><следующем ><разделе ><будет ><рассмотрено ><эвристическое ><приложение ><минимакса.>

<4.3.2. ><Минимакс ><при ><фиксированной ><глубине ><поиска>

<При ><использовании ><минимакса ><в ><более ><сложных ><играх ><редко ><удается ><построить ><>полный< ><граф ><пространства ><состояний. ><Обычно ><поиск ><выполняют ><вглубь ><на ><определенное ><число ><уровней, ><которое ><определяется ><располагаемыми ><ресурсами ><времени ><и ><памяти ><>компьютера<. ><Эта ><стратегия ><называется ><прогнозированием ><п-го ><слоя ><(n-ply ><где ><л ><- ><число ><исследуемых ><уровней. ><Такой ><подграф ><не ><отражает ><всех ><состояний ><игры, ><и ><по­><этому ><его ><узлам ><невозможно ><присвоить ><значения, ><отражающие ><победу ><или ><поражение. ><Поэтому ><с ><каждой ><вершиной ><связывают ><значение, ><определяемое ><некоторой ><>эвристической< ><функцией ><оценки. ><Значение, ><которое ><присваивается ><каждой ><из ><л ><вершин ><на ><пути ><от ><корневой ><вершины, ><- ><не ><показатель ><возможности ><достичь ><победы ><(как ><в ><предыдущем ><примере). ><Это ><просто ><эвристическое ><значение ><оптимального ><состояния, ><которое ><может ><быть ><достигнуто ><за ><л ><шагов ><от ><этой ><корневой ><вершины. ><Прогнозирование ><увеличивает ><силу ><эвристики, ><позволяя ><применить ><ее ><на ><большей ><области ><пространства ><состояний. ><Стратегия ><минимакса ><интегрирует ><эти ><отдельные ><оценки ><в ><значение, ><которое ><>присваивается< ><родительскому ><состоянию.>

<><Глава ><4. ><Эвристический ><поиск>< ><171>

><<>

<Рис. ><4.14. ><Принцип ><минимакса ><для ><игры ><"ним". ><Жирные ><линии ><показывают ><пути ><к ><победе ><МАХ. ><Каждому ><узлу ><присвоено ><значение ><0 ><или ><1 ><в ><соответ­><ствии ><с ><процедурой ><минимакса>

<В ><конфликтной ><игре ><каждый ><игрок ><пытается ><переиграть ><другого, ><и ><многие ><игровые ><эвристики ><прямо ><измеряют ><преимущество ><одного ><игрока ><над ><другим. ><В ><шахматах ><очень ><важно ><иметь ><преимущество ><в ><какой-либо ><части ><игровой ><доски, ><так ><что ><простая ><эвристика ><может ><учитывать ><разность ><количества ><частей, ><где ><имеют ><преимущество ><либо ><МАХ, ><либо ><и ><максимизировать ><ее. ><Можно ><применить ><и ><более ><сложную ><стратегию ><- ><>присваивать< ><различные ><значения ><частям ><доски, ><в ><зависимости ><от ><позиции ><фигур ><на ><доске ><(например, ><ферзь ><против ><пешки ><или ><король ><против ><пешки). ><Большинство ><игр ><дают ><без­><граничные ><возможности ><для ><создания ><всевозможных ><эвристик.>

<Графы ><игр ><рассматриваются ><по ><уровням. ><Как ><показано ><на ><рис. ><4.14, ><МАХ ><и ><де><лают ><шаги ><поочередно. ><Каждой ><ход ><игрока ><определяет ><новый ><уровень ><графа. ><Типичная ><игровая ><программа ><предсказывает ><ходы ><до ><определенной ><фиксированной ><глубины, ><>которая< ><определяется ><пространственными ><или ><временными ><ограничениями ><компьютера. ><Со­><стояния ><до ><этой ><глубины ><оцениваются ><эвристикой ><и ><на ><основе ><минимакса ><>распространяются< ><обратно ><к ><начальному ><состоянию. ><Алгоритм ><поиска ><затем ><использует ><эти ><>производные< ><значения, ><чтобы ><выбрать ><наилучший ><среди ><возможных ><ходов.>

<Присвоив ><оценку ><каждому ><состоянию ><выбранного ><слоя, ><программа ><передает ><это ><>значение< ><каждому ><родительскому ><состоянию. ><Если ><родительское ><состояние ><относится ><к ><уровню ><ему ><передается ><минимальное ><из ><состояний ><всех ><его ><потомков. ><Если ><>родительское< ><состояние ><- ><узел ><уровня ><МАХ, ><минимакс ><назначает ><ему ><максимальное ><>значение< ><из ><всех ><его ><потомков.>

<Максимизируя ><значения ><для ><родительских ><узлов ><МАХ ><и ><одновременно ><минимизируя ><их ><для ><алгоритм ><осуществляет ><проход ><по ><графу, ><присваивая ><значения ><потомкам ><те->

<><172>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<кущего ><состояния. ><Затем ><эти ><значения ><используются ><алгоритмом ><для ><выбора ><наилучшего ><потомка ><текущего ><состояния. ><На ><рис. ><4.15 ><алгоритм ><минимакса ><проиллюстрирован ><на ><гипотетическом ><пространстве ><состояний ><с ><четырьмя ><уровнями.>

<Самые ><ранние ><работы ><по ><ИИ ><в ><этой ><области ><- ><это ><программа ><игры ><в ><шашки, ><>созданная< ><Самюэлем ><(Samuel) ><в ><1959 ><году. ><Эта ><программа ><была ><исключением ><для ><того ><време­><ни, ><особенно ><учитывая ><существующие ><ограничения ><для ><компьютеров ><50-х ><годов. ><Мало ><того, ><что ><эта ><программа ><игры ><в ><шашки ><применяла ><эвристический ><поиск, ><в ><ней ><также ><присутствовал ><простой ><алгоритм ><обучения. ><Эта ><программа ><была ><во ><многом ><пионерской, ><и ><ее ><все ><еще ><используют ><при ><создании ><игровых ><и ><обучающихся ><программ.>

<Программа ><Сэмюэля ><оценивала ><состояние ><доски, ><используя ><взвешенную ><сумму ><не><скольких ><различных ><эвристических ><значений>

<>

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

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

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

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

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

<><Глава ><4. ><Эвристический ><поиск>< ><173>

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

<>

<2 >< >< >< >< >< >< ><359>< >< >< >< >< >< >< >< ><0 >< >< >< >< >< >< >< ><742>< >< >< >< >< >< >< ><156 ><Рис. ><4.15. ><Минимакс ><в ><гипотетическом ><пространстве ><состояний>

<В ><алгоритме ><минимакса ><существует ><и ><другой ><эффект, ><связанный ><с ><эвристическими ><оценками. ><Оценки, ><которые ><находятся ><очень ><глубоко ><в ><пространстве, ><могут ><не ><>приниматься< ><во ><внимание ><из-за ><их ><большой ><глубины ><[Pearl, ><1984]. ><Подобно ><тому, ><как ><среднее ><произведений ><отличается ><от ><произведения ><средних, ><оценка ><минимакса ><(которую ><мы ><хо­><тим ><получить) ><отличается ><от ><минимаксной ><оценки ><(которую ><мы ><получаем). ><В ><этом ><смысле ><обычно ><(хотя ><и ><не ><всегда) ><лучше ><использовать ><более ><глубокий ><поиск ><с ><оценкой ><состояний ><и ><алгоритмом ><минимакса. ><Детальное ><обсуждение ><этой ><проблемы ><и ><средств ><ее ><решения ><можно ><найти ><в ><[Pearl, ><1984].>

<В ><завершение ><обсуждения ><алгоритма ><минимакса ><представим ><его ><приложение ><к ><игре ><в ><"крестики-нолики" ><(раздел ><4.1), ><описанное ><в ><[Nilsson, ><1980]. ><Здесь ><>используется< ><чуть ><более ><сложная ><эвристика, ><позволяющая ><измерить ><конфликт ><в ><игре. ><Эта ><>эвристика< ><состоит ><в ><следующем. ><Выбирается ><состояние, ><которое ><необходимо ><оценить, ><находятся ><все ><победные ><строки ><для ><МАХ, ><а ><затем ><из ><их ><числа ><вычитается ><общее ><>количество< ><победных ><строк ><для ><Алгоритм ><поиска ><пытается ><максимизировать ><эту ><разность. ><Если ><данное ><состояние ><приводит ><к ><победе ><МАХ, ><то ><оно ><оценивается, ><как ><+?; ><а ><если ><оно ><приводит ><к ><победе ><- ><как ><-?. ><На ><рис. ><4.16 ><показано ><применение ><этой ><эвристики ><к ><нескольким ><состояниям.>

<На ><рис. ><4.17, ><4.18 ><и ><4.19 ><показано ><применение ><эвристики, ><представленной ><на ><рис. ><4.16, ><в ><алгоритме ><двухуровневого ><минимакса. ><На ><этих ><рисунках ><>продемонстрирована< ><эвристическая ><оценка, ><возврат ><на ><основе ><минимакса, ><ход ><МАХ, ><а ><также ><>некоторые< ><ограничения ><на ><ходы ><с ><равными ><эвристическими ><значениями ><[Nilsson, ><1971].>

<><174>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<>

<Рис. ><4.16. ><Эвристика, ><учитывающая ><конфликт ><в ><игре ><"крестики-нолики ><">

<4.3.3. ><Процедура ><альфа-бета-усечения>

<Прямой ><алгоритм ><минимакса ><требует ><двух ><проходов ><по ><области ><поиска. ><Первый ><позволяет ><пройти ><вглубь ><области ><поиска ><и ><там ><применить ><эвристику, ><а ><второй ><- ><присвоить ><эвристические ><значения ><состояниям, ><следуя ><вверх ><по ><дереву. ><Минимакс ><рассматривает ><все ><ветви ><в ><пространстве ><поиска, ><включая ><те ><из ><них, ><которые ><могли ><быть ><исключены ><более ><интеллектуальным ><алгоритмом. ><Разработчики ><игровых ><>стратегий< ><в ><конце ><1950-х ><годов ><создали ><алгоритм ><[Newell ><и ><1976], ><который ><>получил< ><название ><альфа-бета-усечения ><и ><позволил ><повысить ><эффективность ><поиска ><в ><играх ><с ><двумя ><участниками ><[Pearl, ><1984].>

<Идея ><альфа-бета-поиска ><проста: ><вместо ><того, ><чтобы ><рассматривать ><все ><состояния ><некоторого ><уровня ><графа, ><алгоритм ><выполняет ><поиск ><в ><глубину. ><В ><процессе ><поиска ><участвуют ><два ><значения, ><называемые ><альфа ><(alpha) ><и ><бета ><(beta). ><Значение ><альфа, ><связанное ><с ><узлами ><МАХ, ><никогда ><не ><уменьшается, ><а ><значение ><бета, ><связанное ><с ><>узлами< ><никогда ><не ><увеличивается. ><Предположим, ><что ><для ><некоторого ><узла ><МАХ ><значение ><альфа ><равно ><6. ><Тогда ><МАХ ><может ><не ><рассматривать ><состояния, ><которые ><связаны ><с ><нижележащими ><узлами ><и ><имеют ><значения ><меньше ><или ><равные ><6. ><Альфа ><- ><самое ><плохое ><значение, ><которое ><может ><принимать ><МАХ, ><если ><будет ><придерживаться ><"наилучшей" ><стратегии. ><Точно ><так ><же, ><если ><значение ><бета ><для ><узла ><равно ><6, ><то ><не ><следует ><рассматривать ><нижележащие ><вершины ><МАХ, ><с ><которыми ><связаны ><значения ><6 ><или ><более.>

<><Глава ><4. ><Эвристический ><поиск>

<175>

><<>

<Рис. ><4.18. ><Двухуровневый ><минимакс ><и ><один ><из ><двух ><возможных ><вторых ><ходов ><МАХ>

<><176>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<Начиная ><альфа-бета-процедуру, ><мы ><опускаемся ><на ><полную ><глубину ><графа, ><используя ><поиск ><в ><глубину, ><и ><вычисляем ><эвристические ><оценки ><для ><всех ><состояний ><этого ><уровня. ><Предположим, ><что ><все ><они ><- ><узлы ><Максимальное ><из ><этих ><значений ><>возвращается< ><родительскому ><состоянию ><(узлу ><МАХ, ><как ><и ><в ><алгоритме ><минимакса). ><Затем ><это ><>значение< ><передается ><прародителям ><узлов ><как ><потенциальное ><граничное ><значение ><бета.>

<Затем ><алгоритм ><опускается ><к ><другим ><потомкам ><потомков ><и ><не ><рассматривает ><их ><>родительские< ><состояния, ><если ><их ><значения ><больше ><или ><равны ><данному ><значению ><бета. ><>Аналогичные< ><процедуры ><можно ><описать ><для ><альфа-отсечения ><по ><потомкам ><второго ><поколения ><вершины ><МАХ.>

<Существуют ><два ><условия ><останова ><алгоритма ><поиска ><на ><основе ><значений ><альфа ><и ><бета.>

<Поиск ><может ><быть ><остановлен ><ниже ><любого ><узла ><значение ><бета ><которого

><меньше ><или ><равно ><значению ><альфа ><любого ><из ><его ><предков ><МАХ.>

<Поиск ><может ><быть ><остановлен ><ниже ><любого ><узла ><МАХ, ><значение ><альфа ><которого

><больше ><или ><равно ><значению ><бета ><любого ><из ><его ><предков >

<>

<Рис. ><4.19. ><Двухуровневый ><минимакс ><применительно ><к ><ходу ><в ><конце ><игры ><[Nilsson, ><1971]>

<Таким ><образом, ><альфа-бета-усечение ><выражает ><отношение ><между ><узлами ><уровней ><п ><и ><При ><этом ><из ><рассмотрения ><могут ><быть ><исключены ><целые ><поддеревья ><с ><корнями ><на ><уровне ><Например, ><на ><рис. ><4.20 ><изображено ><пространство ><поиска ><из ><рис. ><4.15, ><к ><ко><торому ><применен ><алгоритм ><альфа-бета-усечения. ><Заметим, ><что ><результирующее ><возвра­><щаемое ><значение ><идентично ><полученному ><в ><алгоритме ><минимакса, ><но ><при ><этом ><процеду­><ра ><альфа-бета-усечения ><значительно ><экономичнее ><минимакса.>

<При ><удачном ><порядке ><состояний ><в ><области ><поиска ><процедура ><альфа-бета-усечения ><может ><эффективно ><удваивать ><глубину ><поиска ><в ><рассматриваемом ><пространстве ><при ><фиксированных ><пространственно-временных ><характеристиках ><компьютера ><[Nilsson, ><1980]. ><Если ><же ><узлы ><рас><положены ><неудачно, ><процедура ><альфа-бета-усечения ><осуществляет ><поиск ><в ><таком ><же ><про><странстве, ><как ><и ><обычный ><минимакс. ><Однако ><поиск ><проводится ><только ><за ><один ><проход.>

<><Глава ><4. ><Эвристический ><поиск>

<177>

><<4.4. ><Проблемы ><сложности>

<><Наиболее ><сложным ><аспектом ><комбинаторных ><задач ><является ><экспоненциальный ><рост ><пространства ><поиска, ><который ><зачастую ><не ><учитывают ><разработчики ><программ. ><Поскольку ><основные ><виды ><человеческой ><деятельности ><(вычислительной ><и ><другой) ><происходят ><в ><>линейном< ><времени, ><нам ><трудно ><представить ><себе ><экспоненциальный ><рост. ><Мы ><часто ><слышим ><жалобу: ><"Если ><бы ><я ><имел ><более ><мощный ><(или ><быстрый ><или ><высоко ><производительный) ><компьютер, ><моя ><проблема ><была ><бы ><решена". ><Такие ><жалобы, ><часто ><вызываемые ><проблемой ><"взрывного" ><роста ><числа ><состояний, ><обычно ><беспочвенны. ><Просто ><проблема ><была ><понята ><не ><достаточно ><глубоко ><и ><не ><были ><предприняты ><действия ><по ><ее ><решению.>

<Комбинаторный ><рост ><ошеломляет. ><Было ><показано, ><что ><количество ><состояний, ><просматри><ваемых ><при ><полном ><переборе ><в ><пространстве ><возможных ><шахматных ><ходов, ><составляет ><10><120><. ><Это ><не ><просто ><"очень ><большое ><количество" ><- ><это ><число ><сопоставимо ><с ><числом ><молекул ><во ><вселенной ><или ><с ><числом ><наносекунд, ><прошедших ><после ><"большого ><взрыва".>

<>

<Рис. ><4.20. ><Альфа-бета-усечение ><применительно ><к ><пространству ><со­><стояний ><из ><рис. ><4.15. ><Состояния ><без ><числовых ><меток ><не ><оценивались>

<Были ><предложены ><несколько ><метрик ><для ><вычисления ><сложности. ><Одна ><из ><них ><- ><фактор ><ветвления ><пространства. ><Фактор ><ветвления ><определяется ><как ><среднее ><количест­><во ><ветвей ><(потомков), ><выходящих ><из ><любого ><состояния ><в ><пространстве ><поиска. ><Число ><со><стояний ><на ><глубине ><л ><поиска ><равно ><фактору ><ветвления, ><возведенному ><в ><степень. ><По­><сле ><вычисления ><фактора ><ветвления ><можно ><оценить ><стоимость ><поиска ><пути ><любой ><длины. ><На ><рис. ><4.21 ><показана ><зависимость ><между ><фактором ><ветвления ><Б, ><длиной ><пути ><и ><общим ><количеством ><состояний ><Т ><в ><процессе ><поиска ><для ><малых ><значений. ><Графики ><представлены ><в ><логарифмическом ><масштабе, ><поэтому ><- ><не ><прямая ><линия.>

<Несколько ><примеров ><из ><этого ><рисунка ><показывают, ><как ><плохи ><дела ><на ><самом ><деле. ><Ес><ли ><фактор ><ветвления ><равен ><2 ><(например, ><в ><бинарном ><дереве), ><то ><для ><исследования ><всех ><путей ><на ><шесть ><уровней ><вглубь ><области ><поиска ><требуется ><рассмотреть ><приблизительно ><100 ><состояний. ><А ><для ><углубления ><на ><12 ><уровней ><требуется ><рассмотреть ><около ><10000 ><со><стояний. ><Если ><фактор ><ветвления ><может ><быть ><уменьшен ><до ><1,5 ><(с ><помощью ><эвристики ><или>

<><178>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

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

<Математическая ><формула ><зависимости, ><представленной ><на ><рис. ><4.21, ><имеет ><вид>

<Т= ><В ><+ ><В><2>< ><+ ><3>< ><+…+BL>

<где ><- ><общее ><количество ><состояний, ><- ><длина ><пути, ><а ><В ><- ><коэффициент ><ветвления. ><Это ><уравнение ><можно ><привести ><к ><виду>

<->< ><1)/(B->< ><1).>

<>

<Рис. ><4.21. ><Число ><сгенерированных ><узлов ><как ><функция ><от ><фактора ><ветвления ><В ><для ><различной ><длины ><пути ><решения ><Соответствующее ><соотношение ><имеет ><вид ><-1 ><)/(B-1><) ><[Nilsson, ><1980]>

<Измерение ><пространства ><поиска- ><эмпирический ><процесс, ><требующий ><детального ><знакомства ><с ><задачей ><и ><проверки ><различных ><ее ><вариантов. ><Предположим, ><например, ><что ><требуется ><найти ><фактор ><ветвления ><в ><игре ><в ><"пятнашки". ><Для ><этого ><вычислим ><общее ><чис­><ло ><возможных ><ходов. ><По ><2 ><хода ><возможны ><для ><каждого ><угла ><- ><всего ><8 ><угловых ><ходов; ><по ><3 ><- ><для ><центра ><каждой ><стороны ><- ><всего ><12 ><ходов ><и ><4 ><для ><центра ><доски. ><Таким ><обра­><зом, ><всего ><получается ><24 ><хода. ><Разделив ><это ><число ><на ><9 ><(возможное ><количество ><различ­><ных ><местоположений ><пустой ><клетки), ><получим, ><что ><средний ><фактор ><ветвления ><равен ><2,67. ><Как ><показано ><на ><рис. ><4.21, ><это ><не ><очень ><хорошее ><значение ><для ><глубокого ><поиска. ><Если ><не ><принимать ><во ><внимание ><ходы, ><ведущие ><назад ><к ><родительскому ><состоянию ><(используемые ><в ><алгоритмах ><поиска, ><описанных ><в ><этой ><главе), ><то ><в ><каждом ><состоянии ><будет ><на ><один ><ход ><меньше. ><В ><этом ><случае ><фактор ><ветвления ><равен ><1,67, ><что ><делает ><воз><можным ><полный ><перебор ><(в ><некоторых ><пространствах ><состояний).>

<Как ><было ><показано ><в ><главе ><3, ><сложность ><алгоритма ><может ><быть ><определена ><размерами ><списков ><и ><Чтобы ><поддерживать ><приемлемый ><размер ><списка ><можно>

<><Глава ><4. ><Эвристический ><поиск>

<179>

><<сохранять ><в ><нем ><только ><несколько ><(эвристически) ><лучших ><состояний. ><Это ><может ><>ускорить< ><поиск. ><Однако ><в ><этом ><случае ><существует ><опасность ><потери ><лучшего ><состояния ><и ><да­><же ><решения. ><Метод ><поддержания ><определенных ><рамок ><поиска ><в ><зависимости ><от ><числа ><шагов ><называется ><"лучевым ><поиском" ><(beam >

<>

<Рис. ><4.22. ><Неформальный ><график ><стоимости ><поиска ><и ><стоимости ><вычисления ><эвристической ><оценки ><в ><зависимости ><от ><информирован­><ности ><эвристики ><[Nilsson, ><1980]>

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

<На ><рис. ><4.22, ><взятом ><из ><[Nilsson, ><1980], ><представлен ><неформальный ><результат ><>анализа< ><этих ><вопросов. ><По ><оси ><абсцисс ><отложено ><количество ><информации, ><которая ><учтена ><в ><эвристике ><для ><улучшения ><ее ><эффективности. ><По ><оси ><ординат ><показаны ><затраты ><про­><цессора ><на ><осуществление ><поиска. ><Если ><эвристика ><становится ><более ><информирован­><ной, ><затраты ><процессорного ><времени ><на ><рассмотрение ><состояний ><уменьшаются, ><пото­><му ><что ><необходимо ><просматривать ><меньшее ><количество ><состояний. ><Общая ><стоимость ><нахождения ><пути ><решения ><- ><это ><общая ><стоимость ><эвристических ><вычислений ><плюс ><стоимость ><просмотра ><пространства ><поиска. ><Желательно, ><чтобы ><общая ><стоимость ><тако­><го ><поиска ><была ><минимальной.>

<В ><заключение ><следует ><отметить, ><что ><важной ><областью ><исследований ><является ><эври><стический ><поиск ><на ><графах ><И/ИЛИ, ><так ><как ><подобную ><форму ><имеет ><пространство ><состоя­><ний ><для ><экспертных ><систем. ><Поиск ><на ><этих ><структурах ><включает ><компоненты, ><обсуждав­><шиеся ><в ><этой ><и ><предыдущей ><главах. ><Поскольку ><для ><нахождения ><пути ><к ><цели ><необходимо ><просмотреть ><все ><потомки ><узлов ><И, ><эвристическая ><оценка ><стоимости ><поиска ><для ><узла ><И ><представляет ><собой ><сумму ><оценок ><поиска ><его ><потомков.>

<><180>

<Часть ><Искусственный ><интеллект ><как ><представление ><и ><поиск>

><<4.5. ><Резюме ><и ><дополнительная ><литература>

<><Пространства ><поиска ><интересных ><задач ><обычно ><увеличиваются ><экспоненциально. ><Эв><ристический ><поиск ><- ><это ><основной ><инструмент ><для ><управления ><таким ><"комбинаторным ><взрывом". ><В ><данной ><главе ><представлен ><"жадный" ><алгоритм ><поиска, ><а ><затем ><проанализи­><ровано ><поведение ><эвристических ><алгоритмов. ><Мы ><рассмотрели ><такие ><их ><свойства, ><как ><допустимость, ><монотонность ><и ><информированность. ><Эвристический ><поиск ><был ><рассмот­><рен ><на ><простых ><примерах ><типа ><игры ><в ><"пятнашки", ><а ><затем ><распространен ><на ><более ><слож­><ные ><пространства ><состояний, ><возникающие ><при ><проектировании ><экспертной ><системы ><(глава ><6). ><В ><данной ><главе ><также ><была ><рассмотрена ><эвристика, ><применяемая ><в ><играх ><с ><двумя ><участниками. ><Она ><использует ><процедуру ><минимакса ><и ><альфа-бетаусечения ><для ><предсказания ><ходов ><противника. ><Теория ><сложности ><играет ><важную ><роль ><почти ><в ><каждой ><области ><информатики, ><особенно ><при ><анализе ><роста ><пространства ><состояний ><и ><>эвристическом< ><усечении. ><Теория ><сложности ><исследует ><сложность ><задач ><(в ><противоположность ><>алгоритмам<). ><Ключевая ><посылка ><теории ><сложности ><состоит ><в ><наличии ><класса ><существенно ><сложных ><задач. ><Этот ><класс, ><получивший ><название ><класса ><-сложных ><задач ><(Nondeterministically ><включает ><проблемы, ><которые ><не ><могут ><быть ><решены ><в ><разумное ><время ><без ><использования ><эвристики. ><Этому ><классу ><принадлежат ><почти ><все ><за­><дачи ><поиска. ><По ><этой ><проблеме ><мы ><особенно ><рекомендуем ><книги ><[Garey ><и ><1979] ><и ><[Moret ><и ><1991].>

<В ><[Pearl, ><1984] ><детально ><описаны ><такие ><вопросы, ><как ><разработка ><и ><анализ ><эвристик. ><В ><[Korf, ><1987, ><1998, ><1999] ><продолжено ><исследование ><алгоритмов ><поиска, ><в ><том ><числе ><опи><сан ><алгоритм ><Программы ><игры ><в ><шахматы ><вызывают ><постоянный ><интерес ><на ><про­><тяжении ><всей ><истории ><развития ><искусственного ><интеллекта. ><Новые ><результаты ><в ><этой ><об­><ласти ><часто ><представляются ><и ><обсуждаются ><на ><ежегодных ><конференциях.>

<Автор ><благодарит ><Нильса ><Нильсона ><[Nilsson, ><1980] ><за ><его ><подход ><и ><примеры, ><которые ><были ><использованы ><в ><этой ><главе.>

<4.6. ><Упражнения>

<><Придумайте ><эвристику, ><которую ><можно ><было ><бы ><использовать ><в ><программе ><>размещения< ><блоков ><для ><решения ><задачи ><"поставить ><блок ><на ><блок ><Будет ><ли ><такая ><>эвристика< ><допустимой? ><Монотонной?>

<Головоломка ><скользящих ><фишек ><включает ><три ><черные ><и ><три ><белые ><фишки, ><а ><также

><пустую ><клетку, ><как ><показано ><на ><рис. ><4.23.>

<В ><этой ><головоломке ><допустимы ><два ><хода ><с ><соответствующей ><стоимостью.>

<Фишку ><можно ><передвинуть ><в ><соседнюю ><пустую ><позицию. ><Этот ><ход ><стоит ><1. ><Фишка ><>может< ><перепрыгивать ><на ><пустое ><место ><через ><одну ><или ><две ><другие ><фишки. ><Стоимость ><этого ><хода ><равна ><количеству ><перепрыгнутых ><фишек.>

<Цель ><игры ><состоит ><в ><том, ><чтобы ><все ><белые ><фишки ><расположить ><слева, ><а ><черные ><- ><справа. ><Местоположение ><пустой ><клетки ><не ><важно.>

<Проанализируйте ><сложность ><пространства ><состояний ><и ><наличие ><циклов.>

<Предложите ><эвристику ><для ><решения ><этой ><проблемы ><и ><проанализируйте ><ее ><на ><>допустимость<, ><монотонность ><и ><информированность.>

<><Глава ><4. ><Эвристический ><поиск>< ><181>

><

<Рис. ><4.23. ><Головоломка ><скользящих ><блоков>

<3.>< ><Сравните ><три ><эвристики ><для ><игры ><в ><"пятнашки" ><(см. ><рис. ><4.8) ><с ><эвристикой ><сложения

><суммы ><расстояний ><для ><фишек, ><находящихся ><не ><на ><своих ><местах, ><с ><удвоенным ><числом

><прямых ><перестановок. ><Сравните ><их ><по ><следующим ><критериям:>

<а)>< ><точность ><оценки ><расстояния ><к ><цели. ><Для ><этого ><требуется ><найти ><кратчайший ><путь ><к

><решению, ><а ><затем ><использовать ><его ><как ><эталон;>

<б)>< ><информированность. ><Какая ><из ><упомянутых ><эвристик ><наиболее ><эффективно ><сокра><щает ><пространство ><состояний?>

<в)>< ><монотонность ><для ><игры ><в ><"пятнашки";>

<г)>< ><допустимость. ><Какая ><из ><этих ><эвристик ><ограничена ><сверху ><фактической ><стоимостью

><пути ><к ><цели? ><Обоснуйте ><свои ><предположения ><для ><общего ><случая ><или ><приведите

><контрпример.>

<4.>< ><а. ><Как ><было ><сказано ><выше, ><"жадный" ><алгоритм ><поиска ><для ><предотвращения ><зацикли><вания ><использует ><список ><А ><что ><если ><отказаться ><от ><этого ><теста ><и ><определять

><зацикливания ><на ><основе ><Сравните ><эффективность ><этих ><двух ><подходов.>

<б. ><Функция ><не ><проверяет, ><является ><ли ><состояние ><целевым, ><пока ><оно ><не ><удалено ><из ><списка ><Эту ><проверку ><можно ><выполнять ><при ><рассмот><рении ><новых ><состояний. ><Как ><это ><отразится ><на ><эффективности ><алгоритма? ><На ><допус­><тимости?>

<5.>< ><Докажите, ><что ><алгоритм ><А* ><допустим. ><Подсказка: ><при ><доказательстве ><следует ><пока><зать, ><что:>

<а)>< ><для ><алгоритма ><А* ><поиск ><закончится;>

<б)>< ><в ><списке ><всегда ><существует ><узел, ><который ><находится ><на ><оптимальном ><пути

><к ><цели;>

<в)>< ><если ><путь ><к ><цели ><существует, ><то ><алгоритм ><А* ><закончится ><нахождением ><оптималь><ного ><пути ><к ><цели.>

<Подразумевает ><ли ><допустимость ><выполнение ><свойства ><монотонности ><эвристики? ><Ес><ли ><нет, ><опишите, ><когда ><допустимость ><подразумевает ><монотонность.>

<Докажите, ><что ><набор ><состояний, ><рассмотренных ><в ><алгоритме ><А*, ><является ><подмноже­

><ством ><состояний ><поиска ><в ><ширину.>

<Докажите, ><что ><более ><информированная ><эвристика ><просматривает ><более ><узкую ><об­

><ласть ><поиска. ><Подсказка: ><формализуйте ><доказательство, ><представленное ><в ><подраз><деле ><4.2.3.>

<Шифр ><Цезаря ><- ><это ><простая ><схема ><кодирования, ><основанная ><на ><циклических ><пере><становках ><алфавита, ><в ><которой ><символ ><алфавита ><заменяется ><(><+n)-м ><символом.

><Например, ><при ><использовании ><шифра ><Цезаря ><со ><сдвигом ><4 ><слово ><"Caesar" ><запишется

><как ><"Geiwev".>

<9.1. ><Приведите ><три ><эвристики, ><которые ><можно ><использовать ><для ><расшифровки ><шиф><ра ><Цезаря.

182>

<<<9.2. ><В ><простом ><шифре ><подстановки ><каждый ><символ ><заменяется ><другим ><на ><основе ><>некоторого< ><произвольного ><взаимно ><однозначного ><отображения. ><Какая ><из ><эвристик, ><предложенных ><для ><шифра ><Цезаря, ><может ><использоваться ><для ><расшифровки ><такого ><шифра? ><Объясните. ><(Спасибо ><Дону ><Моррисону ><(Don ><за ><этот ><вопрос.)>

<Реализуйте ><стратегию ><минимакса ><на ><дереве, ><показанном ><на ><рис. ><4.24.>

<Выполните ><альфа-бета-усечение ><слева ><направо ><для ><дерева ><из ><упражнения ><10. ><Выполните

><на ><этом ><же ><дереве ><усечение ><справа ><налево. ><Объясните, ><почему ><результаты ><отличаются.>

<Рассмотрите ><трехмерную ><игру ><в ><"крестики-нолики". ><Проанализируйте ><сложность

><пространства ><состояний. ><Предложите ><эвристику ><для ><этой ><игры.>

<Выполните ><альфа-бета-усечение ><для ><игры ><в ><"крестики-нолики" ><(см. ><рис. ><4.17,4.18 ><и ><4.19).

><Сколько ><вершин ><можно ><устранить ><в ><каждом ><случае?>

<а. ><Создайте ><алгоритм ><для ><эвристического ><поиска ><на ><графе ><И/ИЛИ. ><Обратите ><внима­><ние ><на ><то, ><что ><для ><определения ><значения ><родительского ><узла ><необходимо ><просмот><реть ><значения ><всех ><его ><потомков. ><Таким ><образом, ><при ><вычислении ><эвристических

><оценок ><стоимости ><пути ><к ><цели ><оценка ><стоимости ><узла ><состоит ><(как ><минимум) ><из

><суммы ><оценок ><стоимости ><различных ><ветвей.>

<б. ><Используйте ><этот ><алгоритм ><для ><поиска ><на ><графе ><(рис. ><4.25).>

<>

<>

<Рис. ><4.24. >< >< ><Дерево >< >< >< ><для >< >< ><применения ><принципа ><минимакса>

<Рис. ><4.25. ><Пример ><графа ><для ><поиска>

<><Глава ><4. ><Эвристический ><поиск>

<183>

><>

<<>

<>

Глава 5. <Управление ><поиском ><и ><его ><реализация ><в ><пространстве ><состояний>

<Если ><мы ><аккуратно ><отделим ><влияние ><среды, ><в ><которой ><выполняется ><задача, ><от ><влия><ния ><аппаратных ><компонентов ><и ><организации, ><то ><получим ><истинную ><простоту ><адаптив><ной ><системы. ><Как ><мы ><видели, ><для ><описания ><способа ><решения ><человеком ><таких ><задач, ><как ><шахматы, ><логика ><и ><криптоарифметика ><(cryptarithmetic), ><необходимо ><постулировать ><только ><очень ><простую ><систему ><обработки ><информации. ><Очевидно ><сложное ><поведение ><системы ><обработки ><информации ><в ><данной ><среде ><обусловлено ><взаимодействием ><требова><ний ><среды ><с ><несколькими ><основными ><параметрами ><системы, ><в ><частности,>

<характеристиками ><ее ><блоков ><памяти.>

<- ><А. ><Ньюэлл ><и ><Н. ><А. ><Саймон, ><Решение ><проблем ><человеком, ><1972>

<То, ><что ><мы ><называем ><началом, ><часто ><будет ><концом,>

<Приходя ><к ><концу, ><мы ><приходим ><к ><началу.>

<Конец ><- ><это ><наше ><начало...>

<- ><Т. ><С. ><Элиот ><(Т. ><Четыре ><квартета>

<5.0. ><Введение>

<><В ><главах ><3 ><и ><4 ><представлены ><задачи, ><решаемые ><методом ><поиска ><в ><пространстве ><со><стояний. ><Этот ><подход ><"пространства ><состояний" ><к ><решению ><задачи ><позволяет ><использо><вать ><теорию ><графов ><для ><создания ><и ><анализа ><компьютерных ><программ. ><В ><главе ><3 ><опреде><лен ><общий ><алгоритм ><поиска ><с ><возвратами ><, ><а ><также ><алгоритмы ><поиска ><в ><глубину ><и ><в ><ши><рину. ><Эвристический ><поиск ><был ><представлен ><в ><главе ><4. ><Следующие ><понятия ><характеризуют ><данные ><и ><управляющие ><структуры, ><используемые ><для ><реализации ><поиска ><в ><пространстве ><состояний.>

назад содержание далее



ПОИСК:




© FILOSOF.HISTORIC.RU 2001–2021
Все права на тексты книг принадлежат их авторам!

При копировании страниц проекта обязательно ставить ссылку:
'Электронная библиотека по философии - http://filosof.historic.ru'
Сайт создан при помощи Богданова В.В. (ТТИ ЮФУ в г.Таганроге)