Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Решение (2 способ, через построение графа, М.В. Кузнецова)

1) Построим граф, соответствующий таблице. Наличие значений преимущественно на диагонали таблицы говорит о наличии дорог, последовательно связывающих указанные населенные пункты (A-B, B-C, …). Построение графа начнем с размещения узлов (населенных пунктов), располагая их «по кругу», а затем последовательно изобразим все указанные в таблице дороги. Так как нас интересует только число дорог, проходящих через 6 и более пунктов, то длины дорог (веса ребер) указывать не будем.

Из А исходит три дороги, но ясно, что дорога A-Z нас не интересует. Из B исходит одна дорога, из С - две…
Из D исходит три дороги, из Е – две. Из F выходят две дороги, причём одна возвращает в Е (рисуем новую стрелку, FE и EF – разные дороги).

2) Анализ графа.

Общее число пунктов 7. Есть дороги, последовательно связывающие все 7 пунктов, значит 1-й путь: ABCDEFZ.

Есть 3 дороги, которые позволяют «проехать мимо» соседнего пункта (AC идёт «мимо» B, DF – мимо E,…), значит, есть 3 способа проехать через 6 пунктов (AC DEFZ, ABC DF Z, ABCD EZ).

 

Есть одна «обратная дорога», позволяющая изменить порядок прохождения пунктов – FE. Эта дорога при наличии дороги DF, идущей «мимо» Е, создает дополнительные маршруты: один через 7 пунктов ABC DFE Z и один через 6 пунктов ACDFE Z.

 

3) Вывод: общее число дорог, соответствующих условию: 1+3+2=6

4) Ответ: 6

Ещё пример задания:

Р-04. Между населёнными пунктами A, B, C, D, E, F, G построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

  A B C D E F G
A              
B              
C              
D              
E              
F              
G              

Определите длину кратчайшего пути между пунктами A и G (при условии, что передвигаться можно только по построенным дорогам).

Решение:

9) начнём строить возможные маршруты из пункта A; за 1 шаг можно приехать в B, D или сразу в G (в скобках показаны длины маршрутов):

AB(5), AD(12), AG(25)

заметим, что G – это целевая точка (конечный пункт), поэтому мы уже имеем один полный маршрут длиной 25

10) строим двух шаговые маршруты: из B дальше можно ехать в D (возврат в А неинтересен!)

ABD (5 + 8 = 13)

этот маршрут нет смысла продолжать, поскольку в D можно приехать быстрее: длина уже найденного маршрута AD равна 12

11) из D можно ехать в B и C:

ADB (12 + 8 = 20)

ADC (12 + 2 = 14)

12) третий шаг: маршрут ADB продолжать бессмысленно: из B можно вернуться только в A и D

13) продолжаем маршрут ADC (14):

ADCE (14 + 4 = 18)

ADCF (14 + 5 = 19)

ADCG (14 + 10 = 24)

в последнем варианте мы приехали в конечный пункт, причем новый маршрут имеет длину 24 < 25, то есть, он короче найденного ранее

14) четвёртый шаг: продолжаем маршрут ADCE:

ADCEG (18 + 5 = 23)

и маршрут ADCF:

ADCFG (19 + 5 = 24)

15) других продолжений (без возврата в уже посещённые пункты) нет, поэтому кратчайший маршрут – ADCEG, он имеет длину 23.

16) Ответ: 23.

17) Заметим, что эти рассуждения можно зарисовать в виде дерева возможных маршрутов. После первого шага:

 

После второго шага:

После третьего шага:

 

После четвёртого шага:

 

 

Ещё пример задания:

Р-03. Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)

  A B C D E F
A            
B            
C            
D            
E            
F            

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Решение (вариант 1, использование схемы):

1) построим граф – схему, соответствующую этой весовой матрице; из вершины А можно проехать в вершины B и C (длины путей соответственно 2 и 4):

2) для остальных вершин можно рассматривать только часть таблицы над главной диагональю, которая выделена серым цветом; все остальные рёбра уже были рассмотрены ранее

3) например, из вершины В можно проехать в вершины C и E (длины путей соответственно 1 и 7):

