4446
правок
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
Строка 1: | Строка 1: | ||
== Ключевые слова и синонимы == | == Ключевые слова и синонимы == | ||
Буферизация | |||
== Постановка задачи == | == Постановка задачи == | ||
Строка 19: | Строка 19: | ||
'''Жадный алгоритм.''' | '''Жадный алгоритм.''' | ||
При поступлении пакета стоимостью v(p): | При поступлении пакета стоимостью v(p): | ||
1. Если в буфере имеется свободное место, принять пакет p. | 1. Если в буфере имеется свободное место, принять пакет p. | ||
2. В противном случае отбросить (вытеснить) пакет | 2. В противном случае отбросить (вытеснить) пакет p', имеющий минимальную стоимость среди всех пакетов буфера и p. Если <math>p' \ne p</math>, принять p. | ||
Рисунок 1. Естественный жадный алгоритм | Рисунок 1. Естественный жадный алгоритм | ||
0. Вытеснить (отбросить) первый пакет | 0. Вытеснить (отбросить) первый пакет p' согласно порядку FIFO, такой, что <math>v(p') \le v(p) / \beta</math>, если таковой существует ''(p вытесняет p')''. | ||
Рисунок 2. Дополнительное правило для естественного жадного алгоритма | Рисунок 2. Дополнительное правило для естественного жадного алгоритма | ||
0'. Найти первый (т. е. ближайший к началу буфера) пакет | 0'. Найти первый (т. е. ближайший к началу буфера) пакет p', такой, что его стоимость ниже <math>v(p) / \beta</math> и не выше стоимости пакета, следующего за p' в буфере (если таковой существует). Отбросить найденный пакет ''(p вытесняет p')''. | ||
Рисунок 3. Модифицированный жадный алгоритм с вытеснением | Рисунок 3. Модифицированный жадный алгоритм с вытеснением | ||
В работе [7] показано, что при условии | В работе [7] показано, что при условии <math>\beta = 15</math> коэффициент конкурентоспособности жадного алгоритма с вытеснением (PG) составляет 1,983. Довольно сложный анализ выполняется при помощи присваивания стоимостей пакетов, обслуживаемых оффлайновым алгоритмом, пакетам, обслуживаемым алгоритмом PG. | ||
Нижняя граница для этой задачи, равная 5/4, была доказана в [9]. Она была улучшена до | Нижняя граница для этой задачи, равная 5/4, была доказана в [9]. Она была улучшена до <math>\sqrt{2}</math> в работе [2] и затем до 1,419 в [7]. | ||
== Основные результаты == | == Основные результаты == | ||
Модификацию алгоритма PG предложили Бансал, Флейшер, Кимбрел, Мадьян, Шибер и Свириденко [3]. В этой версии правило 0 заменено правилом | Модификацию алгоритма PG предложили Бансал, Флейшер, Кимбрел, Мадьян, Шибер и Свириденко [3]. В этой версии правило 0 заменено правилом 0'. | ||
Таким образом, изменение по сравнению с исходным алгоритмом PG заключается в том, что модифицированный алгоритм находит | Таким образом, изменение по сравнению с исходным алгоритмом PG заключается в том, что модифицированный алгоритм находит «локально оптимальный» пакет для исключения. Обозначим модифицированный жадный алгоритм с вытеснением как MPG. | ||
правок