Считаем пути без перебора вслепую
В ориентированном ациклическом графе нет направленного возвращения в уже пройденную вершину по циклу.
В этом занятии
- Самостоятельно решить задачу по теме «Считаем пути без перебора вслепую» и объяснить проверку результата.
- Нарисуй DAG из пяти вершин, подпиши число путей от старта до каждой и проверь результат перечислением.
Пригодится: informatics9-graph-shortest
Разберёмся перед практикой+
Считаем пути без перебора вслепую
В ориентированном ациклическом графе нет направленного возвращения в уже пройденную вершину по циклу. Число путей от источника до вершины равно сумме чисел путей до её непосредственных предшественников. Источнику назначают одну исходную возможность.
Считать нужно в порядке, где все предшественники уже обработаны. Такой подсчёт нельзя без оговорок переносить на граф с циклом: повторные обходы могут создавать бесконечно много маршрутов. Уточняй, считаются ли пути с ограничениями и какие рёбра допустимы.
A→B, A→C, B→D, C→D. До B и C по одному пути, до D — 1+1=2.
- Проверь отсутствие циклов.
- Суммируй пути от уже обработанных предшественников.
Попробуй самостоятельно
Запиши рассуждения в черновик или сделай построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- Нарисуй DAG из пяти вершин, подпиши число путей от старта до каждой и проверь результат перечислением.
- Сначала предположи результат, затем проверь и объясни, что изменилось.
Источники и дальнейшее чтение
Материал изложен своими словами. Здесь можно проверить научные основания и подробнее изучить тему; часть источников — на английском.
Читай и разбирай пример в своём темпе. К практике можно перейти, когда будешь готов.