Алгоритм взаимозаменяемости
В информатике — алгоритм взаимозаменяемости это метод, используемый для более эффективного решения проблем удовлетворения ограничений (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]
- Повторите для каждого значения w, соответствующего v:
- Повторите для каждой соседней переменной W:
К -алгоритм взаимозаменяемости
[ редактировать ]Алгоритм можно использовать для явного поиска решений проблемы удовлетворения ограничений. Алгоритм также можно запустить на k шагов в качестве препроцессора, чтобы упростить последующий поиск с возвратом.
Находит k-взаимозаменяемые значения в CSP. Повторите для каждой переменной:
- Постройте дерево дискриминации:
- Повторите для каждого значения v:
- Повторите для каждого ( k − 1) набора переменных.
- Повторите эти действия для каждого ( k − 1)-кортежа значений w , которые вместе с v составляют решение подзадачи, индуцированной W :
- Перейдите в, если есть, постройте, если нет, узел дерева дискриминации, соответствующий w|W [2]
- Повторите эти действия для каждого ( k − 1)-кортежа значений w , которые вместе с v составляют решение подзадачи, индуцированной W :
- Повторите для каждого ( k − 1) набора переменных.
Анализ сложности
[ редактировать ]В случае алгоритма взаимозаменяемости соседей, если мы назначим каждому циклу наихудший случай. Тогда для n переменных, которые имеют не более d значений для переменной, мы имеем границу: .
Аналогично, анализ сложности алгоритма k -взаимозаменяемости для наихудшего случая , с -кортежи переменных и , для -кортежи значений, то граница равна: .
Пример
[ редактировать ]
На рисунке показан простой пример раскраски графа с цветами в качестве вершин, так что никакие две вершины, соединенные ребром, не имеют одинакового цвета. Показаны доступные цвета в каждой вершине. Желтый, зеленый, коричневый, красный, синий и розовый цвета представляют вершину Y и по определению полностью взаимозаменяемы. Например, если заменить зеленый цвет на бордовый в растворе оранжевый|X (оранжевый вместо X), зеленый|Y даст другое решение.
Приложения
[ редактировать ]В компьютерных науках алгоритм взаимозаменяемости широко используется в области искусственного интеллекта , задач раскраски графов , структур абстракции и адаптации решений. [2] [4] [5] [6] [7] [8] [9]
Ссылки
[ редактировать ]- ^ Белаид Бенаму и Мохамед Реда Саиди «Рассуждение на основе доминирования в сетях с бинарными ограничениями «не равно»» , Лаборатория информационных и системных наук (LSIS), Центр математики и информатики, Франция.
- ^ Перейти обратно: а б с д и ж г час Фрейдер, EC: Устранение взаимозаменяемых ценностей в проблемах удовлетворения ограничений . В: В учеб. AAAI-91, Анахайм, Калифорния (1991) 227–233.
- ^ Ассеф Хмейсс и Лахдар Саис «О взаимозаменяемости соседей в CSP» , Университет Артруа, ФранкА пока вы се.
- ^ Хазельбок, А.: Использование взаимозаменяемости в задачах удовлетворения ограничений. В Proc. 13-го IJCAI (1993) 282–287
- ^ Вайгель Р., Фалтингс Б.: Составление задач удовлетворения ограничений. Искусственный интеллект 115 (1999) 257–289.
- ^ Шуейри, BY: Методы абстракции для распределения ресурсов. Кандидатская диссертация, Кандидатская диссертация EPFL № 1292 (1994).
- ^ Вейгель Р., Фалтингс Б.: Взаимозаменяемость для адаптации к случаю в конфигурации.Проблемы. В материалах весеннего симпозиума AAAI98 по мультимодальному рассуждению, Стэнфорд, Калифорния, TR SS-98-04. (1998)
- ^ Неагу, Н., Фалтингс, Б.: Использование взаимозаменяемости для адаптации к случаю. В Proc. 4-й ICCBR01 (2001 г.)
- ^ Полная динамическая заменяемость с помощью SAT-кодирования, Стивен Прествич, Центр вычислений ограничений Корка, факультет компьютерных наук, Университетский колледж, Корк, Ирландия.