Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения

Проведено экспериментальное исследование вероятностных жадных алгоритмов и получены статистические оценки для следующих параметров: математического ожидания относительной погрешности, ее среднего квадратического отклонения, вероятности найти точное решение задачи и приближенное решение с относительной погрешностью не более одного процента. Показано, что относительная погрешность этих алгоритмов может быть сделана сколь угодно малой величиной. Приведено описание метода ветвей и границ, на каждой итерации которого применяются вероятностные жадные алгоритмы. Получены доверительные интервалы для вероятности найти точное решение задачи данным методом за несколько первых итераций. Табл. 5, ил. 6, библиогр. 12.