Составители:
Рубрика:
101
шаге необходимо следить, чтобы не образовался цикл. Как только все
вершины будут задействованы, алгоритм завершен. Минимальный об
щий путь равен сумме всех выбранных путей.
Пусть, например, имеется 7 (A, B, C, D, E, F, G) городов и таблица
минимальных расстояний.
Таблица 5.13
B 81
C
42
91
D
63
52
42
E
51
123381
F
22135572
91
G
82
71
14919222
A
B
CDEF
Из табл. 5.13 минимальное расстояние равно 15 (A–E). Соединим эти
вершины. Следующее минимальное расстояние 17 (B–G). Соединим эти
вершины. Следующее минимальное расстояние 18 (A–B и E–G). Мы мо
жем выбрать только одно (любое) соединение, иначе образуется цикл.
Возьмем, например, A–B, а E–G исключим из рассмотрения. Следующим
минимальным расстоянием будет 19 (E–F и C–B). В данном случае мы
можем соединить обе пары вершин. Очередное минимальное расстояние
21 (B–E) проводить нельзя, так как образуется цикл. Следующее мини
мальное расстояние 22 (A–F F–G) также следует пропустить (любая из
этих пар образует цикл. Расстояние 24 (A–C) также неприемлемо, рас
стояние 25 (B–D) завершает построение минимальной сети дорог. Сум
марная длина всех построенных дорог равна L = 15+17+18+19+19+25 =
= 113. Решения меньшей длины не существует.
5.12. Построение турнирной таблицы
Для проведения соревнований используются турнирные таблицы.
В этих таблицах отмечается, какое количество туров нужно сыграть в
турнире и какие команды или игроки должны играть в каждом туре.
При этом количество туров должно быть минимально возможным, а в
каждом туре должны быть заняты все или почти все игроки.
Приведем метод построения турнирной таблицы при условии, что
число команд четное. Если число команд нечетное, то вводится фик
тивный игрок, который не играет ни в одном туре и вместе с ним отды
хает его соперник по туру. Пусть число игроков равно N, при этом бу
Страницы
- « первая
- ‹ предыдущая
- …
- 99
- 100
- 101
- 102
- 103
- …
- следующая ›
- последняя »
