Подтема 6 из 6 · дополнительный урок
Условие на число рёбер
Путь ровно из k рёбер, не меньше k или не больше k: у функции появляется второй параметр.
Второй параметр
Это дополнительный урок: такие задачи есть в подборках, а задачи основных подтем решаются без него. Нужен кратчайший путь из 6 в 100 ровно из двух рёбер. Хватит ли одного числа f(v) на вершину?
Нет: лучший остаток из вершины зависит от того, сколько рёбер ещё нужно пройти. Поэтому у функции второй параметр — f(v, k), длина кратчайшего пути из v в 100 ровно из k рёбер. Шаг по стрелке оставляет на одно ребро меньше. Когда рёбер не осталось, путь годится, только если мы в цели.
from functools import cache graph = {}for line in open("23.txt"): a, b, w = line.split() a, b, w = int(a), int(b), float(w) if a not in graph: graph[a] = [] graph[a].append((b, w)) @cachedef f(v, k): if k == 0: return 0 if v == 100 else float("inf") best = float("inf") for u, w in graph.get(v, []): best = min(best, w + f(u, k - 1)) return best print(f(1, 1), f(1, 2), f(1, 3))print(f(6, 2), f(6, 3))Из 6 ровно двумя рёбрами лучше всего 6 → 7 → 100 за 9.0, хотя кратчайший путь вообще — 6 → 1 → 7 → 100 за 8.5, из трёх рёбер. Значения f(v, k) для учебного графа:
| Вершина | k = 1 | k = 2 | k = 3 |
|---|---|---|---|
| 7 | 2.0 | ∞ | ∞ |
| 4 | 8.0 | ∞ | ∞ |
| 1 | 12.0 | 7.5 | ∞ |
| 6 | ∞ | 9.0 | 8.5 |
У вершины 1 теперь не одно число, а целая строка. Каждое значение собирается из столбца левее: f(1, 2) = min(5.5 + f(7, 1); 2.5 + f(4, 1)) = 7.5. @cache запоминает ответ для каждой пары (v, k).
Не больше и не меньше k
А если путь должен состоять не меньше чем из 3 рёбер? Или не больше чем из 2?
Перебрать все подходящие числа рёбер и взять лучшее: минимум f(v, j) по всем j из нужного диапазона. Сверху число рёбер ограничено: в графе без циклов ребро не повторяется, так что путь не длиннее числа строк в файле — 200.
print(min(f(6, j) for j in range(3, 201)))print(min(f(6, j) for j in range(1, 3)))Внутри min — : f(6, j) для каждого j из диапазона. Невозможные длины дают ∞ и минимум не портят. Если в файле больше строк, верхняя граница — их число плюс один.
Число путей из k рёбер
Сколько путей из 6 в 100 состоят ровно из 3 рёбер?
Подсчёт путей из подтемы 5 со вторым параметром: когда рёбер не осталось, путь засчитывается, только если мы в цели.
@cachedef count(v, k): if k == 0: return 1 if v == 100 else 0 total = 0 for u, w in graph.get(v, []): total += count(u, k - 1) return total print(count(6, 2), count(6, 3))print(sum(count(6, j) for j in range(1, 4)))Из двух рёбер — 6 → 7 → 100 и 6 → 1 → 100, из трёх — 6 → 1 → 7 → 100 и 6 → 1 → 4 → 100. Путей не больше чем из трёх рёбер — сумма по j от 1 до 3: 0 + 2 + 2 = 4.
Итого
- Ровно k рёберf(v, k): шаг по стрелке — k − 1
- k = 0, кратчайший путьв цели 0, в другой вершине ∞
- k = 0, число путейв цели 1, в другой вершине 0
- Не меньше / не большеmin или сумма по j из диапазона
- Верхняя границарёбер в пути не больше, чем строк в файле
Проверьте себя
Ответь сначала сам, потом открой ответ.
ОтветСкрыть ответ
ОтветСкрыть ответ
f(100, 1)? Почему не 0?ОтветСкрыть ответ
ОтветСкрыть ответ
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Путь ровно из двух рёбер
Граф задан рёбрами:
1 20 2.41 7 6.020 7 1.37 100 3.220 100 8.01 100 15.0Найди длину кратчайшего пути из 1 в 100, состоящего ровно из двух рёбер.
Введите длину — десятичную дробь через точку.
Подсказка
Из 1 в 100 двумя рёбрами можно пройти через 7 или через 20.
Решение
9.2: 1 → 7 → 100 стоит 6.0 + 3.2; 1 → 20 → 100 — 10.4.
Решение программой
from functools import cache EDGES = """1 20 2.41 7 6.020 7 1.37 100 3.220 100 8.01 100 15.0"""graph = {}for line in EDGES.splitlines(): a, b, w = line.split() a, b, w = int(a), int(b), float(w) if a not in graph: graph[a] = [] graph[a].append((b, w)) @cachedef f(v, k): if k == 0: return 0 if v == 100 else float("inf") best = float("inf") for u, w in graph.get(v, []): best = min(best, w + f(u, k - 1)) return best print(round(f(1, 2), 2))Ответ: 9.2
Ровно 10 рёбер
В текстовом файле 23-3.txt содержится описание ациклического ориентированного взвешенного графа: в каждой строке — номер начальной вершины ребра, номер конечной вершины и вес ребра; числа разделены пробелами и/или табуляциями. Найдите длину кратчайшего пути из вершины 1 в вершину 100, состоящего ровно из 10 рёбер. В ответ запишите целую часть найденной длины.
Введите целую часть найденной длины.
Подсказка
f(v, k) — кратчайший путь из v в 100 ровно из k рёбер.
Решение
7575: длина 7575.81.
Решение программой
from functools import cache graph = {}for line in open("23-3.txt"): a, b, w = line.split() a, b, w = int(a), int(b), float(w) if a not in graph: graph[a] = [] graph[a].append((b, w)) @cachedef f(v, k): if k == 0: return 0 if v == 100 else float("inf") best = float("inf") for u, w in graph.get(v, []): best = min(best, w + f(u, k - 1)) return best print(int(f(1, 10)))Ответ: 7575
Не меньше 20 рёбер
В текстовом файле 23-1.txt содержится описание ациклического ориентированного взвешенного графа: в каждой строке — номер начальной вершины ребра, номер конечной вершины и вес ребра; числа разделены пробелами и/или табуляциями. Найдите длину кратчайшего пути из вершины 1 в вершину 100, состоящего не менее чем из 20 рёбер. В ответ запишите целую часть найденной длины.
Введите целую часть найденной длины.
Подсказка
Минимум f(1, j) по j от 20 до 200: рёбер в пути не больше, чем строк в файле.
Решение
11557: лучший такой путь — ровно из 20 рёбер, 11557.14.
Решение программой
from functools import cache graph = {}for line in open("23-1.txt"): a, b, w = line.split() a, b, w = int(a), int(b), float(w) if a not in graph: graph[a] = [] graph[a].append((b, w)) @cachedef f(v, k): if k == 0: return 0 if v == 100 else float("inf") best = float("inf") for u, w in graph.get(v, []): best = min(best, w + f(u, k - 1)) return best print(int(min(f(1, j) for j in range(20, 201))))Ответ: 11557
Пути ровно из 5 рёбер
В текстовом файле 23-4.txt содержится описание ациклического ориентированного взвешенного графа: в каждой строке — номер начальной вершины ребра, номер конечной вершины и вес ребра; числа разделены пробелами и/или табуляциями. Определите количество различных путей из вершины 1 в вершину 100, содержащих ровно 5 рёбер.
Введите число.
Подсказка
count(v, k): когда рёбер не осталось, путь засчитывается только в цели.
Решение
22 пути.
Решение программой
from functools import cache graph = {}for line in open("23-4.txt"): a, b, w = line.split() a, b, w = int(a), int(b), float(w) if a not in graph: graph[a] = [] graph[a].append((b, w)) @cachedef count(v, k): if k == 0: return 1 if v == 100 else 0 total = 0 for u, w in graph.get(v, []): total += count(u, k - 1) return total print(count(1, 5))Ответ: 22
Пути не длиннее 6 рёбер
В текстовом файле 23-4.txt содержится описание ациклического ориентированного взвешенного графа: в каждой строке — номер начальной вершины ребра, номер конечной вершины и вес ребра; числа разделены пробелами и/или табуляциями. Определите количество различных путей из вершины 1 в вершину 100, содержащих не более 6 рёбер.
Введите число.
Подсказка
Сумма count(1, j) по j от 1 до 6.
Решение
64: путей из 3, 4, 5 и 6 рёбер — 1, 6, 22 и 35.
Решение программой
from functools import cache graph = {}for line in open("23-4.txt"): a, b, w = line.split() a, b, w = int(a), int(b), float(w) if a not in graph: graph[a] = [] graph[a].append((b, w)) @cachedef count(v, k): if k == 0: return 1 if v == 100 else 0 total = 0 for u, w in graph.get(v, []): total += count(u, k - 1) return total print(sum(count(1, j) for j in range(1, 7)))Ответ: 64