Подсчет путей в ориентированном графе (задача 13)

Хотите готовиться со мной к ЕГЭ?
Пишите: ydkras@mail.ru
Немного обо мне.

В задаче 13 ЕГЭ по информатике требуется подсчитать число путей из одного узла в другой.

Вот типичная задача (заимствована из демонстрационного варианта ФИПИ по информатике 2022 г.):

"На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.Сколько существует различных путей из города А в город М, проходящих через город В?"

Как решать подобные задачи программным путем? Прежде всего надо уметь представлять информацию о графе в форме, удобной для компьютерной обработки. В языке Питон есть очень удобный тип данных для нашей цели: словарь или ассоциативный массив. Это совокупность пар "ключ-значение".

Сначала подготовим исходные данные для заполнения словаря. Создадим текстовый файл, строки которого устроены следующим образом: первая буква строки - это один из городов, а следующие буквы - список городов, в которые можно попасть из данного города.

Для данного графа файл будет таким:

АБВГД
БВЕ
ВЖЗ
ГВЗ
ДГЗ
ЕЖИ
ЖИ
ЗЖИ
ИКЛ
КМ
ЛМ
М

При составлении этого файла необходимо быть очень аккуратным, ничего не упустить и ничего не перепутать и, конечно, не употреблять латинские буквы вместо русских. Последняя строка говорит, что город М существует, но из него нет дорог. (Если мы опустим эту строку, то это может привести к ошибке выполнения в некоторых задачах.)

Напишем фрагмент программы, которая введет этот файл и создаст словарь. описывающий граф:

a={}
f=open('in.txt')
for s in f:
s=s.strip()
if len(s)>0: a[s[0]]=s[1:]

print(a)

Вначале создается пустой словарь (словари заключаются в фигурные скобки). Затем файл с описанием графа читается построчно, и первый символ строки используется как ключ, а остальные - как значение, соответствующее данному ключу. Добавление в словарь - это просто присваивание элементу словаря с некоторым ключом значения. Если такой элемент уже существует, то значение будет перезаписано, в противном случае будет создан новый элемент. Метод strip удаляет пробелы и символы конца строки в начале строки и её конце - это нужно, чтобы убрать символы конца строки. Проверка len(s)>0 нужна, чтобы не обрабатывать пустые строки (если они окажутся в файле, это вызовет обибку выполнения). Первый символ каждой строки, т.е. s[0], используется как ключ в словаре, а хвост строки (все символы, кроме первого) - как значение, связанное с этим ключом.

Для контроля распечатаем словарь:

{'А': 'БВГД', 'Б': 'ВЕ', 'В': 'ЖЗ', 'Г': 'ВЗ', 'Д': 'ГЗ', 'Е': 'ЖИ', 'Ж': 'И', 'З': 'ЖИ', 'И': 'КЛ', 'К': 'М', 'Л': 'М', 'М': ''}

Теперь всё готово для того, чтобы написать программу, которая ищет решение.

Простой случай - подсчёт количества путей

Сначала решим более протую задачу: подсчитаем число путей из А в М без каких-либо дополнительных ограничений.

Для этого напишем рекурсивную функцию ways:

def ways(start,end,karta):
    if start==end: return 1
    r=0
    for i in range(len(karta[start])): r += ways(karta[start][i],end,karta)
    return r

Функция подсчитывает число путей из города start в город end. Граф дорог задается в параметре karta, который должен быть словарем с описанной выше структурой.

Если значения start и end совпадают, то мы уже находимся в городе, в который должны попасть, и функция возвращает 1. Если же мы ещё не добрались до пункта назначения, то функция вызывает сама себя для каждого города, куда можно попасть из текущего города, и суммирует число путей из каждого города до конечного пункта.

Число путей из города А в город М - это результат вычисления функции ways('А','М',a). Разумеется, буквы 'А' и 'М' в параметрах функции должны быть русскими, а не латинскими.

Приведём программу полностью:

def ways(start,end,karta):
    if start==end: return 1
    r=0
    for i in range(len(karta[start])): r += ways(karta[start][i],end,karta)
    return r

a={}
f=open('in.txt')
for s in f:
    s=s.strip()
    if len(s)>0: a[s[0]]=s[1:]

print(ways('А','М',a))

Ограничения на маршрут: запрещенные города и города, обязательные для посещения

Выше был рассмотрен самый простой вариант задачи 13: подсчет числа путей без каких-либо ограничений. Но очень часто требуется считать лишь маршруты, которые проходят через какой-то город и/или не должны проходить через другой город.

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

Подсчитаем число маршрутов от А до В, а затем от В до М. Любой маршрут первого этапа можно комбинировать с маршрутом второго этапа, поэтому общее число маршрутов - это произведение числа маршрутов первого этапа на число маршрутов второго этапа. Таким образом, задача решается заменой последней строки в приведенной выше программе на строку

print(ways('А','В',a)*ways('В','М',a))

Если какой-то город запрещен для посещения, то можно найти сперва общее число маршрутов от начального пункта до конечного, затем - число маршрутов, которые проходят через данный город. Число маршрутов, которые не проходят через этот город, равно разности общего числа маршрутов и числа маршрутов, проходящих через данный город.

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

print(ways('А','М',a) - ways('А','В',a)*ways('В','М',a))

Другой способ рещения задачи с избегаемым городом - доработать нашу функцию ways, добавив в неё возможность исключать из рассмотрения определённые города.

