logo
Проектування друкованих плат пристроїв комп’ютерних систем

4.2 Алгоритм Хейса

Метод Хейса здійснює пошук найкоротшого шляху в багатошаровому ДРП між двома заданими осередками A і B. Для кожного шару i вводиться своє ДРПi. Однойменні осередки (вільні) можуть бути звязані переходами. Осередки можуть бути або зайнятими, або вільними. Кожному вільному осередку ставиться у відповідність індекс довжини Pi і індекс кількості переходів, причому при переході з шару в шар індекс довжини збільшується на 1. Індекс застосовується для зменшення числа переходів.

В процесі розповсюдження хвилі для кожного шару використовуються наступні масиви: ДРПi - стан осередків i-го шару; Li - поточного фронту хвилі в i-м шарі; Mi - осередки шару i сусідні до осередків з Li. При утворенні чергового фронту для i-го шару разом з осередками з Mi використовуються ті вільні осередки i-го шару, в яких можливий перехід з інших шарів і які мають той же індекс P.

Недолік методу: хвиля розповсюджується послідовно в кожному з шарів і незалежно, це приводить до великих витрат машинного часу.

Приклад: проведення траси D6:1,D4:5

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

18

1

18

17

18

2

O

1

13

O

3

O

2

D5

14

O

16

15

14

13

14

15

16

17

4

O

3

15

O

15

14

13

12

13

14

15

16

5

O

4

15

O

14

13

12

11

12

13

14

15

18

6

O

5

17

O

13

12

11

10

11

12

13

14

17

18

7

O

6

18

O

11

10

9

10

11

12

13

16

17

18

8

O

7

19

O

10

9

8

9

10

11

12

15

16

17

9

17

O

8

20

O

9

8

7

8

9

10

11

14

15

16

10

17

16

O

9

21

O

8

7

6

7

8

9

10

13

14

15

11

16

15

O

10

22

O

7

6

5

6

7

8

9

12

13

14

12

15

14

O

11

23

O

6

5

4

5

6

7

8

11

12

13

13

14

13

O

12

24

O

5

4

3

4

5

6

7

10

11

12

14

14

13

12

11

10

9

8

7

4

3

2

3

4

5

6

11

12

13

15

13

12

11

10

9

8

7

6

3

2

1

2

3

4

5

12

13

14

16

12

11

10

9

8

7

6

5

2

1

O

1

13

O

13

14

15

17

13

12

3

2

O

2

D6

14

O

15

14

15

16

18

14

13

O

1

8

O

5

4

3

O

3

15

O

16

15

16

17

19

14

15

O

2

D4

9

O

O

4

15

O

17

16

17

18

20

15

16

O

3

10

O

7

6

O

5

17

O

18

17

18

21

16

17

O

4

11

O

8

7

O

6

18

O

18

22

17

18

O

5

12

O

9

8

O

7

19

O

23

18

O

6

13

O

10

9

O

8

20

O

24

O

7

14

O

11

10

O

9

21

O

25

12

11

O

10

22

O

26

18

17

16

15

14

13

12

O

11

23

O

27

18

17

16

15

14

13

O

12

24

O

28

18

17

16

15

14

15

16

17

18

29

18

17

16

15

16

17

18

30

Рисунок. 4.2 - Трасування (шар 1)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

1

18

17

18

2

18

17

16

17

18

3

O

1

13

O

18

17

16

15

16

17

18

4

O

2

D5

14

O

17

16

15

14

15

16

17

18

5

O

3

15

O

16

15

14

13

14

15

16

17

18

6

O

4

15

O

15

14

13

12

13

14

15

16

17

18

7

O

5

17

O

13

12

11

12

13

14

15

16

17

18

8

O

6

18

O

12

11

10

11

12

13

14

15

16

17

18

9

O

7

19

O

11

10

9

10

11

12

13

14

15

16

17

10

O

8

20

O

10

9

8

9

10

11

12

13

14

15

16

11

O

9

21

O

9

8

7

8

9

10

11

12

13

14

15

12

18

O

10

22

O

8

7

6

7

8

9

10

11

12

13

14

13

18

17

O

11

23

O

7

6

5

6

7

8

9

10

11

12

13

14

18

17

16

O

12

