Iv. Динамические структуры данных

void Commi( int q ) 
// q – число уже поставленных вершин 
{ 
int i, temp; 

---

IV. Динамические структуры данных
©
 К. Поляков, 1995-2009 
http://kpolyakov.narod.ru
40
if ( q == N ) {
 // перестановка получена 
if ( L < Lmin ) { 
Lmin = L; 
for ( i = 0; i < N; i ++ ) 
//
запомнить новый минимальный тур 

Pmin[i] = P[i]; 
} 
return; 
} 
for ( i = q; i < N; i ++ ) { 
temp = P[q]; P[q] = P[i]; P[i] = temp; 
// P[q] <-> P[i] 
L += D [P[q-1]] [P[q]];
// добавить ребро

Commi ( q+1 );
// рекурсивный вызов 
L -= D [P[q-1]] [P[q]];
// убрать ребро

 
temp = P[q]; P[q] = P[i]; P[i] = temp; 
// P[q] <-> P[i]

} 
} 
Главная трудность такого переборного способа заключается в том, что для больших n (напри-
мер, для n>20) число комбинаций настолько велико, что перебор нереален.
Однако, часто можно найти такую стратегию перебора, при которой сразу отбрасывается 
целая группа вариантов, которые заведомо не лучше уже найденного минимального решения. 
Одним из таких алгоритмов является метод ветвей и границ. 
 Метод ветвей и границ 
Идея этого подхода проста и естественна: если частичная длина пути стала больше длины 
самого лучшего из уже найденных туров, дальнейшую проверку делать бессмысленно. При 
этом второй цикл for в процедуре приобретает вид 
for ( i = q; i < N; i ++ ) { 
temp = P[q]; P[q] = P[i]; P[i] = temp; 
L += D [P[q-1]] [P[q]];