Бесконечный цикл в алгоритме итеративного улучшения - PullRequest
Новая
       15

Бесконечный цикл в алгоритме итеративного улучшения

0 голосов
/ 27 октября 2018

Я решаю проблему N-Queen и сталкиваюсь с проблемой, когда N = 8.Когда N = 8, алгоритм застревает в бесконечном цикле.К сожалению, я не могу поделиться своим кодом с вами из-за обязательства, которое я подписал, но я надеюсь, что смогу прояснить это.Давайте возьмем следующую конфигурацию: 

. 0 1 2 3 4 5
0 - - - - - Q
1 - - - Q - -
2 - Q - - - -
3 - - - - Q -
4 - - Q - - -
5 - - - - - Q

Мой код возьмет случайную строку и вычислит угрозы в каждой ячейке и переместит ферзя в ячейку минимальной угрозы.В этом случае строки 1, 2, 3 и 4 не могут быть изменены, поскольку ферзь находится в самой нижней ячейке с резьбой.строки 0 и 1 могут переместиться в крайнее левое положение, но они все равно будут лечить друг друга.Что заставит алгоритм застрять в бесконечном цикле.

1 Ответ

0 голосов
/ 29 октября 2018

Без публикации какого-либо кода или подробного алгоритма у вас действительно не будет вопроса solid Stack Overflow. Однако я рассматриваю ту часть, в которой мы можем помочь: ваш общий подход к распространенным способам исследования пространства поиска. Похоже, это проблема с неправильно выполненным возвратом.

Я вижу две проблемы:

  1. "... нельзя изменить, поскольку ферзь находится в самой нижней ячейке с угрозами". Это кажется искусственным ограничением вашего алгоритма, что приводит к невозможности решения проблемы. Вам нужно вырвать его из навязанного им логического недостатка.
  2. "... заставить алгоритм застрять в бесконечном цикле." Это простая ошибка при обходе вашего пространства поиска. Когда вы достигнете нижнего ряда и не сможете решить проблему, вам нужно вернуться к предыдущей точке выбора и перейти к следующей в наборе непроверенных альтернатив. Вы не правильно сохранили этот набор, поскольку ваша программа возвращается к ранее отклоненному выбору.

Надеюсь, это поможет.

...