24

O

6

5

4

5

6

7

8

9

10

11

12

15

17

16

15

11

12

13

16

16

15

14

9

8

7

6

5

4

3

2

1

2

3

4

5

12

13

14

17

15

14

13

8

7

6

5

4

3

2

1

O

1

13

O

13

14

15

18

14

13

12

9

8

7

6

5

4

3

2

O

2

D6

14

O

14

15

16

19

15

14

13

O

1

8

O

5

4

3

O

3

15

O

16

15

16

17

20

16

15

14

O

2

D4

9

O

6

5

4

O

4

15

O

17

16

17

18

21

17

16

15

O

3

10

O

7

6

5

O

5

17

O

18

17

18

22

18

17

16

17

O

4

11

O

8

7

6

O

6

18

O

18

23

18

17

18

O

5

12

O

9

8

7

O

7

19

O

24

18

O

6

13

O

10

9

8

O

8

20

O

25

O

7

14

O

11

10

9

O

9

21

O

26

17

16

15

14

13

12

11

10

O

10

22

O

27

18

17

16

15

14

13

12

11

O

11

23

O

28

O

12

24

O

29

18

17

16

15

16

17

18

30

18

17

16

17

18

Рисунок. 4.3 - Трасування (шар 2)

Таблиця 4.2 - Проведення траси

шаг

L1

M1

v1

L2

M2

v2

1

,( 17, 13)

,( 17, 12),( 16, 13)

0

,( 17, 13)

,( 17, 12),( 16, 13)

0

2

,( 17, 12),( 16, 13)

,( 15, 13),( 16, 14),( 17, 11),( 16, 12),( 18, 12)

0

,( 17, 12),( 16, 13)

,( 17, 11),( 16, 12),( 16, 14),( 18, 12)

0

3

,( 15, 13),( 16, 14),( 17, 11),( 16, 12),( 18, 12)

,( 19, 12),( 18, 11),( 16, 11),( 15, 12),( 14, 13),( 15, 14),( 16, 15)

0

,( 17, 11),( 16, 12),( 16, 14),( 18, 12)

,( 16, 11),( 17, 10),( 18, 11),( 19, 12),( 16, 15)

0

4

,( 19, 12),( 18, 11),( 16, 11),( 15, 12),( 14, 13),( 15, 14),( 16, 15)

,( 19, 11),( 15, 11),( 14, 12),( 13, 13),( 14, 14),( 15, 15),( 16, 16)

0

,( 16, 11),( 17, 10),( 18, 11),( 19, 12),( 16, 15)

,( 16, 10),( 17, 9),( 18, 10),( 19, 11),( 20, 12),( 14, 13),( 16, 16)

1

5

,( 19, 11),( 15, 11),( 14, 12),( 13, 13),( 14, 14),( 15, 15),( 16, 16)

,( 17, 9),( 19, 10),( 14, 11),( 13, 12),( 12, 13),( 13, 14),( 14, 15),( 15, 16),( 16, 17)

1

,( 16, 10),( 17, 9),( 18, 10),( 19, 11),( 20, 12),( 14, 13),( 16, 16)

,( 16, 9),( 17, 8),( 18, 9),( 19, 10),( 20, 11),( 21, 12),( 14, 12),( 13, 13),( 14, 14),( 16, 17)

1

6

,( 17, 9),( 19, 10),( 14, 11),( 13, 12),( 12, 13),( 13, 14),( 14, 15),( 15, 16),( 16, 17)

,( 21, 12),( 17, 8),( 16, 9),( 13, 11),( 12, 12),( 11, 13),( 12, 14),( 13, 15),( 14, 16),( 15, 17)

2

,( 16, 9),( 17, 8),( 18, 9),( 19, 10),( 20, 11),( 21, 12),( 14, 12),( 13, 13),( 14, 14),( 16, 17)

,( 16, 8),( 17, 7),( 18, 8),( 20, 10),( 21, 11),( 22, 12),( 14, 11),( 13, 12),( 12, 13),( 13, 14),( 14, 15)

1

7

,( 21, 12),( 17, 8),( 16, 9),( 13, 11),( 12, 12),( 11, 13),( 12, 14),( 13, 15),( 14, 16),( 15, 17)

