Примечания и дополнительная литература
PSPACE-полноту задачи QSAT доказали Стокмейер и Мейер (Stockmeyer, Meyer, 1973).
Некоторые базовые результаты PSPACE-полноты для игр с двумя участниками приведены у Шефера (Schaefer, 1978), а также у Стокмейера и Чандры (Stockmeyer, Chandra, 1979). Задача конкурентного размещения, рассматриваемая здесь, явля- ется адаптированным примером класса задач, изучаемых более общей областью размещения объектов; например, обзорную информацию по этой теме можно найти в книге под редакцией Дрезнера (Drezner, 1995).
Игры для двух игроков постоянно порождали сложные вопросы для ученых в области математики и искусственного интеллекта. Берлекамп, Конуэй и Гай (Berlekamp, Conway, Guy, 1982) и Новаковски (Nowakowski, 1998) обсуждают неко- торые математические вопросы в этой области.
Разработка шахматной программы уровня чемпиона мира в течение 50 лет считалась основной задачей прикладного программирования в области компьютерных интеллектуальных игр. Известно, что Алан Тьюринг работал над алгоритмами для игры в шахматы, как и многие ведущие специалисты в области искусственного интеллекта тех лет. Ньюборн (Newborn, 1996) рассказывает об истории работы над задачей вплоть до момента за год до того, как компьютеру IBM Deep Blue наконец-то удалось победить чемпиона мира.Построение плана относится к числу фундаментальных задач в области ис- кусственного интеллекта; она занимает видное место в работе Рассела и Норвига (Russell, Norvig, 2002), а также является темой книги Галлаба, Нау и Траверсо (Ghallab, Nau, Traverso, 2004). Обоснование возможности решения задачи по- строения плана с полиномиальным пространством приводится в работе Савича (Savitch, 1970), посвященной вопросам теории сложности, а не задаче построения плана как таковой.
Примечания к упражнениям
Упражнение 1 основано на задаче, о которой мы узнали от Мэверика Ву и Райана Уильямса; упражнение 2 основано на результате Томаса Шефера.
Еще по теме Примечания и дополнительная литература:
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Список дополнительной литературы
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература
- Дополнительная литература