4) новые маршруты из С – в D и E (длины путей соответственно 3 и 4):

5) новый маршрут из D – в E (длина пути 3):

6) новый маршрут из E – в F (длина пути 2):

7) нужно проехать из А в F, по схеме видим, что в любой из таких маршрутов входит ребро EF длиной 2; таким образом, остается найти оптимальный маршрут из A в E

8) попробуем перечислить возможные маршруты из А в Е:

А – В – Е длина 9

А – В – С – Е длина 7

А – В – C – D – Е длина 9

А –C – Е длина 8

А –C – B – Е длина 12

А –C – D – Е длина 10

9) из перечисленных маршрутов кратчайший – A-B-C-E – имеет длину 7, таким образов общая длина кратчайшего маршрута A-B-C-E-F равна 7 + 2 = 9

10) таким образом, правильный ответ – 9.

Решение (вариант 2, с начала маршрута):

1) составим граф, который показывает, куда (и как) можно ехать из пункта А, рядом с дугами будем записывать увеличение пути, а рядом с названиями пунктов – общую длину пути от пункта A:

2) видно, что напрямую в пункт F из A не доехать

3) строим граф возможных путей дальше: определяем, куда можно ехать из B и C (конечно, не возвращаясь обратно); из B можно ехать только в A (обратно), в C и в E;

4) узел C уже есть на схеме, и оказывается, что короче ехать в него по маршруту A-B-C, чем напрямую A-C, длина «окольного» пути составляет 3 вместо 4 для «прямого»;
при движении по дороге B-E длина увеличивается на 7:

5) строим маршруты из пункта C; кроме A и B, из пункта C можно ехать в D (длина 3) и E (длина 4), причем кратчайший маршрут из A в E оказывается A-B-C-E (длина 7); «невыгодные» маршруты на схеме показывать не будем:

6) из пункта D, кроме как в С и E, ехать некуда; путь D-C – это возврат назад (нас не интересует), путь D-E тоже не интересует, поскольку он дает длину 6 + 3 = 9, а мы уже нашли, что в E из A можно доехать по маршруту длины 7

7) из пункта E можно ехать в F, длина полного маршрута 7 + 2 = 9

8) Ответ: 9

Решение (вариант 3, с конца маршрута):

1) можно точно так же начинать с пункта F и искать кратчайший маршрут до A; судя по таблице, из F можно ехать только в E:

 

2) из E ведут дороги в B, C и D

3) из B можно сразу попасть в A, длина пути будет равна 11:

4) из пункта C есть прямая дорога в A длиной 4, таким образом, существует маршрут длиной
6 + 4 = 10

5) кроме того, есть дорога C-B, которая дает маршрут F-E-C-B-A длиной 9

6) рассмотрение пути C-D не позволяет улучшить результат: оптимальный маршрут имеет длину 9

7) Ответ: 9

Возможные ловушки и проблемы: · можно не заметить, что маршруты, проходящие через большее число пунктов, оказываются короче (A-B-C короче, чем A-C, A-B-C-E короче, чем A-B-E)

Ещё пример задания:

Р-02. Между четырьмя местными аэропортами: ОКТЯБРЬ, БЕРЕГ, КРАСНЫЙ и СОСНОВО, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:

Аэропорт вылета Аэропорт прилета Время вылета Время прилета

СОСНОВО КРАСНЫЙ 06:20 08:35

КРАСНЫЙ ОКТЯБРЬ 10:25 12:35

ОКТЯБРЬ КРАСНЫЙ 11:45 13:30

БЕРЕГ СОСНОВО 12:15 14:25

СОСНОВО ОКТЯБРЬ 12:45 16:35

КРАСНЫЙ СОСНОВО 13:15 15:40

ОКТЯБРЬ СОСНОВО 13:40 17:25

ОКТЯБРЬ БЕРЕГ 15:30 17:15

СОСНОВО БЕРЕГ 17:35 19:30

БЕРЕГ ОКТЯБРЬ 19:40 21:55

Путешественник оказался в аэропорту ОКТЯБРЬ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт СОСНОВО.

1) 15:40 2) 16:35 3)17:15 4) 17:25

Решение:

