На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> Метод грубой силы для обработки графов, Требование: никакой оптимизации, только брут-форс
    Всем хай! Сразу переходим к графовому делу!

    Вот условие задачи:
    дано около 20 топологий графа (две наиболее простых и понятных приведены на рисунке - "Звезда" и "Кольцо"). Используя методы грубой силы проверить заданный граф, например, на топологии "Звезда".
    Примечание: в коде запрещены ЛЮБЫЕ оптимизации/ускорения вычислений. Решать ТОЛЬКО методом грубой силы. Графы задаются матрицами смежностями.
    Прикреплённая картинка
    Прикреплённая картинка

    -----------------------------------------------------------------------
    Данная задача привлекла тем, что здесь запрещено что-то оптимизировать (обычно все наоборот :unsure: ) + есть некоторые вопросы по брут-форсАМ.

    Насколько понимаю, используя метод грубой силы, требуется перебрать ВСЕ ВОЗМОЖНЫЕ комбинации чего-либо (исчерпывающий перебор).
    момент №1: Например, проверка на "Звезду". Тут вроде брут-форс логичен.
    Вот пример на псевдокоде:
    ExpandedWrap disabled
      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 момент: при методах грубой силы стремится к циклам или рекурсии? (если отталкиваться от условия задачи этой)

    подскажите, как быть-то?
    спасибо за внимание
    Сообщение отредактировано: vot -
    1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
    0 пользователей:


    Рейтинг@Mail.ru
    [ Script execution time: 0,0384 ]   [ 16 queries used ]   [ Generated: 25.10.21, 04:01 GMT ]