Расстановка ферзей

  • Автор темы borik
  • Дата начала
Статус
Закрыто для дальнейших ответов.
B

borik

#1
Гаспада. Задачка весьма известная.
Вопрос не совсем в ее решении. Суть в том, чтобы написать ее для решения на кластере.
Короче говоря, как ее разделить на несколько подзадач?
Какие именно части отсылать разным узлам.
Насколько я понимаю, будет один основной, собирающий общитанную инфу. А вот остальные - будут решать. Но что решать-то? Что именно давать им на просчет. Более общую и так же ее разделять? Или сразу мелкие задачки. Тогда как их собрать потом в одно решение.
Вопрос опять же в эффективности. Можно ли сделать так, чтобы одна мелкая задача не решалась на нескольких узлах.
Если не влом, то ответ бросьте на мыло: forapp@yandex.ru
 
K

Kernel

#2
На сколько я помню для генереции 1го решения её сложность то ли N, то ли N log N ... и нахрена тут кластер??? Они данными обмениватся будут дольше!
Так что уточни что точно надо:
1 Нахождение 1-ой фиксированной расстановки для произвольной доски(сложность N)
2 Нахождение 1-ой произвольной расстановки для произвольной доски(сложность по моему все-таки N log N, хотя может даже и N (не помню точно))
3 Нахождение всех расстановок ... даже не привязаваясь к вопросам оптимизационных ограниченй весь возможный спектр состоянии можно задать 8 числами (первое от 0 до 63 включительно, второе от 0 до 62 и т.д.) вот по этому набору ты и выдаёшь мелким кластерам область для поиска ... соответсвенно при сборе решений кластер присылает хосту все найденные решения в том же виде ... можно для простоты собрать их в одно большое число (если не лень писать математику больших чисел) R=a0+a1*64+a2*64*63+a3*64*63*62 ... +a7*64*63*62*61*60*59*58
и задавать область поиска как диапазон R1 .. R2.
 
Статус
Закрыто для дальнейших ответов.