,( 17, 7),( 16, 8),( 15, 9),( 21, 11),( 22, 12),( 12, 11),( 11, 12),( 10, 13),( 11, 14),( 12, 15),( 13, 16),( 14, 17)

2

,( 16, 8),( 17, 7),( 18, 8),( 20, 10),( 21, 11),( 22, 12),( 14, 11),( 13, 12),( 12, 13),( 13, 14),( 14, 15)

,( 16, 7),( 17, 6),( 18, 7),( 21, 10),( 22, 11),( 23, 12),( 13, 11),( 12, 12),( 11, 13),( 12, 14),( 13, 15),( 14, 16)

1

8

,( 17, 7),( 16, 8),( 15, 9),( 21, 11),( 22, 12),( 12, 11),( 11, 12),( 10, 13),( 11, 14),( 12, 15),( 13, 16),( 14, 17)

,( 17, 6),( 16, 7),( 15, 8),( 22, 11),( 23, 12),( 11, 11),( 10, 12),( 9, 13),( 10, 14),( 11, 15),( 12, 16),( 13, 17)

2

,( 16, 7),( 17, 6),( 18, 7),( 21, 10),( 22, 11),( 23, 12),( 13, 11),( 12, 12),( 11, 13),( 12, 14),( 13, 15),( 14, 16)

,( 16, 6),( 17, 5),( 18, 6),( 22, 10),( 23, 11),( 24, 12),( 12, 11),( 11, 12),( 10, 13),( 11, 14),( 12, 15),( 13, 16),( 14, 17)

1

9

,( 17, 6),( 16, 7),( 15, 8),( 22, 11),( 23, 12),( 11, 11),( 10, 12),( 9, 13),( 10, 14),( 11, 15),( 12, 16),( 13, 17)

,( 17, 5),( 16, 6),( 15, 7),( 10, 11),( 9, 12),( 8, 13),( 9, 14),( 10, 15),( 11, 16),( 12, 17),( 23, 11),( 24, 12)

2

,( 16, 6),( 17, 5),( 18, 6),( 22, 10),( 23, 11),( 24, 12),( 12, 11),( 11, 12),( 10, 13),( 11, 14),( 12, 15),( 13, 16),( 14, 17)

,( 16, 5),( 18, 5),( 23, 10),( 24, 11),( 25, 12),( 11, 11),( 10, 12),( 9, 13),( 10, 14),( 11, 15),( 12, 16),( 13, 17),( 14, 18)

1

10

,( 17, 5),( 16, 6),( 15, 7),( 10, 11),( 9, 12),( 8, 13),( 9, 14),( 10, 15),( 11, 16),( 12, 17),( 23, 11),( 24, 12)

,( 17, 4),( 16, 5),( 15, 6),( 9, 11),( 8, 12),( 7, 13),( 8, 14),( 9, 15),( 10, 16),( 11, 17),( 14, 19),( 24, 11),( 25, 12)

3

,( 16, 5),( 18, 5),( 23, 10),( 24, 11),( 25, 12),( 11, 11),( 10, 12),( 9, 13),( 10, 14),( 11, 15),( 12, 16),( 13, 17),( 14, 18)

,( 24, 10),( 25, 11),( 26, 12),( 10, 11),( 9, 12),( 8, 13),( 9, 14),( 10, 15),( 11, 16),( 12, 17),( 13, 18),( 14, 19)

1

11

,( 17, 4),( 16, 5),( 15, 6),( 9, 11),( 8, 12),( 7, 13),( 8, 14),( 9, 15),( 10, 16),( 11, 17),( 14, 19),( 24, 11),( 25, 12)

,( 17, 3),( 16, 4),( 15, 5),( 8, 11),( 7, 12),( 6, 13),( 7, 14),( 8, 15),( 9, 16),( 10, 17),( 13, 19),( 15, 19),( 14, 20),( 25, 11),( 26, 12)

3

,( 24, 10),( 25, 11),( 26, 12),( 10, 11),( 9, 12),( 8, 13),( 9, 14),( 10, 15),( 11, 16),( 12, 17),( 13, 18),( 14, 19)

