3.7. Резюме. Использование фреймов в эвристическом поиске

3.7. Резюме. Использование фреймов в эвристическом поиске

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

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

Главной целью при решении задач должно быть стремление лучше понять пространство задачи и найти такие представления, в рамках которых данная задача решается довольно просто. Цель поиска состоит в том, чтобы получить информацию для формирования надлежащего представления, а не для нахождения решения, как это обычно предполагается; после того, как удастся соответствующим образом представить это пространство задачи, решение найти будет значительно легче.

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

Каким образом можно объединить новое правило с классической стратегией минимакса? Пусть мы находимся в определенном узле А дерева решения (играя в какую-нибудь игру, например, шахматы) и исследуем два (или более) возможных хода, скажем В и С. Каждый из этих ходов получает значения оценок V(B) и V(C). Затем оба этих значения объединяются с помощью функции М для того, чтобы выработать одну общую оценку

S(A) = M( V(B), V(C) ) .

По существу, с помощью функции М должны подводиться итоги поиска на всем дереве ниже узла А и определяться оценка позиции А.

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

Если значение S(B) невелико, то можно предположить, что В — неудачная позиция. Но если мы хотим, чтобы генератор ходов не повторял своих прежних ошибок, сообщение S должно включать некоторую дополнительную информацию относительно того, чем нас не удовлетворяет позиция В или как поступить в данном случае. Нам фактически требуется итоговое объяснение того, что обнаружено в процессе поиска; поскольку мы работаем с деревом перебора, нам требуется также рекурсивное суммирование подобных резюме.

Рассмотрим проблему, названную нами «расхождением резюме». Если резюме для ситуации А содержит (в общем случае) любое явное описание для В и С, то существует опасность того, что любая схема рекурсивного описания будет повторять дерево ходов; это приведет к столь же длительному поиску итогового сообщения, как и поиску самого решения. Чтобы этого не произошло, можно воспользоваться довольно простым способом — ограничить размеры самого резюме. В этом случае следует позаботиться о том, чтобы избежать сильного уменьшения информативности сообщений. Во фреймах-описаниях важные черты и отношения, находящиеся на верхних уровнях, могут служить в качестве резюме, а вспомогательные описания становятся доступными лишь по необходимости. Вопрос о том, какая часть проанализированного дерева должна оставаться в долговременной памяти, а какая отбрасываться после того, как сделан очередной ход, зависит от других аспектов использования участником игры всего накопленного им опыта.

Какие принципы должны лежать в основе образования резюме? И в этом вопросе концепция фреймов демонстрирует свою гибкость. Вместо того чтобы попытаться ограничить сообщения какими-то жесткими форматами, мы можем построить набор «резюме»-фреймов для каждого данного случая; любой фрейм будет вызываться, когда его терминалы подходят к описаниям ситуаций более низких уровней, а маркеры согласуются с текущими целями. Таким образом, каждый из этих фреймов выполняет свою работу только тогда, когда он соответствует текущей ситуации. Например, у человека могут быть самые разные фреймы типа «шахматной вилки». Если конь занимает такую позицию, что угрожает одновременно и шахом, и взятием ладьи, то активируется фрейм вилки, соответствующий следующему условию: при любом из двух возможных ходов теряется та фигура, которая не изменит своей позиции. Как только будет активирован этот фрейм, он может дать конкретную рекомендацию, вероятно, следующего содержания: генератор ходов того игрока, который попадает под вилку, должен выяснить, не может ли какой-нибудь ранее сделанный ход обеспечить защиту того поля, откуда исходит угроза вилки.

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

5.1. Создание фреймов

Из книги автора

5.1. Создание фреймов Чтобы HTML-страница содержала фреймы, а экран был разделен на области, необходимо заменить пару тегов <BODY>..</BODY> в коде HTML-страницы парой тегов <FRAMESET>…</FRAMESET>. Необходимо также указать хотя бы один из атрибутов cols или rows. С помощью этих


5.4. Ссылки внутри фреймов

Из книги автора

5.4. Ссылки внутри фреймов В большинстве случаев при переходе по ссылке в окне браузера текущий документ заменяется новым. При использовании фреймов схема загрузки документов отличается от стандартной. Главное отличие – возможность загружать документ в выбранный фрейм


5.5. Изменение размеров фреймов

Из книги автора

5.5. Изменение размеров фреймов По умолчанию размеры фреймов можно изменять с помощью указателя мыши. Необходимо просто навести указатель на границу между фреймами и, зажав левую кнопку мыши, переместить границу влево или вправо, вверх или вниз (рис. 5.7). Рис. 5.7. Изменение


5.8. Достоинства и недостатки фреймов

Из книги автора

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


1.10. Образы и системы фреймов

Из книги автора

1.10. Образы и системы фреймов «Каждый человек охотно согласится с тем, что между двумя видами ощущений — непосредственными, когда человек, например, страдает от сильной жары или ему приятно разливающееся по всему телу тепло, и ощущениями, воскрешаемыми в памяти или


5.2. Глобальная система пространственных фреймов

Из книги автора

5.2. Глобальная система пространственных фреймов Мне не очень нравится предлагаемая ниже модель, но для систем ИИ раньше или позже нечто подобное непременно потребуется разработать. Глобальный пространственный фрейм (GSF) представляет собой постоянный набор «типичных


Глава 3 Способ формализации фреймов

Из книги автора

Глава 3 Способ формализации фреймов Одни из множества возможных способов формализации фрейма-сценария предполагает представление его в виде сети следующей иерархической структуры (рис.П2). Узел самого верхнего уровня сети (на рисунке ему соответствует кружок,


Помощь пользователей Интернета в поиске

Из книги автора

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


Использование фреймов

Из книги автора

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


Настройки фреймов

Из книги автора

Настройки фреймов После помещения изображения во фрейм мы можем работать отдельно с фреймом и отдельно с его содержимым – картинкой. Инструмент Direct Selection (Выделение напрямую), которым мы пользовались для того, чтобы «достать» до отдельных объектов группы, и здесь придет


Настройки текстовых фреймов

Из книги автора

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


Резюме: использование операторов if для организации выбора из нескольких вариантов

Из книги автора

Резюме: использование операторов if для организации выбора из нескольких вариантов КЛЮЧЕВЫЕ CЛOBA: if, else ОБЩИЕ ЗАМЕЧАНИЯ:      В каждой из последующих форм оператором может быть либо простои оператор, либо составной. Выражение "истинно" в обобщенном смысле, если его


Создание фреймов

Из книги автора

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


18.4.2. Применение символа | при поиске по шаблону

Из книги автора

18.4.2. Применение символа | при поиске по шаблону При использовании оператора case в качестве команды or можно указывать символ. Например, vt100|vt102) соответствует шаблону vt100 или vt102.В следующем примере у пользователя запрашивают тип терминала. Если пользователь вводит vt100 или


Простейшее решение в поиске места для парковки Николай Маслухин

Из книги автора

Простейшее решение в поиске места для парковки Николай Маслухин Опубликовано 24 июля 2013 Поиск места для парковки в современном мегаполисе может стать настоящей головной болью. Обочины заняты, дворы напоминают кладбище для машин, а


Общие сведения о поиске и индексировании

Из книги автора

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