4551
правка
Применение геометрических остовных сетей: различия между версиями
Перейти к навигации
Перейти к поиску
м
Применение геометрических остовных сетей (посмотреть исходный код)
Версия от 00:03, 28 октября 2016
, 28 октября 2016→Нотация и определения
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
Все рассматриваемые далее сети будут считаться простыми и неориентированными. В качестве модели вычислений используется традиционная алгебраическая модель дерева вычислений, дополненная возможностями косвенной адресации. В частности, представленные далее алгоритмы не используют неалгебраическую функцию типа «пол» (округление до целого числа в меньшую сторону) в качестве операции с единичным временем. Формальное определение задачи выглядит следующим образом. | Все рассматриваемые далее сети будут считаться простыми и неориентированными. В качестве модели вычислений используется традиционная алгебраическая модель дерева вычислений, дополненная возможностями косвенной адресации. В частности, представленные далее алгоритмы не используют неалгебраическую функцию типа «пол» (округление до целого числа в меньшую сторону) в качестве операции с единичным временем. Формальное определение задачи выглядит следующим образом. | ||
''' | |||
Задача 1 (оракул расстояния)'''. Пусть даны произвольная вещественная константа <math>\varepsilon > 0 \;</math> и геометрический граф G в d-мерном евклидовом пространстве с константной протяженностью t. Необходимо построить структуру данных, отвечающую на запросы об <math>(1 + \varepsilon)</math>-аппроксимации кратчайшего пути за константное время. | '''Задача 1 (оракул расстояния)'''. Пусть даны произвольная вещественная константа <math>\varepsilon > 0 \;</math> и геометрический граф G в d-мерном евклидовом пространстве с константной протяженностью t. Необходимо построить структуру данных, отвечающую на запросы об <math>(1 + \varepsilon)</math>-аппроксимации кратчайшего пути за константное время. | ||