4551
правка
Минимальные геометрические остовные деревья: различия между версиями
Перейти к навигации
Перейти к поиску
м
Минимальные геометрические остовные деревья (посмотреть исходный код)
Версия от 01:14, 19 декабря 2015
, 19 декабря 2015нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) мНет описания правки |
||
| Строка 2: | Строка 2: | ||
Остовные деревья минимальной длины; остовные деревья минимального веса; минимальные евклидовы остовные деревья; MST; EMST | Остовные деревья минимальной длины; остовные деревья минимального веса; минимальные евклидовы остовные деревья; MST; EMST | ||
== Постановка задачи == | == Постановка задачи == | ||
| Строка 58: | Строка 57: | ||
== Применение == | == Применение == | ||
Минимальные остовные деревья (MST) входят в число самых базовых структур в таких дисциплинах, как вычислительная геометрия и теория графов, и имеют множество вариантов применения. | Минимальные остовные деревья (MST) входят в число самых базовых структур в таких дисциплинах, как вычислительная геометрия и теория графов, и имеют множество вариантов применения. | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Поскольку сложность вычисления MST связана со сложностью нахождения бихроматических пар ближайших точек, открытые вопросы в этих двух задачах родственны; к ним относятся, например, такие варианты, как работа с числом размерностей выше 3. | Поскольку сложность вычисления MST связана со сложностью нахождения бихроматических пар ближайших точек, открытые вопросы в этих двух задачах родственны; к ним относятся, например, такие варианты, как работа с числом размерностей выше 3. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||