Функция может выглядеть, например, так:

def ways(start,end,karta,zapret):
    if start in zapret: return 0
    if start==end: return 1
    r=0
    for i in range(len(karta[start])): r += ways(karta[start][i],end,karta,zapret)
    return r

В нее добавлен новый параметр zapret - это символьная строка, содержащая города, маршруты через которые не учитываются. Если символ start содержится в этой строке, то функция возвращает 0. Строка zapret может состоять более чем из одного символа: в этом случае будут учтены только те маршруты, которые не проходят через любой из городов, перечисленных в этой строке.

Число маршрутов из А в М, не проходящих через город В, можно найти так:

def ways(start,end,karta,zapret):
    if start in zapret: return 0
    if start==end: return 1
    r=0
    for i in range(len(karta[start])): r += ways(karta[start][i],end,karta,zapret)
    return r

a={}
f=open('in.txt')
for s in f:
    s=s.strip()
    if len(s)>0: a[s[0]]=s[1:]

print(ways('А','М',a,'В'))

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

print(ways('А','М',a,'')-ways('А','М',a,'В'))

(Если параметр zapret - это пустая строка, то ограничений на подсчет маршрутов нет.)

Обязательный и избегаемый города

Если требуется, чтобы маршрут обязательно проходил через какой-либо город и не проходил через другой, то можно решить задачу, разбив путь на два этапа, как было описано ранее. На каждом этапе мы задаем запрещенный город в параметре zapret.

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

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

В некоторых задачах ограничение формулируется примерно так: "сколько существует маршрутов, проходящих либо через город В, либо через город З, либо через оба эти города?" Решение простое: следует из общего числа маршрутов вычесто число маршрутов, которые не проходят ни через В, ни через З:

print(ways('А','М',a,'')-ways('А','М',a,'ВЗ'))

Ещё один вариант ограничения - найти число маршрутов, которые проходят либо через пункт В, либо через пункт З, но не через оба этих пункта одновременно. Можно сложить число маршрутов, проходящих через В и не проходящих через З, с числом маршрутов, проходящих через З и не проходящих через В. Можно также найти число маршрутов, проходящих дибо через В, либо через З, либо через В и З, а потом вычесть из него число маршрутов, проходящих как через В, так и через З.

Ограничения на длину маршрута

В некоторых задачах требуется, чтобы определенным ограничениям удовлетворяла и длина маршрута (т.е. количество городов, через которые проходит маршрут).

Так, вопрос может быть таким: "Сколько существует маршрутов из А в М, проходящих ровно через семь городов, считая А и М?"

Доработаем нашу функцию ways с тем, чтобы она хранила текущий маршрут. Дополним её новым параметром trassa, в котором будем хранить маршрут. Когда мы достигнем города назначения, то проверим длину маршрута. Если она такая, какая требуется, то мы засчитываем рашение (возвращаем 1), в противном случае - нет (возвращаем 0).

Вот полная программа, решающая эту задачу:

def ways(start,end,karta,zapret,trassa):
    trassa=trassa+start
    if start in zapret: return 0
    if start==end:
        if len(trassa)==7: return 1
        else: return 0
    r=0
    for i in range(len(karta[start])): r += ways(karta[start][i],end,karta,zapret,trassa)
    return r

a={}
f=open('in.txt')
for s in f:
    s=s.strip()
    if len(s)>0: a[s[0]]=s[1:]

print(ways('А','М',a,'',''))

Так как нам требовалась только длина маршрута, то можно было бы обойтись не строкой, а целой переменной. Но строка, хранящая маршрут, дает большую гибкость: можно, анализировать эту строку и, например, принимать только те маршруты, которые проходят по участку В-Ж. (if 'ВЖ' in trassa).

Самый длинный или самый короткий путь

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

Решим задачу нахождения длины самого длинного и самого короткого пути:

def ways(start,end,karta,zapret,trassa):
    global l,L
    trassa=trassa+start
    if start in zapret: return 0
    if start==end:
        if len(trassa)>L: L=len(trassa)
        if len(trassa)<l: l=len(trassa)
        return 1
    r=0
    for i in range(len(karta[start])): r += ways(karta[start][i],end,karta,zapret,trassa)
    return r

a={}
l=1000
L=0
f=open('in.txt')
for s in f:
    s=s.strip()
    if len(s)>0: a[s[0]]=s[1:]

print(ways('А','М',a,'',''))
print(l,L)

Команда global l,L в функции ways дает доступ к внешним переменным l и L, в которых вычисляется минимальная и blog/loadingмаксимальная длина пути.

Нужно обращать внимание на формулировку вопроса в задачах о длине пути. Данная программа вычисляет число городов, через который проходит путь, включая начальный и конечный города. Если же требуется найти число дорог, по которым надо проехать, то оно, очевидно, на единицу меньше числа городов. Так, данная программа дает ответ, что самый короткий путь содержит 6 городов, а самый длинный - 9. Соответственно, минимальное число дорог - это 5, а максимальное - 8.

Стоит ли овчинка выделки?

У дочитавших до этого места может возникнуть вопрос: а нужно ли всё это? Ведь такие задачи можно решать на листке бумаги. Автор не берется ответить на этот вопрос. Попробуйте найти ответ сами. Решите одну и ту же задачу вручную и на компьютере - и определите, какой способ будет для вас проще и быстрее. Удачи вам!

Поиск по этому блогу

Информатика, ЕГЭ, Питон и т.п.