<<
>>

Упражнения с решениями Упражнение с решением 1

Самоизбегающие блуждания изучаются в области статистической физики; их мож- но определить следующим образом. Пусть £ — множество всех точек R2 с цело- численными координатами (своего рода «сетка» на плоскости).
Самоизбегающее блуждание Wдлины n представляет собой последовательность точек (pl,p2, ■■■, pn) из £, для которых

(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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Упражнения с решениями Упражнение с решением 1:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
  13. Убеждения и решения
  14. Убеждения и решения
  15. НАЙДИТЕ РЕШЕНИЕ
  16. НАЧНИТЕ С ПРИНЯТИЯ РЕШЕНИЯ
  17. Получение информации и принятие решений
  18. Решение измениться
  19. Решение измениться