4551
правка
Триангуляция с минимальным весом: различия между версиями
Материал из WEGA
Триангуляция с минимальным весом (посмотреть исходный код)
Версия от 11:40, 2 октября 2016
, 2 октября 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 34: | Строка 34: | ||
Для решения задач большого размера применяется другой подход, использующий свойства триангуляции с минимальным весом (MWT), которые обычно помогают для случайных множеств точек определить большинство ребер, которые | Для решения задач большого размера применяется другой подход, использующий свойства триангуляции с минимальным весом (MWT), которые обычно помогают для случайных множеств точек определить большинство ребер, которые ''должны'' входить (или ''не могут'' входить) в MWT. После этого можно применить алгоритм динамического программирования для поиска оставшихся MWT-ребер. Для случайных множеств, состоящих из десятков тысяч точек с равномерным распределением, можно при помощи этого подхода найти точную MWT за несколько минут [1]. | ||
== Применение == | == Применение == | ||
