Альтернативные показатели эффективности онлайновых алгоритмов: различия между версиями

Это понятие можно проиллюстрировать тем, насколько выигрышным может оказаться наличие некоторого ''просмотра вперед'' для алгоритмов решения ''систем метрических задач'' (Metrical Task Systems, MTS). MTS – это абстрактная модель, предложенная в работе [2], которая обобщает обширное семейство онлайновых задач, среди которых задача подкачки, k-серверная задача, доступ к спискам и многие другие. В системе метрических задач сервер может перемещаться по точкам метрического пространства (состояниям) при обслуживании последовательности запросов, или задач. Стоимость обслуживания задачи зависит от состояния, в котором находится сервер, а общая стоимость последовательности задается суммой пройденных расстояний плюс стоимость обслуживания всех задач. Значение просмотра вперед в этом контексте заключается в том, что сервер может решить, какую задачу обслужить следующей, не только на основании своих предыдущих перемещений и выходных данных, но и на основании некоторого количества будущих запросов.