Жадный алгоритм — алгоритм, заключающийся в принятии локально оптимальных решений на каждом этапе, допуская, что конечное решение также окажется оптимальным.
Алгоритм жадной триангуляции заключается в следующем:
- Генерируется список всех возможных отрезков, соединяющих пары исходных точек, и сортируется по длине.
- Начиная с самого короткого, в триангуляцию последовательно вставляются отрезки из множества отсортированных по длине отрезков. Если отрезок не пересекается с другими ранее вставленными отрезками, то он вставляется, иначе он отбрасывается.
Если все возможные отрезки имеют разную длину, то результат работы этого алгоритма однозначен, иначе он зависит от порядка вставки отрезков одинаковой длины.
Алгоритм корректно работает как для множества точек на плоскости, так и для выпуклых многоугольников.
В случае с невыпуклым многоугольником алгоритм добавит несколько лишних отрезков снаружи.
Трудоемкость работы жадного алгоритма в среднем составляет ~O(N2logN), поэтому на практике он практически не применяется, однако является очень простым для понимания.
