Имитация отжига и Yahtzee!

Я взял вызов программирования и нашел Yahtzee! Проблема, которую я упрощу:

  • Есть 13 категорий очков
  • Есть 13 бросков игроком (включая игру)
  • Каждый рулон должен соответствовать отдельной категории
  • Цель состоит в том, чтобы найти максимальное количество очков за игру (оптимальное размещение бросков по категориям); оценка (игра) возвращает счет за игру

Грубое принуждение, чтобы найти максимальный игровой счет, требует 13! (= 6,227,020,800) оценка () звонков.

Я выбираю имитацию отжига, чтобы быстрее найти что-то близкое к наивысшему баллу. Хотя и не детерминированный, но достаточно хороший. У меня есть список из 13 бросков из 5 кубиков, например:

((1,2,3,4,5) #1
 (1,2,6,3,4),#2
    ...
 (1,4,3,2,2) #13
)

И игра (1,5,6,7,2,3,4,8,9,10,13,12,11) Переданный в Score() возвращает счет для перестановки этой игры.

Как выбрать хорошее "соседнее государство"? Для случайного перезапуска я могу просто выбрать случайную перестановку чисел nos. 1-13, поместите их в вектор и оцените их. В задаче коммивояжера приведем пример хорошего соседнего государства:

"Соседи некоторой конкретной перестановки - это перестановки, которые создаются, например, путем обмена парой соседних городов".

У меня плохое предчувствие просто поменять местами две случайные позиции, вот так:

(1,5,6,7, 2 , 3,4,8,9,10, 13, 12,11) # switch 2 and 13
(1,5,6,7, 13, 3,4,8,9,10, 2 , 12,11) # now score this one

Но у меня нет доказательств, и я не знаю, как выбрать хорошее соседнее государство. У кого-нибудь есть идеи, как выбрать хорошие соседние штаты?

Источник

2 ответа

Решение

Стратегия парного обмена не кажется мне плохой. Это, безусловно, посещает - в теории - все перестановки. Главное, я думаю, это посмотреть, действительно ли "соседи" "похожи" в вашем случае, т. Е. Если два места размещения, которые отличаются только парным обменом, довольно схожи по количеству очков. Я не могу решить это, потому что правила вашей "игры" мне не понятны.

Источник

Хитрость заключается в том, чтобы иметь несколько типов ходов. Поэтому предлагайте SA как маленькие, объединяющие движения, так и большие, разнообразные движения. Но у вас больше шансов предложить первое. Маленькие ходы просты: измените 1 или переключите 2.

Взгляните на мой пример составления списков медсестер в планировщике слюней. Его открытый исходный код в Java.

Источник
Другие вопросы по тегам