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

i (то есть d
ik
 > d
jk
) ; 
2. найти самую дальнюю вершину l из всех тех вершин, в которые надо ехать через вершину 
j (то есть d
il
 < d
jl
) ; 
3. вычислить середину расстояния между вершинами k и l; если она попадает на ребро 
(i,j) и расстояние до самых дальних вершин меньше уже найденного, запомнить это ме-
сто 
Ниже этот алгоритм записан на на языке Си: 
minDist = 32767;
// большое число 
 for (i = 0; i < N-1; i ++ ) 
 for (j = i+1; j < N; j ++ ) { 
// перебрать все ребра (i,j) 
maxDi = maxDj = 0; 
for (k = 0; k < N; k ++ ) {
// перебрать все вершины 
if ( k == i || k == j ) continue; 
if (D[j,k] < D[i,k]) 
if (D[j,k] < maxDj) maxDj = D[j,k]; 
else 
if (D[j,k] < maxDj) maxDj = D[j,k]; 
} 
 dist = (maxDi + D[i][j] + maxDj) / 2; 
 if ( dist < minDist && dist > maxDi && 

dist < maxDi+D[i][j] ) { 

---

Программирование на языке Си
©
 К. Поляков, 1995-2009 
http://kpolyakov.narod.ru
39

minDist = dist; 
// запомнить новый вариант 

... 

} 
 
 } 
 
Задача коммивояжера 
 Формулировка задачи 
Эта знаменитая задача была сформулирована в 1934 г. В области дискретной оптимизации 
она стала испытательным полигоном, на котором проверяются новые методы. Проблема заклю-
чается в том, что эта задача относится к многочисленному классу задач, которые теоретически 
не решаются иначе, чем перебором.