УПРАЖНЕНИЯ
5.1. Самостоятельно сформулируйте определения следующих понятий: проблема удовлетворения ограничений, ограничение, поиск с возвратами, совместимость дуги, обратный переход и минимизация конфликтов.
5.2. Сколько решений имеет задача раскрашивания карты, показанная на рис. 5.1 ?
5.3. Объясните, почему при поиске решения задачи CSP одна из хороших эвристик состоит в том, что следует выбирать переменную, которая является наиболее ограниченной, и вместе с тем выбирать наименее ограничительное значение.
5.4. Рассмотрите задачу составления (а не решения) кроссвордов2: подбора слов, которые укладываются в прямоугольную сетку. Эта сетка, которая указывается как часть задания, определяет, какие квадраты пусты и какие затенены. Предположим, что предоставлен список слов (например, словарь) и задача состоит в том, чтобы заполнить пустые квадраты с использованием любого подмножества из этого списка. Точно сформулируйте эту задачу следующими двумя способами.
а) Как общую задачу поиска. Выберите соответствующий алгоритм поиска и
определите эвристическую функцию, если, по вашему мнению, она необ-
ходима. Как лучше заполнять пустые квадраты: одновременно по одной
букве или по одному слову?
б) Как задачу удовлетворения ограничений. Должны ли переменные быть представлены в виде слов или букв?
Какая формулировка, по вашему мнению, является наилучшей? Объясните, почему?
5.5. Приведите точные формулировки каждой из перечисленных ниже задач в виде
задач удовлетворения ограничений.
а) Планирование покрытия пола прямоугольниками. Найти в большом
прямоугольнике неперекрывающиеся места для размещения меньших
прямоугольников.
б) Составление расписания занятий. Определены следующие исходные данные: постоянное количество преподавателей и классов, список предлагаемых занятий и список возможных временных интервалов для занятий. С каждым преподавателем связано множество занятий, которые он может проводить.
5.6. Решите криптоарифметическую задачу, приведенную на рис. 5.2, вручную, с помощью поиска с возвратами, предварительной проверки, а также на основе эвристик с MRV и наименее ограничительным значением.
5.7. dfe В табл. 5.1 приведены результаты проверки производительности различных алгоритмов при решении задачи с п ферзями. Проведите испытания тех же алгоритмов при решении задач раскрашивания карты, формируемых случайным образом, с помощью следующего метода: разбросать п точек на единичном квадрате; выбрать точку X случайным образом, соединить X прямой линией с ближайшей точкой у, такой, что X еще не соединена с У, и соединительная линия не пересекает какую-либо другую линию; повторять предыдущий шаг до тех пор, пока не будет исключена возможность проводить дальнейшие соединения. Сформируйте таблицу производительности для наибольшего значения л, с которым удастся справиться с помощью этих алгоритмов, используя как d=4, так и d=3 цветов. Прокомментируйте полученные вами результаты.
5.8. Воспользуйтесь алгоритмом АС-3, чтобы показать, что проверка совместимости дуг позволяет обнаружить несовместимость частичного присваивания {WA=red, V=blue} для задачи, показанной на рис. 5.1.
5.9. Какова в наихудшем случае временная сложность при прогоне алгоритма АС-3 применительно к задаче CSP с древовидной структурой?
5.10. Алгоритм АС-3 помещает обратно в очередь каждую дугу (Хк, XJ каждый раз, когда любое значение удаляется из области определения xL, даже если каждое значение Хк совместимо с несколькими оставшимися значениями Xi. Предположим, что для каждой дуги (Xk,Xi) отслеживается количество оставшихся значений xi? которые являются совместимыми с каждым значением хк. Объясните, как можно эффективно обновлять эти числа, и тем самым докажите, что совместимость дуг можно обеспечить за суммарное время 0{n2d2).
5.11. Покажите, как можно преобразовать одно тернарное ограничение, такое как "А+В=С", в три бинарных ограничения с использованием вспомогательной переменной. Может быть принято предположение о конечных областях определения. (Подсказка. Предусмотрите использование новой переменной, которая принимает значения, являющиеся парами других значений, и примените такие ограничения, как "Xявляется первым элементом пары Y".) Затем покажите, как можно трактовать аналогичным образом ограничения больше чем с тремя переменными. Наконец, покажите, как можно устранить унарные ограничения, модифицируя области определения переменных. На этом завершается демонстрация того, что любую задачу CSP можно преобразовать в задачу CSP только с бинарными ограничениями.
5.12. Ш Предположим, что известно, будто граф имеет множество разрыва цикла, содержащее не больше к узлов. Опишите простой алгоритм поиска минимального множества разрыва цикла, время прогона которого не намного превышает 0(пк) для задачи CSP с п переменными. Найдите в литературе методы обнаружения приближенно минимальных множеств разрыва цикла за время, которое полиномиально зависит от размера множества разрыва. Обеспечивает ли наличие таких алгоритмов практическую применимость метода поиска на основе множества разрыва цикла?
5.13. Рассмотрите приведенную ниже логическую головоломку. В пяти домах, имеющих разный цвет, живут лица пяти национальностей, которые предпочитают разные сорта сигарет, пьют разные напитки и держат разных домашних питомцев. На основе следующих фактов найдите ответ на вопрос: "В каком доме держат зебру и в каком доме пьют воду?"
• Англичанин живет в доме красного цвета.
• Испанец держит собаку.
• Норвежец живет в первом доме слева.
• Сигареты "Куле" курят в доме желтого цвета.
• Человек, курящий "Честерфилд", живет рядом с домом человека, который держит лису.
• Норвежец живет рядом с домом синего цвета.
• Человек, курящий "Уинстон", держит улиток.
• Человек, курящий "Лаки Страйк", пьет апельсиновый сок.
• Украинец пьет чай.
• Японец курит "Парламент".
• Сигареты "Куле" курят в доме, находящемся рядом с домом, где держат лошадь.
• Кофе пьют в доме зеленого цвета.
• Дом зеленого цвета находится непосредственно справа (с точки зрения того, кто решает эту задачу) от дома цвета слоновой кости.
• Молоко пьют в среднем доме.
Обсудите различные представления этой задачи в виде задачи CSP. По каким причинам следовало бы предпочесть одно представление другому?
Игры заставляли людей напрягать свои интеллектуальные способности (иногда до угрожающей степени) на протяжении всего существования цивилизации. В силу своего абстрактного характера игры являются привлекательным объектом исследований и в области искусственного интеллекта. Состояние игры можно легко представить, а поведение агентов обычно ограничено небольшим количеством действий, результаты которых определяются с помощью точных правил. Спортивные игры, такие как крокет и хоккей с шайбой, имеют гораздо более сложные описания, значительно больший диапазон возможных действий и довольно неточные правила, определяющие допустимость действий. За исключением проблематики создания робота-футболиста эти спортивные игры не привлекают значительного интереса в сообществе специалистов по искусственному интеллекту.
Ведение игр было одной из первых задач, рассматриваемых в области искусственного интеллекта. К 1950 году, почти сразу же после того, как компьютеры стали программируемыми, шахматами уже интересовались Конрад Цузе (изобретатель первого программируемого компьютера и разработчик первого языка программирования), Клод Шеннон (основоположник теории информации), Норберт Винер (создатель современной теории управления) и Алан Тьюринг. С тех пор уровень игры с применением компьютеров неуклонно повышался и достиг того, что компьютеры превзошли людей в шашках и игре "Отелло" ("реверси"), побеждали чемпионов (но не всегда) в шахматах и нардах, а также стали конкурентоспособными во многих других играх. Основным исключением остается игра го, в которой компьютеры пока еще выступают на любительском уровне.
Игры, в отличие от большинства учебных задач, которые рассматривались в главе 3, интересны тем, что в них очень трудно найти решение. Например, шахматы характеризуются в среднем коэффициентом ветвления, примерно равным 35, а игра часто продолжается до 50 ходов со стороны каждого игрока, поэтому дерево поиска имеет приблизительно 35100 или 10154 узлов (хотя граф поиска включает "всего лишь" около 1040 различных узлов). Поэтому игры, как и реальная жизнь, требуют способности принимать хоть какие-то решения, даже если вычисление оптимального решения неосуществимо. Кроме того, игры сурово наказывают за неэффективность. Притом что реализация поиска А*, в два раза менее эффективная по сравнению с другой реализацией, просто потребует вдвое больше времени для получения окончательного решения, шахматная программа, вдвое менее эффективно использующая отведенное ей время, по-видимому, потерпит поражение на самых ранних этапах игры, даже при всех прочих равных условиях. Поэтому исследователи, работающие в области ведения игр, стали авторами многих интересных идей, касающихся того, как обеспечить наилучшее возможное использование времени.
Начнем описание данной темы с определения понятий оптимального хода игры и алгоритма его поиска. Затем рассмотрим методы выбора хорошего хода в условиях ограниченного времени. Отсечение позволяет игнорировать те части дерева поиска, которые не оказывают влияния на окончательный выбор, а эвристические функции оценки позволяют приближенно рассчитывать истинную полезность состояния без проведения полного поиска. В разделе 6.5 рассматриваются такие игры, включающие элемент случайности, как нарды; кроме того, в данной главе рассматривается бридж, который включает элементы неполной информации, поскольку не все карты видны каждому игроку. Наконец, в этой главе будет описано, как новейшие программы ведения игр постепенно преодолевают сопротивление людей в борьбе с этими программами и каковы направления будущих разработок.