Проблема 8 королев | Вероятность достижения глобального минимума по алгоритму восхождения на холм
Я натолкнулся на слайд (прикрепленный в конце), в котором упоминается метод восхождения на гору для решения проблемы 8 ферзей. Чтобы подвести итог метода, он делает следующее:
Произвольно инициализируйте 8 ферзей в сетке и запишите начальную стоимость (т. Е. Количество смежных атак для 8 ферзей)
Переместите одну из королев, если вызванная стоимость ниже, и выберите ход, который дает наименьшую стоимость (локально).
Повторяйте шаг 2 до тех пор, пока никакие действия не приведут к снижению стоимости по сравнению с предыдущей.
На стр.15 слайда он далее прокомментировал эффективность алгоритма:
Случайно сгенерированные начальные состояния 8 королев...
14% времени это решает проблему
86% времени это застревает на местном минимуме
При успешном выполнении в среднем занимает всего 4 шага
И 3 в среднем, когда он застревает
Сомневаясь в цифрах (особенно в 14% от достижения минимума в мире), я попытался реализовать метод, описанный выше, и проверил фигуру с помощью моделирования. В конце я получил следующие цифры из моей симуляции:
Вероятность достижения глобального мин. = 18,6%
Среднее количество шагов для каждой симуляции = 4.252
Средняя стоимость в конце каждого моделирования = 1,194
Приведенные выше цифры получены из 500 симуляций. Видимо, цифры отличаются от предложенных на слайде. Вероятно, мои 18,6% довольно сильно отличаются от 14%, и мои средние шаги для каждой симуляции равны 4,252, это отличается от утверждения, что "в среднем делает только 4 шага в случае успеха и 3 в среднем, когда застревает"
Теперь я не понимаю, какой набор цифр является правдой (мой и тот, который предложен на слайде). Кто-нибудь, кто делал подобные эксперименты раньше, может дать мне какие-нибудь предложения? Спасибо
аппендикс
Для более подробной информации о моей реализации, вы можете обратиться к моему исходному коду: https://github.com/riven314/COMP7404_ComputationalIntelligence_MachineLearning/blob/master/nQueens_Problem/nQueens_GreedySim.py
Источник слайда: https://courses.cs.washington.edu/courses/csep573/12au/lectures/04-lsearch.pdf