Жадные алгоритмы распределения ресурсов. Списки и ограниченный перебор
Спесивцев А.В.
Малип 1993
Изучаются три задачи распределения ресурсов - общая, минимаксная и максиминная. Во всех задачах требуется оптимально распределить по потребителям множество ресурсов. Данные разновидности задачи достаточно часто встречаются в вычислительной технике, экономике, экологии, военном деле и других областях. Показывается, что задача распределения ресурсов является NP-трудной. Вследствие этого для ее решения используются приближенные алгоритмы с априорной оценкой погрешности. для приближенного решения задачи предлагаются алгоритмы списковые и ограниченного перебора. Исследование алгоритмо проводится в двух случаях: худшем и среднем. В результате анализа в худшем случае предлагается подход для построения алгоитма, позволяющего решить задачу с любой наперед заданной погрешностью е0. Определяется средняя погрешность спискового алгоритма. Предлагаемый приближенный подход используется для решения задач размещения наборов данных, распределения потоков заявок, целераспределения, обеспечения надежности, защиты информации и др. Для научных работников, занятых проблемами комбинаторной оптимизации, может быть полезна аспирантам и студентам, специализирующимся по прикладной математике Обо всём этом и не только в книге Жадные алгоритмы распределения ресурсов (Александр Спесивцев)
