Граф Скоринг де ля Фер или исследование на тему кредитного скоринга, в рамках расширения кругозора. Ч.3
Часть третья, в которой Атос выпал в осадок, а Граф де ля Фер мудрит с алгоритмами.
UPD Часть первая здесь
UPD Часть вторая здесь
Вступление от авторов:
Добрый день! Сегодня мы продолжаем цикл статей, посвященных скорингу и использованию в оном теории графов. С первой и второй статьей Вы можете познакомиться соответственно здесь и здесь. Настоятельно рекомендуем, иначе, данная статья может показаться бессмысленным экспериментом с алгоритмами.
Все шуточные аллегории, вставки и прочее, призваны немного разгрузить повествование и не позволить ему свалиться в нудную лекцию. Всем, кому не зайдет наш юмор, заранее приносим извинения
Цель данной статьи: не более, чем за 30 минут, описать алгоритм построения графа и рассчитать скоринговый балл для НПАО «Один за всех».
Термины и определения:
- Алгоритм поиска в глубину (DFS, Depth-first search) — Стратегия поиска в глубину, как и следует из названия, состоит в том, чтобы идти «вглубь» графа, насколько это возможно. Алгоритм поиска описывается рекурсивно: перебираем все исходящие из рассматриваемой вершины рёбра. Если ребро ведёт в вершину, которая не была рассмотрена ранее, то запускаем алгоритм от этой нерассмотренной вершины, а после возвращаемся и продолжаем перебирать рёбра. Возврат происходит в том случае, если в рассматриваемой вершине не осталось рёбер, которые ведут в нерассмотренную вершину. Если после завершения алгоритма не все вершины были рассмотрены, то необходимо запустить алгоритм от одной из нерассмотренных вершин