Получите свидетельство
Вход
Поиск оптимального маршрута по таблице
1. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
|
| A | B | C | D | E | F |
| A |
| 4 |
|
|
|
|
| B | 4 |
| 6 | 3 | 6 |
|
| C |
| 6 |
|
| 4 |
|
| D |
| 3 |
|
| 2 |
|
| E |
| 6 | 4 | 2 |
| 5 |
| F |
|
|
|
| 5 |
|
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Решение.
Варианты маршрутов:
A-B-C-E-F. Длина маршрута 4 + 6 + 4 + 5 = 19
A-B-D-E-F. Длина маршрута 4 + 3 + 2 + 5 = 14
A-B-E-F. Длина маршрута 4 + 6 + 5 = 15
Видно, что кратчайший путь равен 14.
2. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.
|
| A | B | C | D | E | F |
| A |
| 2 | 4 | 8 |
| 16 |
| B | 2 |
|
| 3 |
|
|
| C | 4 |
|
| 3 |
|
|
| D | 8 | 3 | 3 |
| 5 | 3 |
| E |
|
|
| 5 |
| 5 |
| F | 16 |
|
| 3 | 5 |
|
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E. Передвигаться можно только по указанным дорогам.
Решение.
Заметим, что в Е можно попасть только из D и F, следовательно, в маршруте также обязательно должен присутствовать пункт D. Составим маршрут следующим образом: стартуя из пункта А, будем всегда выбирать тот пункт, расстояние до которого наименьшее. Получим маршрут A—B—D—E—F, его длина равна 15 км. Теперь, начиная с начала маршрута, будем изменять путь, пользуясь следующим соображением: если расстояние, например, A—B—D больше расстояния A—D, то заменяем участок маршрута A—B—D на A—D. Попробовав произвести все такие замены, получим, что маршрут A—B—D—E—F — самый короткий из тех, что удовлетворяют условию задачи.
Любое другое изменение пути, через которые проходит маршрут, приводит к увеличению его длины.
Ответ: 15.
3. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.
|
| A | B | C | D | E | F | G |
| A |
| 2 |
| 6 |
|
|
|
| B | 2 |
| 5 | 3 |
|
|
|
| C |
| 5 |
| 1 |
|
| 8 |
| D | 6 | 3 | 1 |
| 9 | 7 |
|
| E |
|
|
| 9 |
|
| 5 |
| F |
|
|
| 7 |
|
| 7 |
| G |
|
| 8 |
| 5 | 7 |
|
Определите длину кратчайшего пути между пунктами A и G. Передвигаться можно только по указанным дорогам.
Решение.
Найдём все варианты маршрутов из A в G и выберем самый короткий.
Из пункта A можно попасть в пункты B и D.
Из пункта B можно попасть в пункты C и D.
Из пункта C можно попасть в пункты D и G.
Из пункта D можно попасть в пункты E и F.
Из пункта E можно попасть в пункт G.
Из пункта F можно попасть в пункт G.
A−B−C−D−E−G. Длина маршрута 22.
A−B−C−D−F−G. Длина маршрута 22.
A−B−C−G. Длина маршрута 15.
A−B−D−E−G. Длина маршрута 19.
A−B−D−F−G. Длина маршрута 19.
A−D−F−G. Длина маршрута 20.
A−D−E−G. Длина маршрута 20.
A−B−D−С−G. Длина маршрута 14.
Кратчайший путь равен 14.
Ответ: 14.
4. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
|
| A | B | C | D | E | F | G |
| A |
| 2 |
| 6 |
|
|
|
| B | 2 |
| 5 | 2 |
|
|
|
| C |
| 5 |
| 4 |
|
| 8 |
| D | 6 | 2 | 4 |
| 2 | 7 |
|
| E |
|
|
| 2 |
|
| 5 |
| F |
|
|
| 7 |
|
| 7 |
| G |
|
| 8 |
| 5 | 7 |
|
Определите длину кратчайшего пути между пунктами A и G. Передвигаться можно только по указанным дорогам.
Решение.
Найдём все варианты маршрутов из A в G и выберем самый короткий.
Из пункта A можно попасть в пункты B и D.
Из пункта B можно попасть в пункты C и D.
Из пункта C можно попасть в пункты D и G.
Из пункта D можно попасть в пункты E и F.
Из пункта E можно попасть в пункт G.
Из пункта F можно попасть в пункт G.
A−B−C−D−E−G. Длина маршрута 18.
A−B−C−D−F−G. Длина маршрута 25.
A−B−C−G. Длина маршрута 15.
A−B−D−E−G. Длина маршрута 11.
A−B−D−F−G. Длина маршрута 18.
A−D−F−G. Длина маршрута 20.
A−D−E−G. Длина маршрута 13.
Кратчайший путь равен 11.
Ответ: 11.
5. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.
|
| A | B | C | D | E | F |
| A |
| 2 | 4 | 8 |
| 16 |
| B | 2 |
|
| 3 |
|
|
| C | 4 |
|
| 3 |
|
|
| D | 8 | 3 | 3 |
| 5 | 3 |
| E |
|
|
| 5 |
| 5 |
| F | 16 |
|
| 3 | 5 |
|
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.
Решение.
Найдём все варианты маршрутов, удовлетворяющих условию и выберем самый короткий.
A−D−E−F. Длина маршрута 18.
A−C−D−E−F. Длина маршрута 17.
Кратчайший путь равен 17.
Ответ: 17.
6. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице значает, что прямой дороги между пунктами нет.
|
| A | B | C | D | E | F |
| A |
| 2 | 4 | 8 |
| 16 |
| B | 2 |
|
| 3 |
|
|
| C | 4 |
|
| 3 |
|
|
| D | 8 | 3 | 3 |
| 2 | 3 |
| E |
|
|
| 2 |
| 5 |
| F | 16 |
|
| 3 | 5 |
|
Определите длину кратчайшего пути между пунктами A и F, проходящего через пункт E и не проходящего через пункт B. Передвигаться можно только по указанным дорогам.
Решение.
Найдём все варианты маршрутов, удовлетворяющих условию и выберем самый короткий.
A−C−D−E−F. Длина маршрута 14.
A−D−E−F. Длина маршрута 15.
Кратчайший путь равен 14.
Ответ: 14.
7. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
|
| A | B | C | D | E | F |
| A |
| 3 | 4 | 4 |
| 16 |
| B | 3 |
|
| 5 |
|
|
| C | 4 |
|
| 2 |
|
|
| D | 4 | 5 | 2 |
| 6 | 10 |
| E |
|
|
| 6 |
| 3 |
| F | 16 |
|
| 10 | 3 |
|
Определите длину кратчайшего пути между пунктами A и F при условии, что передвигаться можно только по указанным в таблице дорогам.
Решение.
Найдём все маршруты, удовлетворяющие условию, посчитаем расстояние и выберем кратчайшее.
A-B-D-F 18
A-B-D-E-F 17
A-C-D-F 16
A-C-D-E-F 15
A-D-F 14
A-D-E-F 13
A-F 16
Кратчайшим является A-D-E-F с длиной 13.
8. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
|
| A | B | C | D | E | F | G |
| A |
| 2 |
|
| 6 |
|
|
| B | 2 |
| 10 | 9 | 3 |
|
|
| C |
| 10 |
|
|
|
| 6 |
| D |
| 9 |
|
|
|
| 9 |
| E | 6 | 3 |
|
|
| 5 | 14 |
| F |
|
|
|
| 5 |
| 7 |
| G |
|
| 6 | 9 | 14 | 7 |
|
Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).
Решение.
Рассмотрим все возможные маршруты. Кратчайшим окажется A-B-E-F-G длиной 17
9. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
|
| A | B | C | D | E | F | G |
| A |
| 8 |
|
| 6 |
|
|
| B | 8 |
| 2 | 9 | 3 |
|
|
| C |
| 2 |
|
|
|
| 5 |
| D |
| 9 |
|
|
|
| 9 |
| E | 6 | 3 |
|
|
| 5 | 10 |
| F |
|
|
|
| 5 |
| 7 |
| G |
|
| 5 | 9 | 10 | 7 |
|
Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).
Решение.
Рассмотрим все возможные пути из А в G. Кратчайшим является A-B-C-G длиной 15.
10. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
|
| A | B | C | D | E | F |
| A |
| 2 | 4 | 8 |
| 16 |
| B | 2 |
|
| 3 |
|
|
| C | 4 |
|
| 3 |
|
|
| D | 8 | 3 | 3 |
| 2 | 5 |
| E |
|
|
| 2 |
| 2 |
| F | 16 |
|
| 5 | 2 |
|
Определите длину кратчайшего пути между пунктами A и F, не проходящего через пункт E. Передвигаться можно только по указанным дорогам.
Решение.
Рассмотрим все возможные маршруты из А в F, удовлетворяющие условию. Кратчайшим является A-B-D-F длиной 10.
11. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
|
| A | B | C | D | E | F |
| A |
| 7 | 4 | 8 |
| 16 |
| B | 7 |
|
| 3 |
|
|
| C | 4 |
|
| 3 |
|
|
| D | 8 | 3 | 3 |
| 2 | 3 |
| E |
|
|
| 2 |
| 5 |
| F | 16 |
|
| 3 | 5 |
|
Определите длину кратчайшего пути между пунктами A и F, не проходящего через пункт E. Передвигаться можно только по указанным дорогам.
Решение.
Рассмотрим все возможные пути. Кратчайшим окажется путь A-C-D-F длиной 10.
12. Между населенными пунктами A, B, C, D, E, F построены дороги, протяженность которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
|
| A | B | C | D | E | F |
| A |
| 6 | 10 |
| 3 | 14 |
| B | 6 |
|
|
|
| 7 |
| C | 10 |
|
| 2 | 5 | 3 |
| D |
|
| 2 |
| 4 |
|
| E | 3 |
| 5 | 4 |
|
|
| F | 14 | 7 | 3 |
|
|
|
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Решение.
Варианты маршрутов:
A-B-F. Длина маршрута 6 + 7 = 13
A-C-F. Длина маршрута 10 + 3 = 13
A-E-C-F. Длина маршрута 3 + 5 + 3 = 11
A-F. Длина маршрута 14
Видно, что кратчайший путь равен 11.
Ответ: 11.
13. Между населенными пунктами A, B, C, D, E, F построены дороги, протяженность которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.
|
| A | B | C | D | E | F |
| A |
| 4 | 7 | 11 |
| 16 |
| B | 4 |
|
| 6 | 5 |
|
| C | 7 |
|
|
|
| 9 |
| D | 11 | 6 |
|
| 3 |
|
| E |
| 5 |
| 3 |
| 4 |
| F | 16 |
| 9 |
| 4 |
|
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Решение.
Варианты маршрутов:
A-B-D-E-F. Длина маршрута 4 + 6 + 3 + 4 = 17
A-B-E-F. Длина маршрута 4 + 5 + 4 = 13
A-C-F. Длина маршрута 7 + 9 = 16
A-F. Длина маршрута 16
Видно, что кратчайший путь равен 13.
Ответ: 13.
14. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
|
| A | B | C | D | E | F |
| A |
|
| 3 |
|
|
|
| B |
|
| 9 |
| 4 |
|
| C | 3 | 9 |
| 3 | 8 |
|
| D |
|
| 3 |
| 2 |
|
| E |
| 4 | 8 | 2 |
| 7 |
| F |
|
|
|
| 7 |
|
Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
Решение.
Найдём все варианты маршрутов из A в F и выберем самый короткий.
В пункт F можно попасть только из пункта Е.
В пункт Е можно попасть из пунктов С, В и D.
В пункты В и D можно попасть только из пункта С.
В пункт С можно попасть только из пункта А.
A-C-E-F. Длина маршрута 3 + 8 + 7 = 18.
A-С-D-E-F. Длина маршрута 3 + 3 + 2 + 7 = 15.
A-С-B-E-F. Длина маршрута 3 + 9 + 4 + 7 = 23.
Видно, что кратчайший путь равен 15.
Поиск оптимального маршрута по таблице (43.79 KB)
0
178
5
Нравится
0
