Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=423102&view=findpost&p=3852158 Mon, 20 Sep 2021 14:10:17 +0000 Метод грубой силы для обработки графов https://forum.sources.ru/index.php?showtopic=423102&view=findpost&p=3852158
Вот условие задачи: дано около 20 топологий графа (две наиболее простых и понятных приведены на рисунке - "Звезда" и "Кольцо"). Используя методы грубой силы проверить заданный граф, например, на топологии "Звезда".
Примечание: в коде запрещены ЛЮБЫЕ оптимизации/ускорения вычислений. Решать ТОЛЬКО методом грубой силы. Графы задаются матрицами смежностями.
__________________.png (, : 225)
-----------------------------------------------------------------------
Данная задача привлекла тем, что здесь запрещено что-то оптимизировать (обычно все наоборот :unsure: ) + есть некоторые вопросы по брут-форсАМ.

Насколько понимаю, используя метод грубой силы, требуется перебрать ВСЕ ВОЗМОЖНЫЕ комбинации чего-либо (исчерпывающий перебор).
момент №1: Например, проверка на "Звезду". Тут вроде брут-форс логичен.
Вот пример на псевдокоде:
    k = 0       количество центров звезды (в результате должна быть 1)
     
    запустить перебор всех вершин
        если текущая вершина смежна со всеми остальными, то
        {
            запомнить ее номер (center)
            k увеличиваем на +1
            
            запустить перебор всех смежных с ней (center) вершин
                если смежная вершина соседствует не только с center, то
                {
                    k уменьшаем на 1
                    выход из внутреннего цикла (break)
                }
        }
            
    если k = 1, то
        да, это "Звезда"
    иначе
        нет, не "Звезда"

Сложность вроде O(n^2), где N - количество вершин. Это ведь брут-форс?)

2 момент: надо ли заканчивать брут-форс, если решение НАЙДЕНО?? Например, если делается подбор пароля и там 128 млрд. комбинаций и на 117 883 993 подборе пароль подошел. Брут-форс ПРЕКРАЩАЮТ (а зачем дальше работать, лол) ведь? С одной стороны пишут, что брут-форс делает ИСЧЕРПЫВАЮЩИЙ перебор, но ведь его и прекратить можно, если найдено решение, верно?

3 момент: брут-форс для "Кольца"
Берем произвольную вершину. У нее должна быть 2 соседа. Если не 2, то все, конец. Зачем дальше проверять?? Это уже НЕ кольцо. Т е брут-форс ОБРЫВАЕМ?? Если 2 соседа, то надо их проверять. Но их 2 и как бы разветвление идет, т е нужно задействовать контейнер для их хранения (очередь или еще что) и вообще это напоминает обход графа, допустим DFS, но ДФС ведь не брут-форс. С этим "кольцом" что-то неясно, к чему стремиться, чтобы именно КОНКРЕТНЫЙ брут-форс был.

4 момент: при методах грубой силы стремится к циклам или рекурсии? (если отталкиваться от условия задачи этой)

подскажите, как быть-то?
спасибо за внимание]]> FasterHarder Алгоритмы