Cтраница 2
Альфа-бета алгоритм является эффективной, реализацией минимаксного принципа. Эффективность альфа-бета алгоритма зависит от порядка, в котором просматриваются варианты ходов. Применение альфа-бета алгоритма приводит, в лучшем случае, к уменьшению коэффициента ветвления дерева поиска, соответствующему извлечению из него квадратного корня. [16]
Принцип поиска сначала в глубину, применяемый к данному дереву поиска, сам по себе не определяет последовательность, в которой строятся вычисления. Эта последовательность регулируется порядком выбора процедур, отвечающих на вызовы. Всякое правило, задающее указанный порядок, называется правилом поиска, поскольку оно определяет направление поиска, избираемое интерпретатором в каждой точке ветвления дерева поиска. Согласно стандартному правилу поиска, процедуры, отвечающие на вызов, выбираются в соответствии с их порядком вхождения в текст программы. [17]
В программах П1 и П2 реализован метод ветвей и границ с использованием оригинальных нижних и верхних границ решения. При решении задач с помощью П2 в качестве КО используется минимизация суммарного времени запаздывания, которое будет характеризовать соответствующий вариант расписания. Допускается задание таких видов останова ВП: по величине е, по времени счета, по числу анализируемых подзадач, по максимальному номеру подзадачи, по тому, пуст ли список активных подзадач. Пользователь может различными способами влиять на процесс ветвления дерева вариантов решения задачи. [18]
Каждую из вершин, соответствующих Qi и Q2, можно использовать для дальнейшего ветвления. Конечная вершина отвечает только одному решению. Сумма подмножеств всех висячих вершин в процессе ветвления равна Q. Название метода границ и ветвей связано с ветвлением дерева вариантов и определением нижних границ для каждой его вершины. [19]
Предикатный информационный граф можно рассматривать как обобщение контактных схем и АДВ-модели, причем от контактных схем заимствована структура в виде сети с нагрузкой ребер функциями и использование функций проводимости, а от АДВ-модели - способ введения сложности сети. Кроме того, вводится алгоритм обхода сети, похожий на алгоритм разметки графа [51, 61], который можно рассматривать как соответствующий сети алгоритм поиска. Причем в каждой вершине сети, до которой на некотором запросе х дошел алгоритм поиска, каждое из ребер, исходящее из этой вершины, задает возможное направление поиска, и если на этом запросе х значение предиката, соответствующего ребру, равно 1, то в направлении данного ребра поиск продолжается, а если равно 0, то по этому направлению поиск прекращается. Таким образом, из одной вершины сети может возникнуть сразу несколько направлений, по которым поиск продолжается. Но в задачах поиска часто встречается ситуация, когда из нескольких направлений поиска выбирается точно одно, например, так как это происходит в вершине ветвления алгебраического дерева вычислений, когда в зависимости от результата сравнения выбирается одно из двух направлений движения. В таких случаях гораздо удобнее приписать вершине функцию-переключатель и в зависимости от ее значения на запросе выбрать то направление, на которое указывает значение переключателя. [20]
Предикатный информационный граф можно рассматривать как обобщение контактных схем и АДВ-модели, причем от контактных схем заимствована структура в виде сети с нагрузкой ребер функциями и использование функций проводимости, а от АДВ-модели - способ введения сложности сети. Кроме того, вводится алгоритм обхода сети, похожий на алгоритм разметки графа [51, 61], который можно рассматривать как соответствующий сети алгоритм поиска. Причем в каждой вершине сети, до которой на некотором запросе х дошел алгоритм поиска, каждое из ребер, исходящее из этой вершины, задает возможное направление поиска, и если на этом запросе х значение предиката, соответствующего ребру, равно 1, то в направлении данного ребра поиск продол жнется, а если равно 0, то по этому направлению поиск прекращается. Таким образом, из одной вершины сети может возникнуть сразу несколько направлений, по которым поиск продолжается. Но в задачах поиска часто встречается ситуация, когда из нескольких направлений поиска выбирается точно одно, например, так как это происходит в вершине ветвления алгебраического дерева вычислений, когда в зависимости от результата сравнения выбирается одно из двух направлений движения. В таких случаях гораздо удобнее приписать вершине функцию-переключатель и в зависимости от ее значения на запросе выбрать то направление, на которое указывает значение переключателя. [21]