Что решает
остовное дерево
Статьи
GRA
Алгоритм
Минимальное остовное дерево
Самая дешёвая сеть, связывающая все вершины: Борувка, Краскал и Прим — три способа применить одну лемму.
O(E log V)
2 задачи
GRA
Алгоритм
Задача коммивояжёра
Кратчайший объезд всех точек: ближайший сосед, 2-opt со списками соседей, Or-opt, оценка Хелда — Карпа.
NP-трудна; точно O(2ⁿ · n²)
2 задачи
Задачи
Часто рядом
граф 2 геоданные 2 классика 2 жадность 1 взвешенный граф 1 система непересекающихся множеств 1 куча 1 кластеризация 1 сети 1 оптимизация 1 эвристика 1 приближение 1