Единая транспортная система и география транспорта вариант неизвестен

P(1,6)=106+0=106

P(3,2)=0+106=106

P(3,6)=0+0=0

P(6,1)=196+87=283

_{Для ветвления выберем  пару  претендентов с максимальной оценкой P(6,1)=283}

Произведем  ветвление:

_{,где  и}

Вычислим  оценку для  :

V( )=V( )+P(6,1)=3038+283=3321

Построим  матрицу  , вычеркнув шестую строку и первый столбец в матрице и выполним процесс приведения, запретив переезд из города 1 в город 6

.   

₌ 

Вычислим  оценку для  :

V( )=V( )+ =3038+106= 3144

Полученная  матрица имеет размерность 2х2 и  допускает включение в матрицу  только двух пар городов (1,2) и (3,6)

В результате получаем цикл _,

_{отвечающий  подмножеству  , длина которого равна 3144.}

_{Сравним длину этого цикла с полученными ранее оценками для неветвленных подмножеств. Последовательность объезда городов можно представить следующим образом:5→3→6→1→2→4→5} 

Подмножество  V( )=2946‹V( )=3144. Это подмножество может привести к образованию цикла с меньшей оценкой, поэтому оно должно быть подвергнуто анализу. Для этого восстановим исходную матрицу и запретим проезд из города 5 в город 3, одновременно выполнив приведение.

₌ 
 
 
 

Определим оценку множества  , вычислив сумму приводящих констант:

_{=2602+283+61=2946}

Выберем пары городов-претендентов на ветвление, т.е.(i,j), для которых =0

=0, =0, =0, =0, =0, =0, =0, =0

Для выделенных претендентов подсчитаем оценки

P(1,6)=41+0=41

P(2,3)=0+65=65

P(2,4)=0+9=9

P(2,5)=0+49=49

P(3,6)=87+0=87

P(4,2)=49+2=51

P(5,6)=2+0=2

P(6,1)=65+2=67

_{Для ветвления выберем пару  претендентов с максимальной оценкой P(3,6)=87} 

Произведем  ветвление:

, где  =(3,6), = .

Вычислим  оценку для

V( )=V( )+P(3,6)=2946+87=3033

Построим  матрицу  , для этого вычеркнем в матрице _{третью строку и шестой столбец. Чтобы избежать образования замкнутых подциклов,  запретим переезд из города 6 в город 3 и выполним процесс приведения}

₌  
 

Вычислим оценку для :

V( )=V( )+ =2946+43=2989

А так  как V( )‹V( ), то для ветвления на очередном шаге выберем подмножество V( ).

Выберем пары городов-претендентов на ветвление

=0, =0, =0, =0, =0, =0, =0 =0

Р(1,3)=368+0=368

Р(2,3)=0+0=0

Р(2,4)=0+7=7

P(2,5)=0+49=49

P(4,2)=49+0=49

P(5,1)=0+0=0

P(5,2)=0+0=0

P(6,1)=529+0=529

_{Для ветвления выберем  пару  претендентов с максимальной оценкой  P(6,1)=529}

, где _{и .}

Вычислим  оценку для

V( )=V( )+P(6,1)=2989+529=3518

Построим матрицу , для этого вычеркнем в матрице _{шестую строку и первый столбец и выполним процесс приведения}

₌ 

_{Поскольку полученная матрица является приведенной, оценка для подмножества равна оценке для подмножества = 2989}

А так  как V( )‹V( ), то для ветвления на очередном шаге выберем подмножество V( ).

Выберем пары городов-претендентов на ветвление

=0, =0, =0, =0, =0, =0

P(1,3)=368+0=368

P(2,3)=0+0=0

P(2,4)=0+7=7

P(2,5)=0+49=49

P(4.2)=49+0=49

P(5,2)=7+0=7

Расчеты привели нас к замкнутому подциклу _{3→6→1→3}

_{Запретим  проезд из города 1 в  город 3 и постоим  матрицу  заново,выполнив  процесс приведения}

₌ 

V( )=V( )+ =2989+368=3357

Так как V( )‹V( ), то для ветвления на очередном шаге выберем подмножество V( ).

Выберем пары городов-претендентов на ветвление

=0, =0, =0, =0, =0, =0

P(1,5)=84+0=84

P(2,3)=0+332=332

P(2,4)=0+7=7

P(2,5)=0+0=0

P(4.2)=49+0=49

P(5,2)=7+0=7

_{Для ветвления выберем  пару  претендентов с максимальной оценкой P(2,3)=332}

, где _и

Вычислим  оценку для

V( )=V( )+P(2,3)=3357+332=3689

Построим  матрицу  , для этого вычеркнем в матрице _{вторую строку и третий столбец и выполним процесс приведения} 

₌  

V( )=V( )+ =3357+7=3364

Так как V( )‹V( ), то для ветвления на очередном шаге выберем подмножество V( ).

Выберем пары городов-претендентов на ветвление

=0, =0, =0 , =0

P(1,5)=54+0=84

P(4,2)=49+0=49

P(5,2)=0+0=0

P(5,4)=0+546=546

_{Для ветвления выберем пару  претендентов с максимальной оценкой P(5,4)=546}

, где _и

Вычислим  оценку для

V( )=V( )+P(5,4)=3364+546=3910

Построим  матрицу  , для этого вычеркнем в матрице _{пятую строку и четвертый столбец и запретим проезд из города 4 в город 5, выполним процесс приведения}