Алгоритм взаимозаменяемости

В информатике алгоритм взаимозаменяемости — это метод, используемый для более эффективного решения задач удовлетворения ограничений (CSP). CSP — это математическая задача, в которой объекты, представленные переменными, подчиняются ограничениям на значения этих переменных; цель CSP — назначить переменным значения, которые соответствуют ограничениям. Если две переменные A и B в CSP можно поменять местами (то есть A заменить на B , а B заменить на A ) без изменения сути проблемы или ее решений, то A и B являются взаимозаменяемыми переменными. Взаимозаменяемые переменные представляют симметрию CSP, и, используя эту симметрию, можно сократить пространство поиска решений задачи CSP. Например, если были испробованы решения с A = 1 и B = 2, то с помощью симметрии взаимозаменяемости нет необходимости исследовать решения с B = 1 и A = 2.

Концепция взаимозаменяемости и алгоритм взаимозаменяемости в задачах удовлетворения ограничений были впервые введены Юджином Фройдером в 1991 году. ^{[1] [2]} Алгоритм взаимозаменяемости сокращает пространство поиска алгоритмов поиска с возвратом , тем самым повышая эффективность NP-полных задач CSP. ^[3]

Полностью взаимозаменяемы

Значение a для переменной v полностью взаимозаменяемо со значением b тогда и только тогда, когда каждое решение, в котором v = a, остается решением, когда b заменяется на a и наоборот. ^[2]

Взаимозаменяемый район

Значение a для переменной v является окрестностно взаимозаменяемым со значением b тогда и только тогда, когда для каждого ограничения на v значения, совместимые с v = a, являются в точности теми, которые совместимы с v = b. ^[2]

Полностью заменяемый

Значение a для переменной v полностью заменяемо значением b тогда и только тогда, когда каждое решение, в котором v = a, остается решением при замене b на a (но не обязательно наоборот). ^[2]

Динамически взаимозаменяемый

Значение a для переменной v динамически взаимозаменяемо для b относительно набора A назначений переменных тогда и только тогда, когда они полностью взаимозаменяемы в подзадаче, индуцированной A. ^[2]

Находит соседние взаимозаменяемые значения в CSP. Повторите для каждой переменной:

Постройте дерево дискриминации:

Повторите для каждого значения v:

Повторите для каждой соседней переменной W:

Повторите для каждого значения w, соответствующего v:

Перейти к , если присутствует, построить, если нет, узел дерева дискриминации, соответствующий w|W ^[2]

Алгоритм может быть использован для явного поиска решений проблемы удовлетворения ограничений. Алгоритм также может быть запущен для k шагов в качестве препроцессора для упрощения последующего поиска с возвратом.

Находит k-взаимозаменяемых значений в CSP. Повторите для каждой переменной:

Постройте дерево дискриминации:

Повторите для каждого значения v:

Повторите для каждого ( k − 1)-кортежа переменных

Повторите для каждого ( k − 1)-кортежа значений w , которые вместе с v составляют решение подзадачи, вызванной W :

Перейти к , если присутствует, построить, если нет, узел дерева дискриминации, соответствующий w|W ^[2]

В случае алгоритма взаимозаменяемых соседей, если мы назначаем наихудшую границу для каждого цикла. Тогда для n переменных, которые имеют не более d значений для переменной, то мы имеем границу : .${\displaystyle O(nd(nl)*d)=O(n^{2}d^{2})}$

Аналогично, анализ сложности алгоритма k -взаимозаменяемости для наихудшего случая , с -кортежами переменных и , для -кортежей значений, тогда граница будет: .${\displaystyle O(n^{k-1})}$${\displaystyle (k-1)}$${\displaystyle d^{k-1}}$${\displaystyle (k-1)}$${\displaystyle O(ndn^{kl}d^{k-1})=O(n^{k}d^{k})}$

На рисунке показан простой пример раскраски графа с цветами в качестве вершин, так что никакие две вершины, соединенные ребром, не имеют одинакового цвета. Показаны доступные цвета в каждой вершине. Цвета желтый, зеленый, коричневый, красный, синий, розовый представляют вершину Y и полностью взаимозаменяемы по определению. Например, замена бордового на зеленый в решении orange|X (оранжевый на X), green|Y даст другое решение.

В компьютерных науках алгоритм взаимозаменяемости широко используется в областях искусственного интеллекта , задач раскраски графов , фреймворков абстракции и адаптации решений. ^{[2] [4] [5] [6] [7] [8] [9]}