,( 25, 10),( 26, 11),( 27, 12),( 9, 11),( 8, 12),( 7, 13),( 8, 14),( 9, 15),( 10, 16),( 11, 17),( 12, 18),( 13, 19),( 14, 20),( 15, 19)

1

12

,( 17, 3),( 16, 4),( 15, 5),( 8, 11),( 7, 12),( 6, 13),( 7, 14),( 8, 15),( 9, 16),( 10, 17),( 13, 19),( 15, 19),( 14, 20),( 25, 11),( 26, 12)

,( 18, 3),( 17, 2),( 16, 3),( 15, 4),( 7, 11),( 6, 12),( 5, 13),( 6, 14),( 7, 15),( 8, 16),( 9, 17),( 12, 19),( 13, 20),( 14, 21),( 15, 20),( 16, 19),( 26, 11),( 27, 12)

3

,( 25, 10),( 26, 11),( 27, 12),( 9, 11),( 8, 12),( 7, 13),( 8, 14),( 9, 15),( 10, 16),( 11, 17),( 12, 18),( 13, 19),( 14, 20),( 15, 19)

,( 18, 3),( 26, 10),( 27, 11),( 8, 11),( 7, 12),( 6, 13),( 7, 14),( 8, 15),( 9, 16),( 10, 17),( 11, 18),( 12, 19),( 13, 20),( 14, 21),( 15, 20),( 16, 19)

2

13

,( 18, 3),( 17, 2),( 16, 3),( 15, 4),( 7, 11),( 6, 12),( 5, 13),( 6, 14),( 7, 15),( 8, 16),( 9, 17),( 12, 19),( 13, 20),( 14, 21),( 15, 20),( 16, 19),( 26, 11),( 27, 12)

,( 18, 2),( 16, 2),( 15, 3),( 14, 4),( 19, 3),( 7, 10),( 6, 11),( 5, 12),( 4, 13),( 5, 14),( 6, 15),( 7, 16),( 8, 17),( 11, 19),( 12, 20),( 13, 21),( 15, 21),( 16, 20),( 17, 19),( 27, 11),( 28, 12)

3

,( 18, 3),( 26, 10),( 27, 11),( 8, 11),( 7, 12),( 6, 13),( 7, 14),( 8, 15),( 9, 16),( 10, 17),( 11, 18),( 12, 19),( 13, 20),( 14, 21),( 15, 20),( 16, 19)

,( 17, 3),( 19, 3),( 18, 2),( 26, 9),( 27, 10),( 7, 11),( 6, 12),( 5, 13),( 6, 14),( 7, 15),( 8, 16),( 9, 17),( 10, 18),( 11, 19),( 12, 20),( 13, 21),( 15, 21),( 16, 20),( 17, 19)

2

14

,( 18, 2),( 16, 2),( 15, 3),( 14, 4),( 19, 3),( 7, 10),( 6, 11),( 5, 12),( 4, 13),( 5, 14),( 6, 15),( 7, 16),( 8, 17),( 11, 19),( 12, 20),( 13, 21),( 15, 21),( 16, 20),( 17, 19),( 27, 11),( 28, 12)

,( 29, 12),( 28, 11),( 27, 10),( 20, 3),( 19, 2),( 15, 2),( 14, 3),( 13, 4),( 6, 10),( 5, 11),( 4, 12),( 4, 14),( 5, 15),( 6, 16),( 7, 17),( 10, 19),( 11, 20),( 12, 21),( 16, 21),( 17, 20),( 18, 19)

3

,( 17, 3),( 19, 3),( 18, 2),( 26, 9),( 27, 10),( 7, 11),( 6, 12),( 5, 13),( 6, 14),( 7, 15),( 8, 16),( 9, 17),( 10, 18),( 11, 19),( 12, 20),( 13, 21),( 15, 21),( 16, 20),( 17, 19)

,( 26, 8),( 27, 9),( 16, 3),( 17, 2),( 18, 1),( 19, 2),( 20, 3),( 6, 11),( 5, 12),( 4, 13),( 5, 14),( 6, 15),( 7, 16),( 8, 17),( 9, 18),( 10, 19),( 11, 20),( 12, 21),( 16, 21),( 17, 20),( 18, 19)

2

15

