Введение
Алгоритм поиска или эвристический метод решения задач об удовлетворении ограничениям. В информатике алгоритм минимальных конфликтов — это алгоритм поиска или эвристический метод решения задач об удовлетворении ограничениям. При заданном начальном присваивании значений всем переменным задачи об удовлетворении ограничениям, алгоритм случайным образом выбирает переменную из множества переменных, имеющих конфликты, нарушающие одно или несколько её ограничений. Затем он присваивает этой переменной значение, которое минимизирует число конфликтов. Если существует более одного значения с минимальным числом конфликтов, он выбирает одно из них случайным образом. Этот процесс случайного выбора переменной и присваивания значения, минимизирующего конфликты, повторяется до тех пор, пока не будет найдено решение или не будет достигнуто заранее заданное максимальное количество итераций. Поскольку задачу об удовлетворении ограничениям можно интерпретировать как задачу локального поиска, когда всем переменным присвоены значения (так называемое полное состояние), алгоритм минимальных конфликтов можно рассматривать как эвристику восстановления, выбирающую состояние с минимальным числом конфликтов.
In computer science, the min conflicts algorithm is a search algorithm or heuristic method to solve constraint satisfaction problems. Given an initial assignment of values to all the variables of a constraint satisfaction problem, the algorithm randomly selects a variable from the set of variables with conflicts violating one or more of its constraints. Then it assigns to this variable the value that minimizes the number of conflicts. If there is more than one value with a minimum number of conflicts, it chooses one randomly. This process of random variable selection and min conflict value assignment is iterated until a solution is found or a pre selected maximum number of iterations is reached. Because a constraint satisfaction problem can be interpreted as a local search problem when all the variables have an assigned value (called a complete state), the min conflicts algorithm can be seen as a repair heuristic that chooses the state with the minimum number of conflicts.
История
Хотя искусственный интеллект и дискретная оптимизация изучали и использовали задачи удовлетворения ограничений на протяжении многих лет, алгоритмическая форма для решения больших задач CSP появилась только в начале 1990-х годов. Первоначально Марк Джонстон из Института космического телескопа искал способ планирования астрономических наблюдений на космическом телескопе Хаббл. В сотрудничестве с Хансом Мартином Адорфом из Европейского координационного центра космического телескопа он разработал нейронную сеть, способную решать упрощенную задачу о n ферзях (для 1024 ферзей). Стивен Минтон и Энди Филипс проанализировали алгоритм нейронной сети и выделили в нем два этапа: (1) начальное назначение с использованием жадного алгоритма и (2) этап минимизации конфликтов (впоследствии названный "минимизация конфликтов"). Статья была написана и представлена на AAAI 90; Филипп Лэрд предоставил математический анализ алгоритма. В дальнейшем Марк Джонстон и сотрудники STScI использовали метод минимизации конфликтов для планирования времени наблюдений астрономов на космическом телескопе Хаббл.
Пример
Алгоритм минимальных конфликтов решает задачу N королей, случайным образом выбирая столбец на шахматной доске для перемещения королевы. Алгоритм просматривает каждый возможный ход, оценивая количество конфликтов (число атакующих королей), возникающих в каждой клетке. Королева перемещается в клетку с минимальным количеством конфликтов, при равенстве вариантов выбор осуществляется случайным образом. Важно отметить, что количество конфликтов определяется каждым направлением, с которого королева может атаковать. Если две королевы атакуют в одном и том же направлении (по горизонтали или диагонали), конфликт учитывается только один раз. Также следует учитывать, что если перемещение королевы привело бы к увеличению числа конфликтов по сравнению с текущей позицией, королева не совершает ход. Следовательно, если королева находится в состоянии минимального конфликта, ей не требуется двигаться. Время работы этого алгоритма для решения задачи N королей не зависит от размера задачи. Этот алгоритм способен решить задачу с миллионом королей в среднем за 50 шагов. Это открытие и наблюдения послужили толчком к обширным исследованиям в 1990 году, положив начало изучению задач локального поиска и различий между простыми и сложными задачами. Задача N королей является простой для локального поиска, поскольку решения плотно распределены в пространстве состояний. Алгоритм также эффективен для сложных задач. Например, он был успешно применен для составления расписания наблюдений для космического телескопа Хаббл, сократив время планирования недели наблюдений с трех недель до примерно 10 минут.