Упражнения с решениями Упражнение с решением 1
(i) p1 = (0,0) (перемещение начинается от начала координат);
(ii) в последовательности нет двух одинаковых точек («маршрут» не повторя- ется);
(iii) для всех i = 1, 2, ..., n - 1 точки p. иpi+1 находятся на расстоянии 1 друг от друга (перемещение происходит между соседними точками в £).
Самоизбегающие блуждания (в двух и трех измерениях) используются в фи- зической химии как простая геометрическая модель возможных конфигураций длинноцепочечных полимерных молекул. Такие молекулы можно рассматривать как гибкую цепь, которая может изгибаться, принимая разные геометрические структуры; самоизбегающие блуждания всего лишь предоставляют простую ком- бинаторную абстракцию для таких структур.
В этой области существует знаменитая нерешенная задача: для натурального числа n > 1 количество разных самоизбегающих блужданий длины n обозначается A(n). Обратите внимание: блуждания рассматриваются как последовательности точек, а не как множества; даже если два блуждания проходят через одно множе- ство точек, но в разном порядке, они считаются разными. (Формально блуждания (p1, p2, ..., pn) и (q1, q2, ..., qn) считаются разными, если для некоторого i (1 < i < n) p. Ф qi.) Пример изображен на рис. 9.3. В полимерных моделях, основанных на самоизбегающих блужданиях, величина A(n) напрямую связана с энтропией цепочечной молекулы и поэтому встречается в теориях, относящихся к частоте некоторых метаболических реакций и реакций органического синтеза.
Несмотря на важность величины A(n), простая формула для нее неизвестна. Алгоритм для вычисления A(n) с временем, полиномиальным по n, пока не найден.
(0,1) о- | (1,1) —о | (0,1) о— | (1,1) -о | |
а | —О | О | о | |
(0,0) | (1,0) а | (0,0) b | (1,0) | |
(2,1) | ||||
О | ||||
О— | О | —о | ||
(0,0) | (1,0) | (2,0) | ||
С |
Рис. 9.3. Три разных самоизбегающих блуждания длины 4. Обратите внимание: блуждания (a) и (b) состоят из одинаковых множеств точек, но считаются разными, потому что они обходятся в разном порядке
|
(a) Покажите, что A(n) > 2n-1 для натуральных чисел n > 1.
(b) Предложите алгоритм, который получает число n и выводит A(n) как число в двоичной системе счисления с затратами пространства (то есть памяти), по- линомиальными по n. (Таким образом, время выполнения алгоритма может быть экспоненциальным при условии полиномиальных затрат пространства.
Также обратите внимание на то, что под полиномиальностью имеется в виду «полиномиальность по n», а не «полиномиальность по log n».
В самом деле, из (a) следует, что для записи значения A(n) потребуется не менее n - 1 битов, поэтому очевидно, что n - 1 является нижней границей для пространства, не- обходимого для получения правильного ответа.)Решение
Для начала рассмотрим часть (b). На первый взгляд перебор всех самоизбегающих блужданий кажется сложной задачей; поиск естественно представляется как рост цепочки, растущей из одного звена, с анализом возможных конфигураций и от- ступлениями в том случае, когда продолжить рост без самопересечений не удается. Все мы видели экранные заставки, которые рисуют подобные картинки, но точно сформулировать алгоритм будет непросто.
Итак, сделаем шаг назад; полиномиальное пространство — очень свободная граница, и мы можем сделать шаг в сторону «грубой силы». Допустим, вместо того, чтобы пытаться перебрать все самоизбегающие блуждания длины n, мы просто переберем все блуждания длины n, а затем проверим, какие из них окажутся само- избегающими. Преимущество такого решения в том, что пространство всех блуж- даний описывается намного проще, чем пространство самоизбегающих блужданий.
В самом деле, любое блуждание (p1, p2, ..., pn) для множества С точек сетки на плоскости может быть описано последовательностью выбираемых направлений. Каждый шаг от p. к p+1 может рассматриваться как перемещение в одном из четырех направлений: север, юг, восток или запад. Следовательно, любое блуж- дание длины n отображается на строку длины n - 1 в алфавите {Ж, S, E, W}. (Три блуждания на рис. 9.3 соответствуют строкам ENW, NES и EEN). Каждая такая строка соответствует блужданию длины n, но не все такие строки соответствуют самоизбегающим блужданиям: например, NESW возвращается к точке (0, 0).
Этот способ кодирования блужданий для части (b) вопроса можно использо- вать следующим образом. Используя счетчик по модулю 4, мы перебираем все строки длины n - 1 по алфавиту {Ж, S, E, W}, рассматривая этот алфавит в эквива- лентном виде {0, 1, 2, 3}.
Для каждой такой строки мы строим соответствующее блуждание и проверяем с полиномиальными затратами пространства, является ли оно самоизбегающим. Наконец, мы увеличиваем второй счетчик A (иници- ализируемый 0), если текущее блуждание является самоизбегающим. В конце алгоритма в A хранится значение A(n).Теперь мы можем ограничить пространство, используемое алгоритмом, сле- дующим образом. Первый счетчик, используемый для перебора строк, состоит из n - 1 позиции, каждая из которых занимает два бита (для четырех возможных значений). Второй счетчик, содержащий A, может увеличиваться не более 4n-1 раз, поэтому для него понадобится не более 2n битов. Наконец, полиномиальное про- странство используется для проверки того, является ли каждое сгенерированное блуждение самоизбегающим; но одно и то же пространство может использоваться для всех блужданий, поэтому необходимое пространство также является полино- миальным.
Описанная схема кодирования также помогает ответить на часть (a). Заметим, что все блуждания, которые могут быть закодированы с использованием только букв {Ж, E}, являются самоизбегающими, так как перемещение на плоскости осу- ществляется только вверх и вправо. Для этих двух букв существуют 2й-1 строки длины n - 1, поэтому существуют не менее 2n-1 самоизбегающих блужданий; дру- гими словами, A(n) > 2n-1.
(Ранее было показано, что наш метод кодирования также предоставляет верх- нюю границу, из которой немедленно следует, что A(n) < 4n-1.)
Упражнения
1. Рассмотрим частный случай задачи 3-SAT с кванторами, в котором булева фор- мула не содержит инвертированных переменных. А именно, пусть Ф(x1, ..., xn) — булева формула вида
Сj Л C2 Л ... Л Ck,
где каждое условие С. является дизъюнкцией трех литералов. Монотонность Ф означает, что каждый литерал в каждом условии состоит из неинвертированной переменной, то есть что каждый литерал равен х. для некоторого У, а не ⅞.
Монотонная задача QSAT определяется как задача принятия решенияв которой формула Ф является монотонной.
Сделайте одно из двух: (a) докажите, что монотонная задача QSAT является PSPACE-полной; или (b) предложите алгоритм для решения произвольных эк- земпляров монотонной задачи QSAT за время, полиномиальное по n. (Обратите внимание: в (b) целью является полиномиальное время, а не полиномиальное пространство.)
2. Рассмотрим следующую игру. Имеется множество географических назва- ний — например, названий столиц. Первый игрок называет столицу с страны, в которой находится компания; второй игрок должен выбрать город с', на- чинающийся с буквы, которой заканчивается c. Далее игроки попеременно выбирают города, начинающиеся с последней буквы предыдущего города. Проигрывает тот, кто не может назвать город, еще не встречавшийся ранее в игре. Например, в начале игры, проходящей в Венгрии, первый игрок го- ворит «Будапешт»; далее следует продолжение (например): «Токио, Оттава, Анкара, Амстердам, Москва.»
Конечно, игра помогает проверить знания географии, но даже с полным спи- ском мировых столиц возникает серьезная стратегическая задача. Какое слово выбрать следующим, чтобы попытаться загнать противника в тупик, в котором у него не будет хода?
Примечания и дополнительная литература 553
Чтобы выделить стратегический аспект, определим абстрактную версию игры, которая будет называться географической игрой на графе. Имеется направлен- ный граф G = (V, E) с начальным узлом 5
Еще по теме Упражнения с решениями Упражнение с решением 1:
- § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
- РЕШЕНИЕ
- РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
- ПРИНЯТИЕ РЕШЕНИЙ
- РЕШЕНИЯ КСУ
- Не избегайте принятия решений
- ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
- ЗАДАЧА: РЕШЕНИЕ
- Принять решение
- Управленческие решения
- Решение проблем
- КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
- Убеждения и решения
- Убеждения и решения
- НАЙДИТЕ РЕШЕНИЕ
- НАЧНИТЕ С ПРИНЯТИЯ РЕШЕНИЯ
- Получение информации и принятие решений
- Решение измениться
- Решение измениться