![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Часть 5. Алгоритмы на графах. Точные интерпретации этой нижней границы достаточно сложны, поскольку базовые операции, используемые для решения этих двух задач (сравнение координат в
Интересно поразмышлять над отношениями, связывающими графы и геометрические алгоритмы, которая обусловлена решением задачи вычисления эвклидова дерева MST. Многие практические задачи, с которыми нам, возможно, придется столкнуться, могут быть сформулированы либо как геометрические задачи, либо как задачи на графах. Если преобладающим свойством является физическое расположение объектов, то можно обращаться к помощи геометрических алгоритмов, описанных в части 7; однако если фундаментальное значение приобретают взаимосвязи между объектами, алгоритмы на графах, рассмотренные в данном разделе, скорее всего, окажутся более предпочтительными. Эвклидово дерево MST, по-видимому, приходится на интерфейс между двумя этими подходами (входные данные обладают геометрическими свойствами, а элементы выходных данных взаимосвязаны), и в силу этого обстоятельства разработка простых методов вычисления эвклидова дерева MST остается труднодостижимой целью. В главе 21 мы столкнемся с подобного рода задачей, которая также приходится на этот интерфейс, но там эвклидов подход реализуется через алгоритмы, обладающие куда большим быстродействием, чем соответствующие задачи на графах.
|