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

    Можно пытаться рекурсивно "спускаться" по ребрам вглубь графа, добавляя новую вершину в какую-то структуру, когда кол-во элементов, например, в стеке равно кол-ву вершин, то принтить на экран текущий обход, но потом нужно "прыгнуть" на какой-то уровень рекурсии и формировать новый обход. Но тут возникли проблемы разного рода, которые быстро побороть не получилось.

    Как же получить все возможные обходы в глубину?

    Прикреплённая картинка
    Прикреплённая картинка

    Прикреплённая картинка
    Прикреплённая картинка
      Не совсем понятен критерий отбора путей. Если нужны все возможные обходы в глубину с разным порядком посещения вершин, то должны быть еще два варианта: 1532746 и 1562743 (вообще, хвост 274 ни на что не влияет, его можно обрубить до 2). Какова точная формулировка?
        Цитата AVA12 @
        1532746 и 1562743

        почему 1532746??!
        Идем из 1 в 5, потом из 5 в 3 и продолжаем идти ВГЛУБЬ, если есть такая возможность, т е из 3 в 6, а вот ПОТОМ уже во 2-ю!
        Ведь так ДФС работает или я чего-то недогоняю....
          Что-то я не понимаю, с чем возникли сложности... используйте стандартный алгоритм обхода в глубину, просто на каждом шаге перед выбором дополнительно избавляйтесь от рёбер, ведущих от текущего узла к уже посещённым. На алгоритм это никак не повлияет. Единственное - это сильно усложнит алгоритм, если использовать нерекурсивную версию, а в случае рекурсивной потребует передачи вниз по рекурсии копии очищенного графа и сохранения на текущем уровне неочищеной копии, если есть хотя бы одно удаляемое ребро.
          Сообщение отредактировано: Akina -
            Цитата Akina @
            ведущих от текущего узла к уже посещённым

            это понятно. Можно завести статус у вершины посещена/непосещена или добавлять посещенные вершины в стек/очередь и проверять "новую" вершину входит в стек/очередь или смотреть статус - тут вроде понятно!

            Цитата Akina @
            использовать нерекурсивную версию

            солидарен, т к без рекурсии будет тяжко...очень имхо, поэтому рассматриваем ТОЛЬКО рекурсивный вариант

            Цитата Akina @
            потребует передачи вниз по рекурсии копии очищенного графа и сохранения на текущем уровне неочищеной копии, если есть хотя бы одно удаляемое ребро

            тут пока не все ясно, буду разбираться и, я правильно понимаю, что если будет БОЛЬШЕ 1-й компоненты связности, то такой принцип не сработает? я просто пока разбираю на 1-й компоненте связности, а потом хотелось бы чтобы работало на любом кол-ве компонент связности...

            Цитата AVA12 @
            вообще, хвост 274 ни на что не влияет, его можно обрубить до 2

            ну, это только в этом примере такая топология
              Цитата FasterHarder @
              я правильно понимаю, что если будет БОЛЬШЕ 1-й компоненты связности, то такой принцип не сработает?

              С чего бы? Он универсален, т.к. определяется задачей.
                Akina я правильно понимаю, что окончание рекурсии будет момент, когда у стартовой вершины будут удалены все ребра, т е не будет возможности куда либо пойти?
                  Есссно. На этот критерий модификация не влияет. Только не удалены, а обойдены.
                  Сообщение отредактировано: Akina -
                    Цитата Akina @
                    это сильно усложнит алгоритм, если использовать нерекурсивную версию
                    Проще не избавляться от рёбер, а помечать посещённые вершины (каждое добавленное ребро добавляет также вершину, в которую оно пройдено) и пропускать рёбра, повторно ведущие в них. Тогда нерекурсивный алгоритм становится даже проще рекурсивного (по крайней мере требует меньше памяти).

                    От классической задачи обхода в глубину задача отличается тем, что приходится сохранять рёбра, по которым мы возвращаемся, чтобы продолжить поиск в другом направлении. При обычном обходе в глубину они забываются сразу.
                      Цитата Akina @
                      каждом шаге перед выбором дополнительно избавляйтесь от рёбер

                      т е ты говорил, что ребро не удаляется, а помечается как обойденное. Это нужно делать через матрицу смежности, да?
                      В нужной ячейке матрицы смежности менять 1 на 0?

                      Цитата Akina @
                      случае рекурсивной потребует передачи вниз по рекурсии копии очищенного графа и сохранения на текущем уровне неочищеной копии, если есть хотя бы одно удаляемое ребро.

                      хотел еще вот этот вариант обсудить
                      т е ввели стартовую вершину и вызываем рекурсивную функцию Получить_Все_ДФС.
                      Какие параметры она будет иметь?
                      1) матрица смежности для неочищенной копии
                      2) матрица смежности для очищенного графа
                      3) номер вершины, от которой происходит движение "вглубь" графа
                      ---------------------------------------------------------
                      т е всего три параметра, причем все они передаются НЕ по ссылке, а по значению, чтобы на каждом уровне рекурсии сохранялось состояние своей копии матрицы смежности (кстати в С, С++ массивы только передаются по ссылке и приходится их оборачивать в структуру, что добиться передачи по значению)? Точно не потребуется иметь стек/очередь какую-нибудь для запоминания чего-либо)

                      Цитата amk @
                      т классической задачи обхода в глубину задача отличается тем, что приходится сохранять рёбра, по которым мы возвращаемся, чтобы продолжить поиск в другом направлении. При обычном обходе в глубину они забываются сразу.

                      да, amk, ты очень точно диагностировал проблему, которая возникла, т к рекурсия при обходе ДФС имеет разрывы (прыгает с уровня на уровень), в отличие, например, от какого-нибудь дерева, где можно спускаться последовательно, начиная от корня...
                      Сообщение отредактировано: FasterHarder -
                        Цитата FasterHarder @
                        причем все они передаются НЕ по ссылке, а по значению, чтобы на каждом уровне рекурсии сохранялось состояние своей копии матрицы смежности

                        Именно. Ну то есть для экономии памяти можно делать это только когда было чего удалять, но нужность этого действа зависит от диаметра графа. Кстати, а какой он типичный? десятки, сотни, тысячи?
                          Цитата Akina @
                          Именно. Ну то есть для экономии памяти можно делать это только когда было чего удалять, но нужность этого действа зависит от диаметра графа. Кстати, а какой он типичный? десятки, сотни, тысячи?

                          вообще проблемы с памятью как бы нет, т е при решении этой задачки на это вообще можно НЕ обращать внимания.
                          рассматриваются не big graph, а графы с максимальным кол-вом вершин 10 штук. Но при этом могут быть связные графы (каждая вершина связана с каждой другой)
                          наверное, можно как-то используя комбинаторику посчитать максимально возможное кол-во обходов ДФС на связном графе с 10-ю вершинами, хотя я не знаю точно, как это сделать, может K = (n - 1)!/2, n = 10
                          но на память повторю, внимание можно не обращать как бы...

                          P.S. мне представляется большей проблемой, когда у графа будет больше 1-й компоненты связности...хотя тоже не уверен

                          Добавлено
                          Akina, что насчет описанных параметров?
                          я попробую написать псевдокод и показать, т к на данный момент многое непонятно остается и не вывезу решение дальше сам...
                            Цитата FasterHarder @
                            что насчет описанных параметров?

                            Перебор у тебя насчёт параметров. Передавать надо только текущее состояние графа и текущую вершину. Всё. Более того, граф можно хранить глобально, а передавать текущий полный путь - думаю, на каждом шаге на основе текущего пути строить список посещённых узлов будет не дороже, чем передавать его в готовом виде.
                              Цитата Akina @
                              граф можно хранить глобально

                              так, т е есть матрица смежности глобальной области видимости, поэтому толкать ее в ф-цию нет необходимости. Тут понятно.
                              Цитата Akina @
                              передавать текущий полный путь

                              вот тут не все ясно! для этого пути потребуется какая-то структура данных. Наверное, это будет очередь, которая запоминает номера вершин при обходе текущего ДФС. Я прав?

                              во-первых, как понять, что текущий ДФС сформирован и его пора выводить на экран? Кол-во элементов очереди должно стать равно кол-ву вершин исходного графа? Если да, то это понятно, как сделать и так я даже пытался уже делать, но не мог вернуться на нужный уровень рекурсии.

                              во-вторых, когда очередь распечатана, то нужно вернуться на развилочную вершину, чтобы пойти по-другому пути ДФС, но как ее найти, ведь она не последняя в очереди, как правило, а может быть где-то в середине, и пока до нее доберешься, то все промежуточные копии рекурсии будут закрыты/забыты (об этом коротко упомянул amk)

                              В общем это, я пока не догоняю основную идею такого перебора, хотя сам принцип построения ДФС вроде понимаю нормально...
                                Цитата FasterHarder @
                                для этого пути потребуется какая-то структура данных.

                                Какая структура? зачем? или массив посещённых вершин, или вообще UNC в стрингах.
                                Цитата FasterHarder @
                                как понять, что текущий ДФС сформирован и его пора выводить на экран?

                                Да элементарно - количество узлов в пути равно количеству узлов графа.
                                Цитата FasterHarder @
                                когда очередь распечатана, то нужно вернуться на развилочную вершину, чтобы пойти по-другому пути ДФС, но как ее найти

                                Да просто возврат из рекурсии. А там на каждом уровне уже организован for each по доступным вершинам, он сам разберётся, обрабатывать следующую вершину, или они кончились, и надо возвращаться.
                                Т.е.

                                ExpandedWrap disabled
                                  SUB recurse(currentpath, currentpoint)
                                  IF LENGTH(currentpath) = COUNT(points) THEN
                                      PRINT currentpath
                                  ELSE
                                      FOR EACH point IN (достижимые из currentpoint вершины, отсутствующие в currentpath)
                                          CALL recurse(currentpath + point, point)
                                      NEXT
                                  END IF
                                  END SUB
                                Сообщение отредактировано: Akina -
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0734 ]   [ 18 queries used ]   [ Generated: 28.03.24, 12:27 GMT ]