Я натолкнулся на слайд (прикрепленный в конце), в котором упоминается метод восхождения на гору для решения проблемы 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