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

Тема в разделе "Свободное общение", создана пользователем borik, 28 мар 2004.

Статус темы:
Закрыта.
  1. borik

    borik Гость

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

    Kernel Гость

    На сколько я помню для генереции 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.
     
  3. admin

    admin Well-Known Member

    Регистрация:
    8 авг 2003
    Сообщения:
    2.811
    Симпатии:
    0
    borik
    влом. для ответов на email зарегистрируцся и подпишись на тему.
     
Статус темы:
Закрыта.

Поделиться этой страницей