,( 29, 12),( 28, 11),( 27, 10),( 20, 3),( 19, 2),( 15, 2),( 14, 3),( 13, 4),( 6, 10),( 5, 11),( 4, 12),( 4, 14),( 5, 15),( 6, 16),( 7, 17),( 10, 19),( 11, 20),( 12, 21),( 16, 21),( 17, 20),( 18, 19)

,( 20, 4),( 21, 3),( 27, 9),( 28, 10),( 29, 11),( 30, 12),( 29, 13),( 18, 18),( 19, 19),( 18, 20),( 17, 21),( 9, 19),( 10, 20),( 11, 21),( 5, 10),( 4, 11),( 4, 15),( 5, 16),( 6, 17),( 13, 3),( 12, 4)

3

,( 26, 8),( 27, 9),( 16, 3),( 17, 2),( 18, 1),( 19, 2),( 20, 3),( 6, 11),( 5, 12),( 4, 13),( 5, 14),( 6, 15),( 7, 16),( 8, 17),( 9, 18),( 10, 19),( 11, 20),( 12, 21),( 16, 21),( 17, 20),( 18, 19)

,( 29, 12),( 27, 8),( 26, 7),( 21, 3),( 20, 2),( 19, 1),( 17, 1),( 16, 2),( 15, 3),( 6, 10),( 5, 11),( 4, 12),( 3, 13),( 4, 14),( 5, 15),( 6, 16),( 7, 17),( 8, 18),( 9, 19),( 10, 20),( 11, 21),( 17, 21),( 18, 20),( 19, 19)

3

16

,( 20, 4),( 21, 3),( 27, 9),( 28, 10),( 29, 11),( 30, 12),( 29, 13),( 18, 18),( 19, 19),( 18, 20),( 17, 21),( 9, 19),( 10, 20),( 11, 21),( 5, 10),( 4, 11),( 4, 15),( 5, 16),( 6, 17),( 13, 3),( 12, 4)

,( 22, 3),( 21, 4),( 27, 8),( 28, 9),( 29, 10),( 30, 11),( 30, 13),( 29, 14),( 19, 18),( 19, 20),( 20, 19),( 18, 21),( 8, 19),( 9, 20),( 10, 21),( 5, 17),( 4, 16),( 4, 10),( 12, 3),( 11, 4)

3

,( 29, 12),( 27, 8),( 26, 7),( 21, 3),( 20, 2),( 19, 1),( 17, 1),( 16, 2),( 15, 3),( 6, 10),( 5, 11),( 4, 12),( 3, 13),( 4, 14),( 5, 15),( 6, 16),( 7, 17),( 8, 18),( 9, 19),( 10, 20),( 11, 21),( 17, 21),( 18, 20),( 19, 19)

,( 20, 1),( 21, 2),( 22, 3),( 16, 1),( 15, 2),( 14, 3),( 26, 6),( 27, 7),( 29, 11),( 30, 12),( 29, 13),( 19, 18),( 20, 19),( 19, 20),( 18, 21),( 5, 10),( 4, 11),( 3, 12),( 2, 13),( 3, 14),( 4, 15),( 5, 16),( 6, 17),( 7, 18),( 8, 19),( 9, 20),( 10, 21)

3

17

,( 22, 3),( 21, 4),( 27, 8),( 28, 9),( 29, 10),( 30, 11),( 30, 13),( 29, 14),( 19, 18),( 19, 20),( 20, 19),( 18, 21),( 8, 19),( 9, 20),( 10, 21),( 5, 17),( 4, 16),( 4, 10),( 12, 3),( 11, 4)

,( 22, 4),( 23, 3),( 22, 2),( 21, 1),( 29, 10),( 30, 11),( 30, 13),( 29, 14),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 4, 10),( 3, 11),( 2, 12),( 1, 13),( 2, 14),( 3, 15),( 4, 16),( 5, 17),( 6, 18),( 7, 19),( 8, 20),( 9, 21),( 15, 1),( 14, 2),( 13, 3),( 23, 3),( 22, 4),( 27, 7),( 28, 8),( 29, 9),( 30, 10),( 30, 14),( 29, 15),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 9, 21),( 8, 20),( 7, 19),( 2, 13),( 11, 3),( 10, 4),( 4, 17)

4

