Алгоритм Лас Вегаса для расстановки восьми ферзей

[Сурка]

Алгори́тм имита́ции о́тжига (англ. Simulated annealing) — общий алгоритмический метод решения задачи глобальной оптимизации, особенно дискретной и комбинаторной оптимизации. Один из примеров методов Монте-Карло.

Монте-Карло и Лас Вегас - это вероятностные алгоритмы. но разные.
а рекурсивный сам по себе...
так?

[Grag]

Сурка! Объясни мне, что значит рекурсивный алгоритм??? Рекурсивный вызов функции - это я понимаю! А уж по какому алгоритму работает функция - сам(а) отжигай!!!

[Сурка]

в данном случае

рекурсивный алгоритм решения помещает ферзя на первой клетке первой вертикали, а затем вызывая себя для того, чтобы поставить ферзя на вторую горизонталь. если в какой-то момент алгоритму не удается найти положения для очередного ферзя на очередной горизонтали, то алгоритм возвращается на предыдущий шаг и пробует другое размещение ферзя на предыдущей строке.

вот как-то так

[sabbathist]

Блин. так это поиск в глубину банальный.

[LeBron]

Не парьтесь вы, пишите Лас-Вегас (довольно доступное объяснение з Вики:

Допустим, у нас есть некий вероятностный алгоритм A, который с определенной вероятностью дает верный результат. Если существует возможность алгоритмически проверить результат алгоритма A на корректность (скажем, с помощью алгоритма K), то можно выполнять алгоритм A до тех пор, пока проверка не установит, что результат верен.

) и не заморачивайтесь рекурсией и всем остальным.

[Сурка]

Сообщение от sabbathist

Блин. так это поиск в глубину банальный.

это который рекурсивный?

Сообщение от LeBron

Не парьтесь вы, пишите Лас-Вегас и не заморачивайтесь рекурсией и всем остальным.

так я и не заморачиваюсь ) мне именно Лас Вегас нужен.

так нет ни у кого уже написанной программки?

[sabbathist]

Да, это поиск в глубину пишется рекурсией. Программки нет, но там несложно, поверьте)

[Сурка]

так мне же не поиск в глубину нужен, а Лас Вегас

[Сурка]

объясните мне, пожалуйста, что функция uniform делает?

Queens(result)
result содержит номера вертикалей для ферзей
с соответствующих горизонталей
возвращает 1 в случае успеха и 0 в случае неудачи
row=l
repeat
// ферзи уже расставлены в горизонталях l..row-l
spotsPossible=0
for i=l to 8 do
if клетка (row.i) атакована then
spotsPossible=spotsPossible+l
if uniform(l,spotsPossible)=l then
try=i
end if
end if
end for
if spotsPossible>0 then
result[row]=try
row=row+l
end if
return  (spotsPossible>0)

... Следующий оператор if выглядит несколько странно, но посмо-
трим, что происходит, если опустить первую горизонталь, на которой
не атакована ни одна клетка. На первой вертикали функция uniform
генерирует случайное число между 1 и 1, т.е. 1, поэтому переменная try
будет указывать на первую вертикаль. Во второй вертикали uniform
генерирует число между 1 и 2, которое с 50%-ной вероятностью будет
единицей и с 50%-ной вероятностью двойкой, поэтому вероятность то-
го, что новым значением переменной try станет двойка, равна 50%. В
третьей вертикали uniform генерирует число между 1 и 3; это число с
вероятностью 33% будет 1, и также с вероятностью 33% значение try
станет равно 3. Окончательно мы заключаем, что для каждой из сво-
бодных вертикалей вероятность быть опробованной на данном проходе
равна 1/spotsPossible.