Граф переходов
Граф переходов — это модель, в которой вершины изображают состояния объекта, а рёбра — возможные переходы между состояниями. Такая модель помогает систематически перебирать маршруты и считать, сколькими способами можно попасть из одного состояния в другое.
Как строят модель
Сначала определяют все существенные состояния: например, пункты маршрута, положения исполнителя или уже выполненные действия. Затем соединяют две вершины, если из одного состояния можно непосредственно перейти в другое. Направление стрелки должно совпадать с направлением перехода.
После построения модели задача сводится к поиску маршрутов из начальной вершины в конечную. Важно заранее понять, разрешено ли посещать вершины повторно и считаются ли различными маршруты, проходящие по разным рёбрам.
Подсчёт маршрутов
Если \(f(v)\) — число способов попасть из вершины \(v\) в конечную вершину, то для вершины, из которой выходят рёбра в \(u_1,u_2,\ldots,u_k\), используют правило:
Для конечной вершины обычно задают \(f(\text{финиш})=1\): это означает, что уже найден один завершённый маршрут. Затем значения передают назад по графу. Такой подход является основой подсчёта путей по графу.
Из состояния \(A\) можно перейти в \(B\) или \(C\). Из \(B\) есть один переход в финиш, а из \(C\) — два разных перехода в финиш. Тогда из \(B\) можно завершить маршрут одним способом, из \(C\) — двумя, а из \(A\) — \(1+2=3\) способами.
Граф переходов описывает возможные изменения состояния, а не обязательно физическую карту дорог. Поэтому две разные операции могут вести в одну и ту же вершину, а одно и то же состояние может достигаться разными маршрутами.
Вершина \(X\) ведёт в вершины \(Y\) и \(Z\). Из \(Y\) до финиша 2 маршрута, из \(Z\) — 3. Сколько маршрутов ведёт из \(X\) до финиша?
Главное
- Вершины графа переходов — состояния, рёбра — разрешённые переходы между ними.
- Для подсчёта маршрутов складывают количества способов продолжить путь по всем исходящим переходам.
- Направление переходов и правило повторного посещения вершин нужно учитывать явно.