Решение задачи: Пути из А в М через Ж (без Л)

Задание 5.

Определите количество различных путей из города А в город М, проходящих через город Ж и не проходящих через город Л.

Решение:

Для решения этой задачи будем последовательно подсчитывать количество путей до каждой вершины, начиная от города А. При этом будем учитывать условия: путь должен проходить через город Ж и не должен проходить через город Л.

1. Исключаем город Л: Все пути, проходящие через город Л, нам не подходят. На схеме видно, что город Л связан с городами И и М. Если мы не можем проходить через Л, то путь И-Л-М становится недоступным. Однако, есть прямой путь И-М. Также, если мы не можем проходить через Л, то это означает, что мы не можем использовать ребро И-Л и ребро Л-М. Таким образом, город Л просто игнорируется при подсчете путей.

2. Подсчитываем пути до города Ж: Сначала найдем количество путей из А в Ж, не проходящих через Л.

• А = 1 (начальная точка)
• Б = 1 (путь А-Б)
• Г = 1 (путь А-Г)
• Д = 1 (путь А-Д)
• В = Б + Г = 1 + 1 = 2 (пути А-Б-В, А-Г-В)
• Е = Б + В = 1 + 2 = 3 (пути А-Б-Е, А-Б-В-Е, А-Г-В-Е)
• З = Д + В = 1 + 2 = 3 (пути А-Д-З, А-Д-В-З, А-Г-В-З)
• Ж = Е + З = 3 + 3 = 6 (пути до Ж)

Итак, количество путей из А в Ж равно 6.

3. Подсчитываем пути из города Ж в город М: Теперь, из города Ж, нам нужно найти количество путей до города М, также не проходящих через город Л. Поскольку мы уже исключили город Л, просто продолжаем подсчет.

• Ж = 1 (теперь Ж - наша новая начальная точка для этого этапа)
• И = Ж = 1 (путь Ж-И)
• К = И = 1 (путь Ж-И-К)
• М = И + К = 1 + 1 = 2 (пути Ж-И-М, Ж-И-К-М)

Итак, количество путей из Ж в М равно 2.

4. Общее количество путей: Чтобы найти общее количество путей из А в М, проходящих через Ж и не проходящих через Л, нужно перемножить количество путей из А в Ж на количество путей из Ж в М.

Общее количество путей = (Пути А → Ж) * (Пути Ж → М) = 6 * 2 = 12.

Ответ: 12

Задание 6.

Используя метод динамического программирования, найдите кратчайшее расстояние между точками А и В. Заполните таблицу.

Решение:

Метод динамического программирования для нахождения кратчайшего пути заключается в том, что мы последовательно вычисляем кратчайшее расстояние до каждой вершины, начиная от стартовой точки А. Для каждой вершины мы выбираем минимальное значение из сумм расстояний до предыдущих вершин и весов ребер, ведущих к текущей вершине.

Будем заполнять таблицу, где каждая ячейка будет содержать кратчайшее расстояние от А до соответствующей точки.

Начнем с точки А. Расстояние от А до А равно 0.

Таблица для заполнения:

Представим сетку как матрицу, где (строка, столбец) обозначает позицию. Например, A находится в (4,1), B находится в (1,4).

Обозначим ячейки как \(C_{ij}\), где \(i\) - номер строки (сверху вниз, 1-4), \(j\) - номер столбца (слева направо, 1-4).

Исходные веса ребер:

(A) → (3) → (2) → (7)
(2) → (4) → (3) → (6)
(3) → (7) → (5) → (2)
(3) → (5) → (5) → (B)

Расчеты:

1. Начальная точка А: Расстояние до А = 0.

2. Первый ряд (снизу вверх, слева направо):

• Расстояние до (4,1) (A) = 0
• Расстояние до (4,2) = Расстояние до (4,1) + вес ребра (4,1)→(4,2) = 0 + 3 = 3
• Расстояние до (4,3) = Расстояние до (4,2) + вес ребра (4,2)→(4,3) = 3 + 2 = 5
• Расстояние до (4,4) = Расстояние до (4,3) + вес ребра (4,3)→(4,4) = 5 + 7 = 12

3. Второй ряд:

• Расстояние до (3,1) = Расстояние до (4,1) + вес ребра (4,1)→(3,1) = 0 + 2 = 2
• Расстояние до (3,2) = min(Расстояние до (3,1) + вес ребра (3,1)→(3,2), Расстояние до (4,2) + вес ребра (4,2)→(3,2)) = min(2 + 4, 3 + 4) = min(6, 7) = 6
• Расстояние до (3,3) = min(Расстояние до (3,2) + вес ребра (3,2)→(3,3), Расстояние до (4,3) + вес ребра (4,3)→(3,3)) = min(6 + 3, 5 + 3) = min(9, 8) = 8
• Расстояние до (3,4) = min(Расстояние до (3,3) + вес ребра (3,3)→(3,4), Расстояние до (4,4) + вес ребра (4,4)→(3,4)) = min(8 + 6, 12 + 6) = min(14, 18) = 14

4. Третий ряд:

• Расстояние до (2,1) = Расстояние до (3,1) + вес ребра (3,1)→(2,1) = 2 + 3 = 5
• Расстояние до (2,2) = min(Расстояние до (2,1) + вес ребра (2,1)→(2,2), Расстояние до (3,2) + вес ребра (3,2)→(2,2)) = min(5 + 7, 6 + 7) = min(12, 13) = 12
• Расстояние до (2,3) = min(Расстояние до (2,2) + вес ребра (2,2)→(2,3), Расстояние до (3,3) + вес ребра (3,3)→(2,3)) = min(12 + 5, 8 + 5) = min(17, 13) = 13
• Расстояние до (2,4) = min(Расстояние до (2,3) + вес ребра (2,3)→(2,4), Расстояние до (3,4) + вес ребра (3,4)→(2,4)) = min(13 + 2, 14 + 2) = min(15, 16) = 15

5. Четвертый ряд (до B):

• Расстояние до (1,1) = Расстояние до (2,1) + вес ребра (2,1)→(1,1) = 5 + 3 = 8
• Расстояние до (1,2) = min(Расстояние до (1,1) + вес ребра (1,1)→(1,2), Расстояние до (2,2) + вес ребра (2,2)→(1,2)) = min(8 + 5, 12 + 5) = min(13, 17) = 13
• Расстояние до (1,3) = min(Расстояние до (1,2) + вес ребра (1,2)→(1,3), Расстояние до (2,3) + вес ребра (2,3)→(1,3)) = min(13 + 5, 13 + 5) = min(18, 18) = 18
• Расстояние до (1,4) (B) = min(Расстояние до (1,3) + вес ребра (1,3)→(1,4), Расстояние до (2,4) + вес ребра (2,4)→(1,4)) = min(18 + B, 15 + B) Здесь B - это конечная точка, а не вес ребра. Вес ребра (1,3)→(1,4) равен 5, а вес ребра (2,4)→(1,4) равен 2. = min(18 + 5, 15 + 2) = min(23, 17) = 17

Заполненная таблица кратчайших расстояний:

Кратчайшее расстояние между точками А и В равно 17.

Ответ: Кратчайшее расстояние между точками А и В равно 17. Заполненная таблица приведена выше.