алгоритмам. Действительно,
алгоритмам. Действительно, пусть все решения имеют длину N, тогда исследовать требуется порядка ?S1?*?S2?*...*?SN? узлов дерева. Если значение Si ограничено некоторой константой С, то получаем порядка СN узлов.
2.1.2. Задача о расстановке ферзей
На шахматной доске N*N требуется расставить N ферзей таким образом, чтобы ни один ферзь не атаковал другого.
Примечание. Трудно найти книгу по информатике, в которой не рассматривалась бы эта задача. Нам трудно избежать этой участи, ибо нет лучшей задачи для первоначального ознакомления со схемой решения переборных задач. Приведем краткое описание материала в том виде, в котором он излагается на занятии.
Отметим следующее. Все возможные способы расстановки ферзей - СNN^2 (около 4,4*109 для N=8). Каждый столбец содержит самое большее одного ферзя, что дает только NN расстановок (1,7*107 для N=8). Никакие два ферзя нельзя поставить в одну строку, а поэтому, для того чтобы вектор (а1, а2, ..., aN) был решением, он должен быть перестановкой элементов
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
