Том 6, серия 2, номер 1, 1999 г., Стр. 12-32
УДК 519.854.33
Е. Н. Гончаров, Ю. А. Кочетов
Поведение вероятностных жадных алгоритмов для многостадийной задачи размещения
Аннотация:
Проведено экспериментальное исследование вероятностных жадных алгоритмов и получены статистические оценки для следующих параметров: математического ожидания относительной погрешности, ее среднего квадратического отклонения, вероятности найти точное решение задачи и приближенное решение с относительной погрешностью не более одного процента. Показано, что относительная погрешность этих алгоритмов может быть сделана сколь угодно малой величиной. Приведено описание метода ветвей и границ, на каждой итерации которого применяются вероятностные жадные алгоритмы. Получены доверительные интервалы для вероятности найти точное решение задачи данным методом за несколько первых итераций.
Табл. 5, ил. 6, библиогр. 12.
Гончаров Е. Н. 1
Кочетов Ю. А. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
Статья поступила 30 октября 1998 г.
Исправленный вариант — 10 марта 1999 г.