1) сначала заметим, что есть прямой рейс из аэропорта ОКТЯБРЬ в СОСНОВО с прибытием в 17:25:

ОКТЯБРЬ СОСНОВО 13:40 17:25

2) посмотрим, сможет ли путешественник оказаться в СОСНОВО раньше этого времени, если полетит через другой аэропорт, с пересадкой

3) можно лететь, через КРАСНЫЙ, но, как следует из расписания,

ОКТЯБРЬ КРАСНЫЙ 11:45 13:30

КРАСНЫЙ СОСНОВО 13:15 15:40

путешественник не успеет на рейс КРАСНЫЙ – СОСНОВО, который улетает в 13:15, то есть на 15 минут раньше, чем в КРАСНЫЙ прилетает самолет ОКТЯБРЬ – КРАСНЫЙ

4) можно лететь через БЕРЕГ,

БЕРЕГ СОСНОВО 12:15 14:25

ОКТЯБРЬ БЕРЕГ 15:30 17:15

но рейс БЕРЕГ – СОСНОВО вылетает даже раньше, чем рейс ОКТЯБРЬ – БЕРЕГ, то есть, пересадка не получится

5) поскольку даже перелеты с одной пересадкой не стыкуются по времени, проверять варианты с двумя пересадками в данной задаче бессмысленно (хотя в других задачах они теоретически могут дать правильное решение)

6) таким образом, правильный ответ – 4 (прямой рейс).

Возможные ловушки и проблемы: · можно не заметить, что путешественник не успеет на пересадку в КРАСНОМ (неверный ответ 15:40) · можно перепутать аэропорты вылета и прилета (неверный ответ 16:35)

Решение (вариант 2, граф):

1) для решения можно построить граф, показывающий, куда может попасть путешественник из аэропорта ОКТЯБРЬ

2) из аэропорта ОКТЯБРЬ есть три рейса:

ОКТЯБРЬ СОСНОВО 13:40 17:25

ОКТЯБРЬ КРАСНЫЙ 11:45 13:30

ОКТЯБРЬ БЕРЕГ 15:30 17:15

3) построим граф, около каждого пункта запишем время прибытия

4) проверим, не будет ли быстрее лететь с пересадкой: рейс «КРАСНЫЙ-СОСНОВО» вылетает в 13:15, то есть, путешественник на него не успевает; он не успеет также и на рейс «БЕРЕГ-СОСНОВО», вылетающий в 12:15

5) таким образом, правильный ответ – 4 (прямой рейс).

Еще пример задания:

Грунтовая дорога проходит последовательно через населенные пункты А, B, С и D. При этом длина дороги между А и В равна 80 км, между В и С – 50 км, и между С и D – 10 км. Между А и С построили новое асфальтовое шоссе длиной 40 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге – 20 км/час, по шоссе – 40 км/час.

1) 1 час 2) 1,5 часа 3)3,5 часа 4) 4 часа

Решение:

1) нарисуем схему дорог, обозначив данные в виде дроби (расстояние в числителе, скорость движения по дороге – в знаменателе):

2) разделив числитель на знаменатель, получим время движения по каждой дороге

3) ехать из А в B можно

· напрямую, это займет 4 часа, или …

· через пункт C, это займет 1 час по шоссе (из А в С) и 2,5 часа по грунтовой дороге
(из В в С), всего 1 + 2,5 = 3,5 часа

4) таким образом, правильный ответ – 3.

Возможные ловушки и проблемы: · можно не заметить, что требуется найти минимальное время поездки именно в В, а не в С (неверный ответ 1 час) · можно ограничиться рассмотрением только прямого пути из А в В и таким образом получить неверный ответ 4 часа · можно неправильно нарисовать схему

 

Еще пример задания:

Р-01. Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.

1) 2) 3) 4)
  A B C D Е
A          
B          
C          
D          
Е          

 

  A B C D Е
A          
B          
C          
D          
Е          

 

  A B C D Е
A          
B          
C          
D          
Е          

 

  A B C D Е
A          
B          
C          
D          
Е          

 

Решение (вариант 1):

1) нужно рассматривать все маршруты из А в В, как напрямую, так и через другие станции

