Списочное планирование: различия между версиями

Перейти к навигации Перейти к поиску
м
(Новая страница: «Ключевые слова и синонимы Планирование в режиме онлайн на идентичных машинах == Постано…»)
 
Строка 3: Строка 3:


== Постановка задачи ==
== Постановка задачи ==
Статья Рональда Грэма [ ] была опубликована в шестидесятых. На протяжении многих лет она служила типичным примером онлайновых алгоритмов (хотя исходный алгоритм был разработан как простая эвристика аппроксимации). В ней рассматривалась следующая базовая формулировка задачи.
Статья Рональда Грэма [8] была опубликована в шестидесятых. На протяжении многих лет она служила типичным примером онлайновых алгоритмов (хотя исходный алгоритм был разработан как простая эвристика аппроксимации). В ней рассматривалась следующая базовая формулировка задачи.
   
   


Строка 9: Строка 9:




Если задания подаются одно за другим, и каждое задание по очереди должно быть назначено машине без какого-либо представления о будущих заданиях, такая задача называется онлайновой. Онлайновые алгоритмы обычно оцениваются с использованием (абсолютного) коэффициента конкурентоспособности, который аналогичен коэффициенту аппроксимации одноименных алгоритмов. Для алгоритма A мы обозначаем его стоимость также как A. Стоимость оптимального оффлайнового алгоритма, который знает всю последовательность заданий, обозначается как OPT. Коэффициентом конкурентоспособности алгоритма A является инфимум R > 1, такой, что для любых входных данных A < R OPT.
Если задания подаются одно за другим, и каждое задание по очереди должно быть назначено машине без какого-либо представления о будущих заданиях, такая задача называется онлайновой. Онлайновые алгоритмы обычно оцениваются с использованием (абсолютного) ''коэффициента конкурентоспособности'', который аналогичен ''коэффициенту аппроксимации'' одноименных алгоритмов. Для алгоритма <math>\mathcal{A}</math> мы обозначаем его стоимость также как <math>\mathcal{A}</math>. Стоимость оптимального оффлайнового алгоритма, который знает всю последовательность заданий, обозначается как OPT. Коэффициентом конкурентоспособности алгоритма <math>\mathcal{A}</math> является инфимум <math>\mathcal{R} \ge 1</math>, такой, что для любых входных данных <math>\mathcal{A} \le \mathcal{R} \cdot OPT</math>.


== Основные результаты ==
== Основные результаты ==
4431

правка

Навигация