,( 20, 1),( 21, 2),( 22, 3),( 16, 1),( 15, 2),( 14, 3),( 26, 6),( 27, 7),( 29, 11),( 30, 12),( 29, 13),( 19, 18),( 20, 19),( 19, 20),( 18, 21),( 5, 10),( 4, 11),( 3, 12),( 2, 13),( 3, 14),( 4, 15),( 5, 16),( 6, 17),( 7, 18),( 8, 19),( 9, 20),( 10, 21)

,( 22, 4),( 23, 3),( 22, 2),( 21, 1),( 29, 10),( 30, 11),( 30, 13),( 29, 14),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 4, 10),( 3, 11),( 2, 12),( 1, 13),( 2, 14),( 3, 15),( 4, 16),( 5, 17),( 6, 18),( 7, 19),( 8, 20),( 9, 21),( 15, 1),( 14, 2),( 13, 3),( 26, 5),( 27, 6)

3

18

,( 22, 4),( 23, 3),( 22, 2),( 21, 1),( 29, 10),( 30, 11),( 30, 13),( 29, 14),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 4, 10),( 3, 11),( 2, 12),( 1, 13),( 2, 14),( 3, 15),( 4, 16),( 5, 17),( 6, 18),( 7, 19),( 8, 20),( 9, 21),( 15, 1),( 14, 2),( 13, 3),( 23, 3),( 22, 4),( 27, 7),( 28, 8),( 29, 9),( 30, 10),( 30, 14),( 29, 15),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 9, 21),( 8, 20),( 7, 19),( 2, 13),( 11, 3),( 10, 4),( 4, 17)

,( 23, 4),( 24, 3),( 27, 6),( 28, 7),( 29, 8),( 30, 9),( 30, 15),( 29, 16),( 21, 18),( 22, 19),( 21, 20),( 20, 21),( 8, 21),( 7, 20),( 6, 19),( 2, 12),( 1, 13),( 2, 14)

4

,( 22, 4),( 23, 3),( 22, 2),( 21, 1),( 29, 10),( 30, 11),( 30, 13),( 29, 14),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 4, 10),( 3, 11),( 2, 12),( 1, 13),( 2, 14),( 3, 15),( 4, 16),( 5, 17),( 6, 18),( 7, 19),( 8, 20),( 9, 21),( 15, 1),( 14, 2),( 13, 3),( 26, 5),( 27, 6)

,( 22, 1),( 23, 2),( 24, 3),( 23, 4),( 29, 9),( 30, 10),( 30, 14),( 29, 15),( 14, 1),( 13, 2),( 12, 3),( 27, 5),( 21, 18),( 22, 19),( 21, 20),( 20, 21),( 8, 21),( 7, 20),( 6, 19),( 5, 18),( 4, 17),( 3, 16),( 2, 15),( 1, 14),( 1, 12),( 2, 11),( 3, 10)

3

19

,( 23, 4),( 24, 3),( 27, 6),( 28, 7),( 29, 8),( 30, 9),( 30, 15),( 29, 16),( 21, 18),( 22, 19),( 21, 20),( 20, 21),( 8, 21),( 7, 20),( 6, 19),( 2, 12),( 1, 13),( 2, 14)

,( 23, 5)

4

,( 22, 1),( 23, 2),( 24, 3),( 23, 4),( 29, 9),( 30, 10),( 30, 14),( 29, 15),( 14, 1),( 13, 2),( 12, 3),( 27, 5),( 21, 18),( 22, 19),( 21, 20),( 20, 21),( 8, 21),( 7, 20),( 6, 19),( 5, 18),( 4, 17),( 3, 16),( 2, 15),( 1, 14),( 1, 12),( 2, 11),( 3, 10)

,( 23, 5)

3

Шляхи одночасно досягли координати ( 23, 5), тому шлях проводится за найменшим значенням ?.

Остаточно шлях має вигляд:

Шар 2:

(17,13),( 17, 12),( 17, 11),( 17, 10),( 17, 9),( 17, 8),( 17, 7),( 17, 6),

Перехід на шар 1:

( 17, 5),( 17, 4),( 17, 3),( 18, 3),( 19, 3),( 20, 3),( 21, 3),( 22, 3),( 23, 3),( 23, 4), ( 23, 5)