2) рассмотрим таблицу 1:

· из верхней строки таблицы следует, что из А в В напрямую везти нельзя, только через C (стоимость перевозки А-С равна 3) или через D (стоимость перевозки из А в D равна 1)

  A B C D Е
A          

· предположим, что мы повезли через C; тогда из третьей строки видим, что из C можно ехать в В, и стоимость равна 4

  A B C D Е
C          

· таким образом общая стоимость перевозки из А через С в В равна 3 + 4 = 7

· кроме того, из С можно ехать не сразу в В, а сначала в Е:

  A B C D Е
C          

а затем из Е – в В (стоимость также 2),

  A B C D Е
Е          

так что общая стоимость этого маршрута равна 3 + 2 + 2 = 7

· теперь предположим, что мы поехали из А в D (стоимость 1); из четвертой строки таблицы видим, что из D можно ехать только обратно в А, поэтому этим путем в В никак не попасть:

  A B C D Е
D          

· таким образом, для первой таблицы минимальная стоимость перевозки между А и В равна 7; заданное условие «не больше 6» не выполняется

3) аналогично рассмотрим вторую схему; возможные маршруты из А в В:

· , стоимость 7

· , стоимость 7

· таким образом, минимальная стоимость 7, условие не выполняется

4) для третьей таблицы:

· , стоимость 7

· , стоимость 6

· , стоимость 7

· таким образом, минимальная стоимость 6, условие выполняется

5) для четвертой:

· , стоимость 9

· , стоимость 8

· минимальная стоимость 8, условие не выполняется

6) условие «не больше 6» выполняется только для таблицы 3

7) таким образом, правильный ответ – 3.

Возможные ловушки и проблемы: · метод ненагляден, легко запутаться и пропустить решение с минимальной стоимостью

Решение (вариант 2, с рисованием схемы):

1) для каждой таблицы нарисуем соответствующую ей схему дорог, обозначив стоимость перевозки рядом с линиями, соединяющими соседние станции:

1) 2) 3) 4)
  A B C D Е
A          
B          
C          
D          
Е          

 

  A B C D Е
A          
B          
C          
D          
Е          

 

  A B C D Е
A          
B          
C          
D          
Е          

 

  A B C D Е
A          
B          
C          
D          
Е          

 

2) теперь по схемам определяем кратчайшие маршруты для каждой таблицы:

1: или , стоимость 7

2: или , стоимость 7

3: , стоимость 6

4: , стоимость 8

8) условие «не больше 6» выполняется только для таблицы 3

9) таким образом, правильный ответ – 3.

Возможные ловушки и проблемы: · нужно внимательно строить схемы по таблицам, этот дополнительный переход (от табличных моделей к графическим) повышает наглядность, но добавляет еще одну возможность для ошибки · наглядность схемы зависит от того, как удачно вы выберете расположение ее узлов; один из подходов – сначала расставить все узлы равномерно на окружности, нарисовать все связи и посмотреть, как можно расположить узлы более удобно · по невнимательности можно пропустить решение с минимальной стоимостью

Еще пример задания [1]:

Р-00. Между четырьмя местными аэропортами: ВОСТОРГ, ЗАРЯ, ОЗЕРНЫЙ и ГОРКА, ежедневно выполняются авиарейсы. Приведён фрагмент расписания перелётов между ними:

Аэропорт вылета Аэропорт прилета Время вылета Время прилета

ВОСТОРГ ГОРКА 16:15 18:30

ОЗЕРНЫЙ ЗАРЯ 13:40 15:50

ОЗЕРНЫЙ ВОСТОРГ 14:10 16:20

ГОРКА ОЗЕРНЫЙ 17:05 19:20

ВОСТОРГ ОЗЕРНЫЙ 11:15 13:20

ЗАРЯ ОЗЕРНЫЙ 16:20 18:25

ВОСТОРГ ЗАРЯ 14:00 16:15

ЗАРЯ ГОРКА 16:05 18:15

ГОРКА ЗАРЯ 14:10 16:25

ОЗЕРНЫЙ ГОРКА 18:35 19:50

