Задача о k официантах (The k-server Problem) Алгоритмы обрабатывающие вход по мере поступления Козлов Вадим гр.3539 6 октября 2005 г.

Презентация:



Advertisements
Похожие презентации
Параллельность прямых, прямой и плоскости Определение Две прямые в пространстве называются параллельными, если они лежат в одной плоскости и не пересекаются.
Advertisements

Свойства функции. Функция y=f(x), x X называется чётной, если для любого х из множества Х выполняется равенство: f(-x)=f(x) График чётной функции симметричен.
Определение Лемма Признак перпендикулярности прямой и плоскости Признак перпендикулярности прямой и плоскости Теорема 1 Теорема 2 Теорема о прямой перпендикулярной.
Лектор Пахомова Е.Г г. Математический анализ Раздел: Интегрирование ФНП Тема: Двойной интеграл (определение, свойства, вычисление)
Свойства функций Область определения, множество значений, четность, нечетность, периодичность.
Математические методы и модели организации операций Задачи линейного программирования.
Класс NP и NP-полные задачи. NP-полнота задачи выполнимости Задача выполнимости булевой функции: Вход: булева функция, заданная формулой Требуется определить,
Линейное программирование Задача теории расписаний.
Свойства функции. Определение 1 Функцию у=f(x) называют возрастающей на множестве Х D(f), если для любых точек х 1 и х 2 множества Х, таких что х 1
Свойства функции Алгебра 10 класс Урок – лекция Харитоненко Н.В. МОУ СОШ 3 с.Александров Гай.
Свойства функций Область определения, множество значений, четность, нечетность, периодичность.
Глава II. Векторная алгебра. Элементы теории линейных пространств и линейных операторов Раздел математики, в котором изучаются свойства операций над векторами,
Свойства функций Свойства функций Выполнили: Царук Ксения Быкова Ксения Проверила: Сальманова Наталья Ивановна.
{ изоморфизм графов - подграф - планарный и плоский графы - укладка плоских графов - маршруты, связность и компоненты - метрические характеристики - Эйлеровы.
Взаимное расположение прямых и плоскостей 10 класс.
Свойства функций. 1)Возрастание и убывание функций. ! Функцию у = f (x) называют возрастающей на множестве Х D (f), если для любых точек х 1.
Точка х 0 называется точкой максимума функции f(x),, если существует такая окрестность точки x 0, что для всех х х 0 из этой окрестности выполняется неравенство.
Лектор Пахомова Е.Г г. Математический анализ Раздел: Интегрирование ФНП Тема: Тройной интеграл.
Свойства линейных операций над матрицами Свойства линейных операций над векторами.
Приближенные схемы Задачи теории расписаний. Полиномиальная приближенная схема (PTAS) Семейство приближенных алгоритмов для задачи Π, {A ε } ε называется.
Транксрипт:

Задача о k официантах (The k-server Problem) Алгоритмы обрабатывающие вход по мере поступления Козлов Вадим гр октября 2005 г.

2 Содержание 1. Вступление и постановка задачи 2. Work-Function алгоритм 3. Главные результаты теории

Вступление Постановка задачи

4 The k-server Problem Постановка задачи В некотором метрическом пространстве k официантов располагаются в конкретных точках Заказы официантам происходят от столиков (точек в пространстве) обслуживаются немедленно: передвижением какого-то официанта в точку заказа Последовательность заказов, где точка в M, конечна, но за ранее не известна Требуется online алгоритм приводящий к минимизации суммарных передвижений

5 с-оптимальность Алгоритм А называется с-оптимальным (c-competitive), если для любого r и для любого opt выполняется неравенство cost A (r) < с · cost opt (r) + а где opt – некий оптимальный алгоритм

6 The k-server Problem Развитие решающих алгоритмов Сomplicated algorithmk O(k) (Fiat-Rabani-Ravid) Harmonic algorithm2 k (Grove) Work-Function algorithm (WFA)2k - 1 (Koutsoupias-Papadimitriou)

Work-Function algorithm

8 Work-Function algorithm Определения Состояние системы – множество координат столиков, у которых стоят официанты - последовательность заказов Рабочая функция W r (X) – функция, сопоставляющая состоянию X наименьшую стоимость обслужить r из начального состояния A 0, придя в X Стоимость – суммарное пройденное расстояние. (наименьший путь определяется оптимальным offline алгоритмом, т.е. знающим r)

9 Work-Function algorithm Находимся в состоянии X Приходит (i+1)-ый заказ r (ρ=r 1 r 2 …r i - предыдущие) Выбираем такое X', чтобы минимизировать - стоимость оптимального перехода из состояния X в X'

Главные результаты теории

11 Главные результаты теории 1 Почему достигается минимум Лемма:

12 Главные результаты теории 2 заметим

13 Главные результаты теории 3 W называется квази выпуклой, если для любого состояния А и В существует биекция h : А > В такая, что для любого разбиения А на мультимножества X и Y, справедливо W(A) + W(B) > W(X + h(Y)) + W(h(X) + Y) Смысл заключается в том, что А можно переделать в В (параллельно переделывая В в А) "маленькими шажками", не увеличивая суммарную работу. Лемма: Все рабочие функции квазивыпуклы

14 Главные результаты теории 4 Состояние А назовем минимизатором точки а относительно W, если на нем достигается минимум Лемма: Если А минимизатор для r относительно W ρ, то А минимизатор для r относительно W ρr

15 Главные результаты теории 5 Теорема: Work-Function algorithm является (2k-1)-оптимальным, т.е. cost A (r) < (2k-1) · cost opt (r) + а

16 Вопросы

17 Ссылки Конспект лекций Э.А.Гирша /031210_ pdf Решение задачи n-line/scribes/lec8-9. ps Решение задачи гармоническим методом kserver.ppt