Задача: используя метод ветвей и границ найти вариант размещения 6-ти элементов на 6-ти позициях платы размером 1x6 позиций.
Исходные данные: матрица весовых коэффициентов R(i,j), задающая для каждой пары элементов вес соединяющего их проводника, D(i,j) - матрица длин проводника между двумя элементами.
R(i,j) =
D(i,j) =
Алгоритм данного метода основан на поиске оптимального расположения элементов на позициях путём последовательного переборе всевозможных сочетаний элементов, ещё не закреплённых на определённых позициях.
Расчёты ведутся производятся по следующим формулам:
Fp = nn r(i,j)*d(i,j), IX(1,n), jX(i,n),
w = n sortk(r(i,j))*sortk(d(i,j)), iX(1,n), jX(n+1,N), kX(1,n)
U = n sortk(r(i,j))*sortk(d(i,j)), iX(n+1,N), jX(n+2,N)
Fоц = Fp + w + U
Исходные данные введём в программу на языке Pascal. Недостатком данной программы является отсутствие анализа ветвления при получении одинаковых минимальных значений функции Fоц в разных позициях для одного элемента. Упрощённый алгоритм, после нахождения минимального значения, выбирает в качестве оптимальной ту позиции, в которой данное значение было получено впервые. Таким образом, применение данного алгоритма даёт гарантированного верный результат лишь в случае отсутствия ветвления. Это обстоятельство необходимо проанализировать по итогам расчётов.
Распечатка результатов вычислений, выполненных программой приведена ниже:
Input data:
R-table (weight) D-table (lenght)
---------------- ----------------
0 2 2 3 9 4 0 1 2 3 4 5
2 0 1 10 5 6 1 0 1 2 3 4
2 1 0 3 4 7 2 1 0 1 2 3
3 10 3 0 7 8 3 2 1 0 1 2
9 5 4 7 0 11 4 3 2 1 0 1
4 6 7 8 11 0 5 4 3 2 1 0
---------------- ----------------
*** Calculation for vertex #1 ***
Put vertex #1 into position of vertex #1:
1 2 3 4 5 6
Fp==0
w=9*1+4*2+3*3+2*4+2*5+=44
U=11*1+10*1+8*1+7*1+7*2+6*2+5*2+4*3+3*3+1*4+=97
-------
Fest=141
Put vertex #1 into position of vertex #2:
2 1 3 4 5 6
Fp==0
w=9*1+4*1+3*2+2*3+2*4+=33
U=11*1+10*1+8*1+7*2+7*2+6*2+5*3+4*3+3*4+1*5+=113
-------
Fest=146
Put vertex #1 into position of vertex #3:
3 2 1 4 5 6
Fp==0
w=9*1+4*1+3*2+2*2+2*3+=29
U=11*1+10*1+8*1+7*2+7*2+6*3+5*3+4*4+3*4+1*5+=123
-------
Fest=152
Put vertex #1 into position of vertex #4:
4 2 3 1 5 6
Fp==0
w=9*1+4*1+3*2+2*2+2*3+=29
U=11*1+10*1+8*1+7*2+7*2+6*3+5*3+4*4+3*4+1*5+=123
-------
Fest=152
Put vertex #1 into position of vertex #5:
5 2 3 4 1 6
Fp==0
w=9*1+4*1+3*2+2*3+2*4+=33
U=11*1+10*1+8*1+7*2+7*2+6*2+5*3+4*3+3*4+1*5+=113
-------
Fest=146
Put vertex #1 into position of vertex #6:
6 2 3 4 5 1
Fp==0
w=9*1+4*2+3*3+2*4+2*5+=44
U=11*1+10*1+8*1+7*1+7*2+6*2+5*2+4*3+3*3+1*4+=97
-------
Fest=141
Fmin=141 n_min=1
*** Calculation for vertex #2 ***
Put vertex #2 into position of vertex #2:
1 2 3 4 5 6
Fp=2*1+=2
w=9*2+4*3+3*4+2*5+10*1+6*2+5*3+1*4+=93
U=11*1+8*1+7*1+7*2+4*2+3*3+=57
-------
Fest=152
Put vertex #2 into position of vertex #3:
1 3 2 4 5 6
Fp=2*2+=4
w=9*1+4*3+3*4+2*5+10*1+6*1+5*2+1*3+=72
U=11*1+8*1+7*2+7*2+4*3+3*4+=71
-------
Fest=147
Put vertex #2 into position of vertex #4:
1 4 3 2 5 6
Fp=2*3+=6
w=9*1+4*2+3*4+2*5+10*1+6*1+5*2+1*2+=67
U=11*1+8*1+7*2+7*3+4*3+3*4+=78
-------
Fest=151
Put vertex #2 into position of vertex #5:
1 5 3 4 2 6
Fp=2*4+=8
w=9*1+4*2+3*3+2*5+10*1+6*1+5*2+1*3+=65
U=11*1+8*1+7*2+7*2+4*3+3*4+=71
-------
Fest=144
Put vertex #2 into position of vertex #6:
1 6 3 4 5 2
Fp=2*5+=10
w=9*1+4*2+3*3+2*4+10*1+6*2+5*3+1*4+=75
U=11*1+8*1+7*1+7*2+4*2+3*3+=57
-------
Fest=142
Fmin=142 n_min=6
*** Calculation for vertex #3 ***
Put vertex #3 into position of vertex #3:
1 6 3 4 5 2
Fp=2*5+2*2+1*3+=17
w=9*1+4*3+3*4+10*1+6*2+5*4+7*1+4*1+3*2+=92
U=11*1+8*2+7*3+=48
-------
Fest=157
Put vertex #3 into position of vertex #4:
1 6 4 3 5 2
Fp=2*5+2*3+1*2+=18
w=9*1+4*2+3*4+10*1+6*3+5*4+7*1+4*1+3*2+=94
U=11*1+8*2+7*3+=48
-------
Fest=160
Put vertex #3 into position of vertex #5:
1 6 5 4 3 2
Fp=2*5+2*4+1*1+=19
w=9*1+4*2+3*3+10*2+6*3+5*4+7*1+4*2+3*3+=108
U=11*1+8*1+7*2+=33
-------
Fest=160
Put vertex #3 into position of vertex #6:
1 6 2 4 5 3
Fp=2*5+2*1+1*4+=16
w=9*2+4*3+3*4+10*1+6*2+5*3+7*1+4*2+3*3+=103
U=11*1+8*1+7*2+=33
-------
Fest=152
Fmin=152 n_min=6
*** Calculation for vertex #4 ***
Put vertex #4 into position of vertex #4:
1 6 2 4 5 3
Fp=2*5+2*1+3*3+1*4+10*2+3*2+=51
w=9*2+4*4+6*1+5*3+7*1+4*3+8*1+7*1+=89
U=11*2+=22
-------
Fest=162
Put vertex #4 into position of vertex #5:
1 6 2 5 4 3
Fp=2*5+2*1+3*4+1*4+10*1+3*3+=47
w=9*2+4*3+6*2+5*3+7*1+4*2+8*1+7*2+=94
U=11*1+=11
-------
Fest=152
Put vertex #4 into position of vertex #6:
1 6 2 3 5 4
Fp=2*5+2*1+3*2+1*4+10*3+3*1+=55
w=9*3+4*4+6*1+5*2+7*2+4*3+8*1+7*2+=107
U=11*1+=11
-------
Fest=173
Fmin=152 n_min=5
*** Calculation for vertex #5 ***
Put vertex #5 into position of vertex #5:
1 6 2 5 4 3
Fp=2*5+2*1+3*4+9*3+1*4+10*1+5*2+3*3+4*2+7*1+=99
w=4*2+6*3+7*1+8*2+11*1+=60
U==0
-------
Fest=159
Put vertex #5 into position of vertex #6:
1 6 2 5 3 4
Fp=2*5+2*1+3*4+9*2+1*4+10*1+5*3+3*3+4*1+7*2+=98
w=4*3+6*2+7*2+8*1+11*1+=57
U==0
-------
Fest=155
Fmin=155 n_min=6
Calculation complete
|1|6|2|5|3|4|
The smallest Fest is 155
На выходе получаем массив, содержащий номера позиций, в которые помещается элементы с номером элемента массива:
Элемент
Позиция
Отсортируем данные в строке «Позиция» по возрастанию, тогда увидим в каком порядке расположены элементы на плате:
Элемент
Позиция
В ходе вычислений ветвлений по минимальному значению Fоц не обнаружено, следовательно, в данном случае полученный результат действительно представляет собой оптимальный вариант размещения элементов по позициям.
