Prim algoritmi qanday ishlaydi?
Mustaqil ish
| 55
|
A |
B |
C | |
|
| ||||
|
I |
4 |
8 |
6 |
368 |
|
II |
9 |
6 |
9 |
346 |
|
III |
4 |
6 |
9 |
202 |
|
|
65 |
66 |
81 |
|
|
A = |
|
|
X0 = (0,0,0,368,346,202)
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x4 |
368 |
4 |
8 |
6 |
1 |
0 |
0 |
|
x5 |
346 |
9 |
6 |
9 |
0 |
1 |
0 |
|
x6 |
202 |
4 |
6 |
9 |
0 |
0 |
1 |
|
F(X0) |
0 |
-65 |
-66 |
-81 |
0 |
0 |
0 |
min (368 : 6 , 346 : 9 , 202 : 9 ) = 224/9
|
|
|
|
|
|
|
|
|
|
|
|
|
|
| |||||||
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
|
|
| |||||||||
|
x4 |
368 |
4 |
8 |
6 |
1 |
0 |
0 |
184/3 |
|
|
| |||||||||
|
x5 |
346 |
9 |
6 |
9 |
0 |
1 |
0 |
346/9 |
|
|
| |||||||||
|
x6 |
202 |
4 |
6 |
9 |
0 |
0 |
1 |
202/9 |
|
|
| |||||||||
|
F(X1) |
0 |
-65 |
-66 |
-81 |
0 |
0 |
0 |
|
|
|
| |||||||||
|
|
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 | |||||||||||||
|
|
368-(202*6):9 |
4-(4*6):9 |
8-(6*6):9 |
6-(9*6):9 |
1-(0*6):9 |
0-(0*6):9 |
0-(1*6):9 | |||||||||||||
|
|
346-(202*9):9 |
9-(4*9):9 |
6-(6*9):9 |
9-(9*9):9 |
0-(0*9):9 |
1-(0*9):9 |
0-(1*9):9 | |||||||||||||
|
|
202 : 9 |
4 : 9 |
6 : 9 |
9 : 9 |
0 : 9 |
0 : 9 |
1 : 9 | |||||||||||||
|
|
0-(202*-81):9 |
-65-(4*-81):9 |
-66-(6*-81):9 |
-81-(9*-81):9 |
0-(0*-81):9 |
0-(0*-81):9 |
0-(1*-81):9 | |||||||||||||
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x4 |
700/3 |
4/3 |
4 |
0 |
1 |
0 |
-2/3 |
|
x5 |
144 |
5 |
0 |
0 |
0 |
1 |
-1 |
|
x3 |
202/9 |
4/9 |
2/3 |
1 |
0 |
0 |
1/9 |
|
F(X1) |
1818 |
-29 |
-12 |
0 |
0 |
0 |
9 |
min (2331/3 : 11/3 , 144 : 5 , 224/9 : 4/9 ) = 284/5
|
|
|
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
|
|
|
|
x4 |
700/3 |
4/3 |
4 |
0 |
1 |
0 |
-2/3 |
175 |
|
|
|
|
x5 |
144 |
5 |
0 |
0 |
0 |
1 |
-1 |
144/5 |
|
|
|
|
x3 |
202/9 |
4/9 |
2/3 |
1 |
0 |
0 |
1/9 |
101/2 |
|
|
|
|
F(X2) |
1818 |
-29 |
-12 |
0 |
0 |
0 |
9 |
|
|
|
|
|
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
2331/3-(144*11/3):5 |
11/3-(5*11/3):5 |
4-(0*11/3):5 |
0-(0*11/3):5 |
1-(0*11/3):5 |
0-(1*11/3):5 |
-2/3-(-1*11/3):5 |
|
144 : 5 |
5 : 5 |
0 : 5 |
0 : 5 |
0 : 5 |
1 : 5 |
-1 : 5 |
|
224/9-(144*4/9):5 |
4/9-(5*4/9):5 |
2/3-(0*4/9):5 |
1-(0*4/9):5 |
0-(0*4/9):5 |
0-(1*4/9):5 |
1/9-(-1*4/9):5 |
|
1818-(144*-29):5 |
-29-(5*-29):5 |
-12-(0*-29):5 |
0-(0*-29):5 |
0-(0*-29):5 |
0-(1*-29):5 |
9-(-1*-29):5 |
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x4 |
2924/15 |
0 |
4 |
0 |
1 |
-4/15 |
-2/5 |
|
x1 |
144/5 |
1 |
0 |
0 |
0 |
1/5 |
-1/5 |
|
x3 |
434/45 |
0 |
2/3 |
1 |
0 |
-4/45 |
1/5 |
|
F(X2) |
13266/5 |
0 |
-12 |
0 |
0 |
29/5 |
16/5 |
min (19414/15 : 4 , - , 929/45 : 2/3 ) = 147/15
|
|
|
|
|
|
|
|
|
|
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
min |
|
x4 |
2924/15 |
0 |
4 |
0 |
1 |
-4/15 |
-2/5 |
731/15 |
|
x1 |
144/5 |
1 |
0 |
0 |
0 |
1/5 |
-1/5 |
- |
|
x3 |
434/45 |
0 |
2/3 |
1 |
0 |
-4/45 |
1/5 |
217/15 |
|
F(X3) |
13266/5 |
0 |
-12 |
0 |
0 |
29/5 |
16/5 |
|
|
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 | ||||||||||
|
19414/15-(929/45*4):2/3 |
0-(0*4):2/3 |
4-(2/3*4):2/3 |
0-(1*4):2/3 |
1-(0*4):2/3 |
-4/15-(-4/45*4):2/3 |
-2/5-(1/5*4):2/3 | ||||||||||
|
284/5-(929/45*0):2/3 |
1-(0*0):2/3 |
0-(2/3*0):2/3 |
0-(1*0):2/3 |
0-(0*0):2/3 |
1/5-(-4/45*0):2/3 |
-1/5-(1/5*0):2/3 | ||||||||||
|
929/45 : 2/3 |
0 : 2/3 |
2/3 : 2/3 |
1 : 2/3 |
0 : 2/3 |
-4/45 : 2/3 |
1/5 : 2/3 | ||||||||||
|
26531/5-(929/45*-12):2/3 |
0-(0*-12):2/3 |
-12-(2/3*-12):2/3 |
0-(1*-12):2/3 |
0-(0*-12):2/3 |
54/5-(-4/45*-12):2/3 |
31/5-(1/5*-12):2/3 | ||||||||||
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
|
|
| |||||
|
x4 |
2056/15 |
0 |
0 |
-6 |
1 |
4/15 |
-8/5 |
|
|
|
| |||||
|
x1 |
144/5 |
1 |
0 |
0 |
0 |
1/5 |
-1/5 |
|
|
|
| |||||
|
x2 |
217/15 |
0 |
1 |
3/2 |
0 |
-2/15 |
3/10 |
|
|
|
| |||||
|
F(X3) |
14134/5 |
0 |
0 |
18 |
0 |
21/5 |
34/5 |
|
|
|
| |||||
|
Базис |
B |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
|
x4 |
2056/15 |
0 |
0 |
-6 |
1 |
4/15 |
-8/5 |
|
x1 |
144/5 |
1 |
0 |
0 |
0 |
1/5 |
-1/5 |
|
x2 |
217/15 |
0 |
1 |
3/2 |
0 |
-2/15 |
3/10 |
|
F(X4) |
14134/5 |
0 |
0 |
18 |
0 |
21/5 |
34/5 |
x1 = 28.8, x2 = 14.46, x3 = 0
F(X) = 65*28.8 + 66*14.46 + 81*0 = 2826
Adabiyotlar
1. Кленберг Дж.,Тардос Е.”Алгоритмы.Разработка и применение”.2016г.
2. Кормен Т.,Лейзерсон Ч.,Ривест Р.«Алгоритмы.Построение и анализ»,2013г.
3. Колдаев. Основы_алгоритмизации_и программирования. 2013 г.
4. Г.Уоррен «Алгоритмические трюки для программистов», 2014 г.
Download 465.6 Kb.
Do'stlaringiz bilan baham:
