Партнерка на США и Канаду по недвижимости, выплаты в крипто
- 30% recurring commission
- Выплаты в USDT
- Вывод каждую неделю
- Комиссия до 5 лет за каждого referral
– последняя вершина 
, в к-рой закончился поиск в глубину, следовательно, – это корень некоторого глубинного дерева (и корень некоторой ССК). Любая вершина этого дерева достижима из на графе .
Проведем поиск в глубину на «транспонированном» графе 
, начав с вершины . Очевидно, что будет корнем некоторого глубинного дерева со мн-вом вершин 
.
Любая вершина 
будет достижима из на , т. е. достижима из 
на исходном графе .
Предположим, что 
такая вершина 
, что 
недостижима из на .
Тогда и должны принадлежать разным глубинным деревьям 
и 
на графе .
является максимальным среди значений 
, следовательно, построение началось и закончилось раньше, чем .
Но построение не может закончиться, пока не проверены связи всех его вершин, а достижима из , т. е. должна принадлежать – противоречие.
Следовательно, все вершины 
достижимы из и наоборот, т. е. – это мн-во вершин одной ССК.
При поиске в глубину на будем помещать все пройденные вершины в стек и отмечать, как проверенные.
После выделения (проверки всех связей вершины ) нужно вытолкнуть полученные вершины из стека и продолжить поиск в глубину, начиная с непроверенной вершины, имеющей максимальное значение . Очередное выделенное дерево будет содержать все вершины следующей ССК.
Таким образом, от графа будут последовательно «отщепляться» сильно связные компоненты.
Общая трудоемкость алгоритма составляет 
, если используются списки смежных вершин, или 
– для матрицы смежности.
Иллюстрация работы алгоритма поиска в глубину на графе . Вершины выбирались в порядке убывания значений : 
.
Выделено 3 ССК со мн-вами вершин: 
, 
, 
.
Комбинаторные алгоритмы
Исследуемые объекты представлены дискретными математическими структурами (мн-вами, графами,…).
Требуется найти ответ на вопросы типа:
- существует ли способ…
- сколько существует способов…
- найти все решения…
- найти лучшее (в смысле некоторого критерия) решение.
При этом обычно не существует аналитического решения и не заданы правила вычислений.
Задачи, требующие перебора вариантов решения – комбинаторные.
Общие условия:
- 
– множество элементов решения;
- решение 
, 
, 
– это обычно не просто множество, а комплекс, в котором важен порядок следования эл-тов 
;
- мн-во всех возможных вариантов решений 
(возможных комплексов эл-тов из 
) очень велико и не может быть построено целиком, поэтому все решения 
отыскиваются последовательно;
- не каждый вариант может оказаться решением задачи.
2 основных подхода к решению комбинаторных задач:
бэктрекинг и метод решета.
Бэктрекинг (поиск с возвратом)
Решение (полное) формируется рекурсивно на основе последовательности частичных решений
, 
,…, 
: при очередном рекурсивном вызове к текущему решению добавляется новый элемент – один из мн-ва допустимых.
Если из текущего решения 
невозможно построить никакое последующее 
(тупик) или уже является полным решением, то производится рекурсивный возврат к предыдущему частичному решению 
и выбирается следующий допустимый элемент 
.
Бэктрекинг позволяет перебрать все варианты полных решений без повторов.
Дерево решений для задачи, в к-рой любой элемент может входить в решение только 1 раз:
… 
… 
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 |
Основные порталы (построено редакторами)