Таблица 5.1. Результаты применения различных алгоритмов CSP для решения разных задач. Слева направо показаны алгоритмы простого поиска с возвратами, поиска с возвратами на основе эвристической функции MRV, локального поиска с предварительной проверкой, локального поиска с предварительной проверкой на основе MRV и локального поиска с минимальными конфликтами. В каждой ячейке показано среднее количество проверок совместимости (за пять прогонов), которые потребовались для решения данной задачи; обратите внимание на то, что все эти числа, кроме двух, находящихся вверху справа, выражены в тысячах (К). Числа в круглых скобках показывают, что за назначенное количество проверок не было найдено ни одного ответа. Первой задачей является поиск раскраски в 4 цвета для 50 штатов США. Остальные задачи взяты из [56, табл. 1]. Во второй задаче по дочитывается общее количество проверок, необходимых для решения всех задач с п ферзями для л от 2 до 50. Третьей задачей является "головоломка с зеброй", которая описана в упр. 5.13. Последние две задачи представляют собой искусственные задачи, формируемые случайным образом (алгоритм с минимальными конфликтами к ним не применялся). Эти результаты показывают, что предварительная проверка на основе эвристической функции MRV является лучшим способом решения всех этих задач по сравнению с другими алгоритмами поиска с возвратами, но этот метод не всегда превосходит локальный поиск с минимальными конфликтами