Помогите с алгоритмом решения


Это сообщение отредактировал(а) Shadowlord - 18.1.2010, 18:48

Количество слоёв не лимитировано? начакльный и конечный слои не заданы?

Видимо да. Я так понял задание к примеру у меня есть материалы m1 m2 m3 m4...  и клеи k1 k2 k3  ...
нужно собрать пары  к примеру m1m2 m4m5 ...  так что бы затратить минимальное количество клеев, смотрю в сторону покрытия множеств ведь фактически у меня есть конечное множество М и семейство его подмножеств(наборы материалов которые может склеить один клей ).
Но что то дальше у меня дело пока не сдвинулось 

Не понял... так тебе надо минимальное количество клеев, позволяющих склеить любую пару материалов непосредственно, или минимальное количество клеев, позволяющих склеить любую пару материалов либо непосредственно, либо с одним или несколькими промежуточными материалами?
Это разные задачи...

Я думаю непосредственно пару материалов, то есть каждый с каждым  .
в результате получить вариант склейки, то есть пары и каким клеем они были склеены   

Это сообщение отредактировал(а) Shadowlord - 19.1.2010, 06:53

Появилась такая глупая идея, строим матрицу A размерностью m*k, где m число типов материалов а к число типов клеев.
aij=1, если kj может клеить mi и 0 если нет. Из а строим матрицу смежности графа где вершины это материалы а ребра это возможность склеить, при построение записываем куда нибудь используемые клей. Потом проверяем все ли вершины соединенны друг с другом, если да то можно склеить каждый материал  любым другим.
Вот только я не уверен что это всегда будет минимальное количество клеев, если только отсортировать клеи по количеству склеиваемых(по их убыванию)

Это сообщение отредактировал(а) Shadowlord - 19.1.2010, 09:25