4446
правок
Списочное планирование: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Постановка задачи
Irina (обсуждение | вклад) (Новая страница: «Ключевые слова и синонимы Планирование в режиме онлайн на идентичных машинах == Постано…») |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Статья Рональда Грэма [ ] была опубликована в шестидесятых. На протяжении многих лет она служила типичным примером онлайновых алгоритмов (хотя исходный алгоритм был разработан как простая эвристика аппроксимации). В ней рассматривалась следующая базовая формулировка задачи. | Статья Рональда Грэма [8] была опубликована в шестидесятых. На протяжении многих лет она служила типичным примером онлайновых алгоритмов (хотя исходный алгоритм был разработан как простая эвристика аппроксимации). В ней рассматривалась следующая базовая формулировка задачи. | ||
| Строка 9: | Строка 9: | ||
Если задания подаются одно за другим, и каждое задание по очереди должно быть назначено машине без какого-либо представления о будущих заданиях, такая задача называется онлайновой. Онлайновые алгоритмы обычно оцениваются с использованием (абсолютного) коэффициента конкурентоспособности, который аналогичен коэффициенту аппроксимации одноименных алгоритмов. Для алгоритма A мы обозначаем его стоимость также как A. Стоимость оптимального оффлайнового алгоритма, который знает всю последовательность заданий, обозначается как OPT. Коэффициентом конкурентоспособности алгоритма A является инфимум R > | Если задания подаются одно за другим, и каждое задание по очереди должно быть назначено машине без какого-либо представления о будущих заданиях, такая задача называется онлайновой. Онлайновые алгоритмы обычно оцениваются с использованием (абсолютного) ''коэффициента конкурентоспособности'', который аналогичен ''коэффициенту аппроксимации'' одноименных алгоритмов. Для алгоритма <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>. | ||
== Основные результаты == | == Основные результаты == | ||