Intel_Nils (526801), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

1Д, ГОЛОВОЛОМКИ И ИГРЫ КАК ПРИМЕРЫ ЗАДАЧ Мы еще не давали точного определения, что значит решить некоторую задачу с применением методов поиска. Точно так же мы не определили, что мы понимаем под задачей. По всей видимости, еще никем не было дано такого простого определения слова «задача», которое полностью бы соответствовало тому интуитивному значению, которое мы намереваемся здесь использовать.

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

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

Игра в пятнадцать (слева — начальная конфигурация, справа— целевая). Для иллюстрации понятий, возникающих при решении задач, мы часто будем пользоваться головоломкой, известной как игра в пятнадцать. В ней используется пятнадцать пронумерованных подвижных фишек, расположенных на площадке размером 4 К 4 клетки. Одна клетка этой площадки остается всегда пустой, так что всегда одну из соседних с ней фишек можно передвинуть на место этой пустой клетки, «передвинув», таким образом, и эту пустую клетку. Игра в пятнадцать иллюстрируется на рис. 1.1, на котором изображены две конфигурации фишек.

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

В этой задаче имеется точно определенная начальная ситуация и точно определенная цель. Имеется также некоторое множество операций, или ходов, переводящих одну ситуацию в другую. Мы начнем с введения некоторых фундаментальных понятий, связанных с нахождением решений, которые могут быть использованы для нахождения решения игры в пятнадцать. Гл. й Введение . 1.3. СОСТОЯНИЯ И ОПЕРАТОРЫ По-видимому, самый прямолинейный подход при поиске ре- шения для игры в пятнадцать состоит в попытке перепробовать различные ходы, пока не удастся получить целевую конфигура- цию. Такого рода попытка по существу связана с поиском прн помощи проб и ошибок. (Мы, разумеется, предполагаем, что та- кой поиск может быть выполнен в принципе, скажем, на некото- рой вычислительной машине, а не с привлечением реальной игры в пятнадцать). Отправляясь от начальной конфигурации, мы могли бы построить все конфигурации, возникающие в резуль- тате выполнения каждого из возможных ходов, затем построить следующее множество конфигураций после применения следую- щего хода н т.

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

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

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

Полосина из них (или примерно 10,5 10") достижима нз данной начальной конфигурации. Х8. Состояния и операторы Решение игры в пятнадцать можно было бы получить, используя процесс поиска 1перебора) '), цри котором прежде всего применяют операторы к начальному состоянию, с тем чтобы получить новые состояния, к которым также применяют операторы, и т.

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

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

Мы вернемся к дальнейшему обсуждению методов, связанных с пространством состояний, в следующих двух главах. ') В отечественной литературе широко используется слово «перебор» в качестве значения английского «зеагс)1» («поиск»). Ниже мы будем пользоввтьсн обоимн русскими терминами как зквивалентами — Призе перев. 1б Гм Е Введение ЕЯ. СВЕДЕНИЕ ЗАДАЧИ К ПОДЗАДАЧАМ В некотором смысле более тонкий подход к решению задачи связан с понятием подзадач. При таком подходе производится исследование исходной задачи с целью выделения такого множества подзадач, чтобы решение некоторого определенного подмножества этих подзадач содержало в себе решение исходной задачи.

Рассмотрим, например, задачу о проезде на автомобиле из Пало-Альто (шт. Калифорния) в Кембридж (шт. Массачусетс). Эта задача может быть сведена, скажем, к следующим подзадачам: Подзадача 1. Проехать из Пало-Альта в Сан-Франциско. Подзадача 2. Проехать из Сан-Франциско в Чикаго,шт.

Иллинойс. Подзадача 3. Проехать из Чикаго в Олбани, шт. Нью-Р(орк. Подзадача 4. Проехать из Олбани в Кембридж. Здесь решение всех четырех подзадач обеспечило бы некоторое решение первоначальной задачи. Каждая из подзадач может быть решена с применением какого. либо метода, К ним могут быть применены методы, использующие пространство состояний, или же их можно проанализировать с целью выделения для каждой своих подзадач и т.

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

Характеристики

Список файлов книги