Путешественник оказался в аэропорту ВОСТОРГ в полночь (0:00). Определите самое раннее время, когда он может попасть в аэропорт ГОРКА.

1) 16:15 2) 18:15 3)18:30 4) 19:50

Решение («обратный ход»):

1) сначала заметим, что есть прямой рейс из аэропорта ВОСТОРГ в ГОРКУ с прибытием в 18:30:

ВОСТОРГ ГОРКА 16:15 18:30

2) посмотрим, сможет ли путешественник оказаться в ГОРКЕ раньше этого времени, если полетит через другой аэропорт, с пересадкой; рассмотрим все остальные рейсы, который прибывают в аэропорт ГОРКА:

ЗАРЯ ГОРКА 16:05 18:15

ОЗЕРНЫЙ ГОРКА 18:35 19:50

3) это значит, что имеет смысл проверить только возможность перелета через аэропорт ЗАРЯ (через ОЗЕРНЫЙ явно не получится раньше, чем прямым рейсом); для этого нужно быть в ЗАРЕ не позже, чем в 16:05

4) смотрим, какие рейсы прибывают в аэропорт ЗАРЯ раньше, чем в 16:05:

ОЗЕРНЫЙ ЗАРЯ 13:40 15:50

5) дальше проверяем рейсы, который приходят в ОЗЕРНЫЙ раньше, чем в 13:40

ВОСТОРГ ОЗЕРНЫЙ 11:15 13:20

6) таким образом, мы «пришли» от конечного пункта к начальному, в обратном направлении

7) поэтому оптимальный маршрут

8) и правильный ответ – 2.

Возможные ловушки и проблемы: · «напрашивается» ошибочный ответ 18:30 (прямой рейс) · при решении задачи «прямым ходом», с начального пункта, легко пропустить вариант с двумя пересадками

Задачи для тренировки [2]:

  A B C D
A        
B        
C        
D        

1) В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Укажите схему, соответствующую таблице.

 

 

1) 2) 3) 4)

2) В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пун­кты не соединены автомагистралями. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 5». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом любой населенный пункт должен встречаться на маршруте не более одного раза.

1) 2) 3) 4)
  A B C D
A        
B        
C        
D        

 

  A B C D
A        
B        
C        
D        

 

  A B C D
A        
B        
C        
D        

 

  A B C D
A        
B        
C        
D        

 

3) В таблице приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите таблицу, для которой выполняется условие «Минимальная стоимость перевозки грузов от пункта А до пункта В не больше 3».

1) 2) 3) 4)
  A B C D Е
A          
B          
C          
D          
Е          

 

  A B C D Е
A          
B          
C          
D          
Е          

 

  A B C D Е
A          
B          
C          
D          
Е          

 

  A B C D Е
A          
B          
C          
D          
Е          

 

 

  A B C D
A        
B        
C        
D        

 

4) В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.

 

 

1) 2) 3) 4)

5) В таблицах приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная стоимость перевозки грузов от пункта В до пункта D не больше 6».

1) 2) 3) 4)
  A B C D
A        
B        
C        
D        

 

  A B C D
A        
B        
C        
D        

 

  A B C D
A        
B        
C        
D        

 

  A B C D
A        
B        
C        
D        

 

 

  A B C D
A        
B        
C        
D        

 

6) В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.

 

 

1) 2) 3) 4)

7) В таблицах приведена протяженность автомагистралей между соседними населенными пунктами. Если пересечение строки и столбца пусто, то соответствующие населенные пункты не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная протяженность маршрута от пункта А до пункта С не больше 6». Протяженность маршрута складывается из протяженности автомагистралей между соответствующими соседними населенными пунктами. При этом через любой насеченный пункт маршрут должен проходить не более одного раза.

1) 2) 3) 4)
  A B C D
A        
B        
C        
D        

 

  A B C D
A        
B        
C        
D        

 

  A B C D
A        
B        
C        
D        

 

  A B C D
A        
B        
C        
D        

 

 

 

  A B C D E
A          
B          
C          
D          
E          

8) В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.

 

1) 2) 3) 4)

 

  A B C D E
A          
B          
C          
D          
E          

 

9) В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.

 

1) 2) 3) 4)
Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...