Итерационные алгоритмы улучшения компоновки

В качестве исходных данных выступают уже имеющиеся варианты компоновки.
Пусть К₀- вариант компоновки, имеющий оценку по некоторому параметру F₀ = F(K₀) (меньше - лучше). Пусть К₀ характеризуется некоторым разбиением на куски M₁,..., M_h. Рассмотрим два элемента - x_i ∈ M_a и x_j ∈ M_b. Их обмен приведет к появлению компоновки K₁ с оценкой F₁. Если F₁ < F₀ - то К₁ лучше, чем K₀. Так проводим постепенное улучшение оценки до тех пор, пока это возможно. Абсолютно оптимальный результат может быть и не достигнут из-за немонотонного поведения функции F(K) (мы остаемся в "потенциальной яме"). Глобальный минимум, в отличие от локального, получить проблематично.

Две тактики для окончания итераций при обмене пар элементов:
1. Первый же успешный обмен, приводящий к улучшению оценки, немедленно проводится и фиксируется новая компоновка K_i+1
2. Производится полный перебор вариантов и выбирается обмен, приводящий к максимальной разнице Δ_max = F_i - F_i+1