Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.190.207.144] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сразу переходим к графовому делу!
Вот условие задачи: дано около 20 топологий графа (две наиболее простых и понятных приведены на рисунке - "Звезда" и "Кольцо"). Используя методы грубой силы проверить заданный граф, например, на топологии "Звезда". Примечание: в коде запрещены ЛЮБЫЕ оптимизации/ускорения вычислений. Решать ТОЛЬКО методом грубой силы. Графы задаются матрицами смежностями. Прикреплённая картинка
----------------------------------------------------------------------- Данная задача привлекла тем, что здесь запрещено что-то оптимизировать (обычно все наоборот ) + есть некоторые вопросы по брут-форсАМ. Насколько понимаю, используя метод грубой силы, требуется перебрать ВСЕ ВОЗМОЖНЫЕ комбинации чего-либо (исчерпывающий перебор). момент №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 момент: при методах грубой силы стремится к циклам или рекурсии? (если отталкиваться от условия задачи этой) подскажите, как быть-то? спасибо за внимание |