Задание 23 · Анализ графов
Практика и итог
Вся тема на одной странице: как решилась задача темы, главное из подтем, порядок решения и частые ошибки.
Одна задача — вся тема
Задача темы — кратчайший путь из 1 в 100 в графе из файла 23-5.txt — прошла через подтемы, и каждая добавляла к решению новый шаг. Пролистай черновик: точками отмечены строки, которых не было после предыдущей подтемы.
- Подтема 1, «Граф и путь»: ребро — строка, длина — сумма весов. Точками отмечены новые строки.
- Подтема 2, «Лучший путь до цели»: f(v) — через ответы соседей.
- Подтема 3, «Программа с @cache»: словарь рёбер и @cache.
- Подтема 4, «Условия на путь»: условие — разрез пути. Ответ задачи темы — 10211.
Функция f остаётся той же — вопрос меняет только три места в ней или её аргументы. Подтема 5 считает число путей, самый длинный путь и число рёбер, а дополнительный урок — пути ровно из k рёбер.
Карта темы
Каждая подтема дала одно правило функции, и любое решение собирается из них. Сверху — путь от файла к ответу, ниже — по блоку на подтему. Заголовок блока ведёт на подтему.
- Графсловарь: вершина → (куда, вес)
- Функцияf(v) через f соседей, @cache
- Ответf(1), целая часть в конце
1Граф и путь
- строка «a b w»ребро из a в b весом w, только в одну сторону
- длина путисумма весов, а не число рёбер
2Лучший путь до цели
- f(цели)0 — уже на месте
- f(v)min(вес + f(конца)) по стрелкам из v
- тупик∞, а не 0
3Программа с @cache
line.split()без аргумента — любые пробелы и табуляцииgraph.get(v, [])стрелки из v; у тупика пусто@cacheкаждая вершина считается один раз
4Условия на путь
- через kf(s, k) + f(k, t)
- в обход kв k вернуть ∞
- через ребро a → bf(s, a) + вес + f(b, t)
5Другие вопросы о путях
- число путейв цели 1, сумма вместо min
- самый длинныйmax, в тупике −∞
- число рёбервместо веса 1
6Условие на число рёбердополнительный урок
- f(v, k)путь ровно из k рёбер
Как решать
Любое задание 23 решается одним порядком из пяти шагов. Каждому шагу ты уже учился — под ним номера подтем:
Перед ответом выведи само число, а не только целую часть: так видно и бесконечность, и почти целую сумму вроде 4519.999999999998.
Частые ошибки
Шесть ошибок встречаются чаще других, и каждую ловит один вопрос к себе. Выбери ошибку — увидишь, как её исправить, и вопрос, который её ловит:
- тупик — ноль
- в тупике f = 0 →
float("inf"). Спроси себя: можно ли из этой вершины дойти до цели?подтема 2 - целая часть рано
- веса переведены в int при чтении → вес — float, int только от итоговой суммы. Спроси себя: не потерялись ли дробные части весов?подтема 3
- round вместо int
round(12.6)→int(12.6). Спроси себя: просят целую часть или округление?подтема 3- split(" ")
line.split(" ")→line.split(). Спроси себя: нет ли в строке двух пробелов или табуляции?подтема 3- нет @cache
- программа на файле не заканчивается → @cache над функцией. Спроси себя: не считается ли одна вершина много раз?подтема 3
- запрет в старой функции
- запрет добавили в уже вызванную f → для запрета — своя функция. Спроси себя: не вернёт ли @cache старые ответы?подтема 4
Итог
Тема пройдена: задача темы решена от ребра в строке до ответа 10211. Вот что взять с собой.
- ПорядокГраф, правило, края, вопрос, ответ.
- Правилоf(v) = min(вес + f(конца)), @cache.
- КраяВ цели 0, в тупике ∞.
- УсловияЧерез вершину — сумма двух f, в обход — ∞ в ней.
- Задача темыint(f(1)) = 10211; учебный граф — 7.5.
Проверьте себя
Ответь сначала сам, потом открой ответ.
Из вершины 5 выходят рёбра в 9 весом 2 и в 12 весом 7; f(9) = 10, f(12) = 4. Чему равно f(5)?
ОтветСкрыть ответ
min(2 + 10, 7 + 4) = 11.
Почему в тупике f = ∞, а не 0?
ОтветСкрыть ответ
0 значит «уже в цели». Из тупика до цели не дойти, и такой путь не должен победить в min.
Как найти кратчайший путь из 1 в 100 через вершину 4?
ОтветСкрыть ответ
f(1, 4) + f(4, 100): путь делится вершиной 4 на два независимых участка.
Нужно не длину пути, а число путей. Что меняется в функции?
ОтветСкрыть ответ
В цели 1 вместо 0, в тупике 0, а вместо min — сумма ответов соседей без весов.
Практика
Для проверки ответов нужен JavaScript. Условия, подсказки и решения доступны ниже.
Количество путей
В текстовом файле 23-4.txt содержится описание ациклического ориентированного взвешенного графа: в каждой строке — номер начальной вершины ребра, номер конечной вершины и вес ребра; числа разделены пробелами и/или табуляциями. Определите количество различных путей из вершины 1 в вершину 100.
Введите число.
Подсказка
В цели 1, в тупике 0, для остальных — сумма по соседям. Запоминай ответы.
Решение
227 путей.
Решение программой
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, t): if v == t: return 1 total = 0 for u, w in graph.get(v, []): total += count(u, t) return total print(count(1, 100))Ответ: 227
Кратчайший путь по файлу 23-3
В текстовом файле 23-3.txt содержится описание ациклического ориентированного взвешенного графа: в каждой строке — номер начальной вершины ребра, номер конечной вершины и вес ребра; числа разделены пробелами и/или табуляциями. Найдите длину кратчайшего пути из вершины 1 в вершину 100. В ответ запишите целую часть найденной длины.
Введите целую часть найденной длины.
Подсказка
Словарь из файла, f с @cache, целая часть в конце.
Решение
7393: длина 7393.88.
Решение программой
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, t): if v == t: return 0 best = float("inf") for u, w in graph.get(v, []): best = min(best, w + f(u, t)) return best print(int(f(1, 100)))Ответ: 7393
Путь без запрещённой вершины
В текстовом файле 23-5.txt содержится описание ациклического ориентированного взвешенного графа: в каждой строке — номер начальной вершины ребра, номер конечной вершины и вес ребра; числа разделены пробелами и/или табуляциями. Найдите длину кратчайшего пути из вершины 1 в вершину 100, не проходящего через вершину 722. В ответ запишите целую часть найденной длины.
Введите целую часть найденной длины.
Подсказка
Запрещённая вершина возвращает бесконечность — в отдельной функции.
Решение
10228.
Решение программой
from functools import cache graph = {}for line in open("23-5.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)) BAN = 722 @cachedef g(v, t): if v == BAN: return float("inf") if v == t: return 0 best = float("inf") for u, w in graph.get(v, []): best = min(best, w + g(u, t)) return best print(int(g(1, 100)))Ответ: 10228
Граф с тупиками
В текстовом файле 23-6.txt содержится описание ациклического ориентированного взвешенного графа: в каждой строке — номер начальной вершины ребра, номер конечной вершины и вес ребра; числа разделены пробелами и/или табуляциями. Найдите длину кратчайшего пути из вершины 1 в вершину 100. В ответ запишите целую часть найденной длины.
Введите целую часть найденной длины.
Подсказка
Тупик, из которого не дойти до цели, — бесконечность, а не ноль.
Решение
9257: длина 9257.03.
Решение программой
from functools import cache graph = {}for line in open("23-6.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, t): if v == t: return 0 best = float("inf") for u, w in graph.get(v, []): best = min(best, w + f(u, t)) return best print(int(f(1, 100)))Ответ: 9257
Путь через обязательную вершину
В текстовом файле 23-6.txt содержится описание ациклического ориентированного взвешенного графа: в каждой строке — номер начальной вершины ребра, номер конечной вершины и вес ребра; числа разделены пробелами и/или табуляциями. Найдите длину кратчайшего пути из вершины 1 в вершину 100, проходящего через вершину 429. В ответ запишите целую часть найденной длины.
Введите целую часть найденной длины.
Подсказка
Сумма минимумов двух участков.
Решение
9659.
Решение программой
from functools import cache graph = {}for line in open("23-6.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, t): if v == t: return 0 best = float("inf") for u, w in graph.get(v, []): best = min(best, w + f(u, t)) return best print(int(f(1, 429) + f(429, 100)))Ответ: 9659