Сообщение Re[3]: Поиск в глубину от 08.12.2016 10:27
Изменено 08.12.2016 10:28 Kernan
Здравствуйте, Qbit86, Вы писали:
Q>Здравствуйте, Kernan, Вы писали:
K>>Поиск в глбуину.
Q>Да, это примитив, который в любом случае будет необходим. Поиск в глубину, как ни странно, занимается не поиском, а построением леса и классификацией дуг. Каждый раз, когда встречаем back edge, это сигнал об обнаружении цикла.
Для непримитива недо теориме из ТГ смотреть и придумывать. Опять же, все наивные алгоритмы имеют просто неприличную алгоритмическую сложность в худшем случае.
Q>Здравствуйте, Kernan, Вы писали:
K>>Поиск в глбуину.
Q>Да, это примитив, который в любом случае будет необходим. Поиск в глубину, как ни странно, занимается не поиском, а построением леса и классификацией дуг. Каждый раз, когда встречаем back edge, это сигнал об обнаружении цикла.
Для непримитива недо теориме из ТГ смотреть и придумывать. Опять же, все наивные алгоритмы имеют просто неприличную алгоритмическую сложность в худшем случае.
Re[3]: Поиск в глубину
Здравствуйте, Qbit86, Вы писали:
Q>Здравствуйте, Kernan, Вы писали:
K>>Поиск в глбуину.
Q>Да, это примитив, который в любом случае будет необходим. Поиск в глубину, как ни странно, занимается не поиском, а построением леса и классификацией дуг. Каждый раз, когда встречаем back edge, это сигнал об обнаружении цикла.
Для непримитива надо теоримы из ТГ смотреть и придумывать что-то. Опять же, все наивные алгоритмы имеют просто неприличную алгоритмическую сложность в худшем случае.
Q>Здравствуйте, Kernan, Вы писали:
K>>Поиск в глбуину.
Q>Да, это примитив, который в любом случае будет необходим. Поиск в глубину, как ни странно, занимается не поиском, а построением леса и классификацией дуг. Каждый раз, когда встречаем back edge, это сигнал об обнаружении цикла.
Для непримитива надо теоримы из ТГ смотреть и придумывать что-то. Опять же, все наивные алгоритмы имеют просто неприличную алгоритмическую сложность в худшем случае.