В процессе перебора храним общую площадь построенных к данному моменту треугольников (S) и суммарную площадь в наилучшем из ранее найденных построений (min). Простейшее из отсечений, которое мы можем использовать, состоит в следующем. Если на каком-то шаге окажется, что S ≥ min, то продолжать построение не имеет смысла и необходимо вернуться к предыдущему шагу.
Как можно улучшить это отсечение? Заметим, что, сравнивая общую площадь треугольников с min, мы никак не учитываем количество треугольников, которые осталось построить. Это можно сделать так. Перед началом работы переборного алгоритма вычислим площадь минимального треугольника, который возможно построить, взяв в качестве вершин какие-то три из заданных N точек (Smin ). Если на очередном шаге перебора нам осталось построить r треугольников, а S + r·Smin ≥ Smin, то также следует выполнить отсечение.
Полученный алгоритм имеет следующий недостаток. В начальный момент
времени min приходится полагать равным бесконечности, и нет никакой
гарантии, что первые из построенных решений будут настолько хорошими,
чтобы указанное отсечение работало эффективно (а это попросту необходимо).
Следовательно, нужно каким-то образом подобрать хорошее начальное
решение. Это можно сделать, например, с помощью жадного алгоритма: строим
треугольник с минимально возможной площадью, выкидываем его вершины,
строим треугольник с минимальной площадью из оставшихся точек и т. д.
Для дальнейшего улучшения алгоритма применим метод локальной оптимизации. Пусть отыскалось решение с меньшей суммарной площадью, чем наилучшее из ранее найденных. Попробуем обменять вершины у каких-то двух треугольников, т.е. перейти от левого рисунка к правому. Перебрав все пары построенных треугольников и все варианты обмена вершин внутри них, нам с некоторой вероятностью удастся улучшить рассматриваемое решение.