Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.14.83.223] |
|
Страницы: (2) [1] 2 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Дан неориентированный граф, обладающий одной компонентой связности (т е из любой вершины можно попасть в любую другую без разрыва пути) (см.рис.). Дана стартовая вершина. В моем примере, это вершина №1. Нужно осуществить Depth-first search, но не простой! Нужно получить все возможные варианты обхода. На своем примере я насчитал 10 таких обходов. Красным цветом помечен "минимальный" обход, который я легко могу получить. Возникли проблемы с получением всех путей/обходов. Какие вспомогательные структуры данных помогут в этом: ну, типа стек, очередь, дек, ЛОС и т.п. Да, чуть не забыл, граф задается матрицей смежности, состоящей из 0 и 1. Петли в графе запрещены. Можно пытаться рекурсивно "спускаться" по ребрам вглубь графа, добавляя новую вершину в какую-то структуру, когда кол-во элементов, например, в стеке равно кол-ву вершин, то принтить на экран текущий обход, но потом нужно "прыгнуть" на какой-то уровень рекурсии и формировать новый обход. Но тут возникли проблемы разного рода, которые быстро побороть не получилось. Как же получить все возможные обходы в глубину? Прикреплённая картинка
Прикреплённая картинка
|
Сообщ.
#2
,
|
|
|
Не совсем понятен критерий отбора путей. Если нужны все возможные обходы в глубину с разным порядком посещения вершин, то должны быть еще два варианта: 1532746 и 1562743 (вообще, хвост 274 ни на что не влияет, его можно обрубить до 2). Какова точная формулировка?
|
Сообщ.
#3
,
|
|
|
Цитата AVA12 @ 1532746 и 1562743 почему 1532746??! Идем из 1 в 5, потом из 5 в 3 и продолжаем идти ВГЛУБЬ, если есть такая возможность, т е из 3 в 6, а вот ПОТОМ уже во 2-ю! Ведь так ДФС работает или я чего-то недогоняю.... |
Сообщ.
#4
,
|
|
|
Что-то я не понимаю, с чем возникли сложности... используйте стандартный алгоритм обхода в глубину, просто на каждом шаге перед выбором дополнительно избавляйтесь от рёбер, ведущих от текущего узла к уже посещённым. На алгоритм это никак не повлияет. Единственное - это сильно усложнит алгоритм, если использовать нерекурсивную версию, а в случае рекурсивной потребует передачи вниз по рекурсии копии очищенного графа и сохранения на текущем уровне неочищеной копии, если есть хотя бы одно удаляемое ребро.
|
Сообщ.
#5
,
|
|
|
Цитата Akina @ ведущих от текущего узла к уже посещённым это понятно. Можно завести статус у вершины посещена/непосещена или добавлять посещенные вершины в стек/очередь и проверять "новую" вершину входит в стек/очередь или смотреть статус - тут вроде понятно! Цитата Akina @ использовать нерекурсивную версию солидарен, т к без рекурсии будет тяжко...очень имхо, поэтому рассматриваем ТОЛЬКО рекурсивный вариант Цитата Akina @ потребует передачи вниз по рекурсии копии очищенного графа и сохранения на текущем уровне неочищеной копии, если есть хотя бы одно удаляемое ребро тут пока не все ясно, буду разбираться и, я правильно понимаю, что если будет БОЛЬШЕ 1-й компоненты связности, то такой принцип не сработает? я просто пока разбираю на 1-й компоненте связности, а потом хотелось бы чтобы работало на любом кол-ве компонент связности... Цитата AVA12 @ вообще, хвост 274 ни на что не влияет, его можно обрубить до 2 ну, это только в этом примере такая топология |
Сообщ.
#6
,
|
|
|
Цитата FasterHarder @ я правильно понимаю, что если будет БОЛЬШЕ 1-й компоненты связности, то такой принцип не сработает? С чего бы? Он универсален, т.к. определяется задачей. |
Сообщ.
#7
,
|
|
|
Akina я правильно понимаю, что окончание рекурсии будет момент, когда у стартовой вершины будут удалены все ребра, т е не будет возможности куда либо пойти?
|
Сообщ.
#8
,
|
|
|
Есссно. На этот критерий модификация не влияет. Только не удалены, а обойдены.
|
Сообщ.
#9
,
|
|
|
Цитата Akina @ Проще не избавляться от рёбер, а помечать посещённые вершины (каждое добавленное ребро добавляет также вершину, в которую оно пройдено) и пропускать рёбра, повторно ведущие в них. Тогда нерекурсивный алгоритм становится даже проще рекурсивного (по крайней мере требует меньше памяти).это сильно усложнит алгоритм, если использовать нерекурсивную версию От классической задачи обхода в глубину задача отличается тем, что приходится сохранять рёбра, по которым мы возвращаемся, чтобы продолжить поиск в другом направлении. При обычном обходе в глубину они забываются сразу. |
Сообщ.
#10
,
|
|
|
Цитата Akina @ каждом шаге перед выбором дополнительно избавляйтесь от рёбер т е ты говорил, что ребро не удаляется, а помечается как обойденное. Это нужно делать через матрицу смежности, да? В нужной ячейке матрицы смежности менять 1 на 0? Цитата Akina @ случае рекурсивной потребует передачи вниз по рекурсии копии очищенного графа и сохранения на текущем уровне неочищеной копии, если есть хотя бы одно удаляемое ребро. хотел еще вот этот вариант обсудить т е ввели стартовую вершину и вызываем рекурсивную функцию Получить_Все_ДФС. Какие параметры она будет иметь? 1) матрица смежности для неочищенной копии 2) матрица смежности для очищенного графа 3) номер вершины, от которой происходит движение "вглубь" графа --------------------------------------------------------- т е всего три параметра, причем все они передаются НЕ по ссылке, а по значению, чтобы на каждом уровне рекурсии сохранялось состояние своей копии матрицы смежности (кстати в С, С++ массивы только передаются по ссылке и приходится их оборачивать в структуру, что добиться передачи по значению)? Точно не потребуется иметь стек/очередь какую-нибудь для запоминания чего-либо) Цитата amk @ т классической задачи обхода в глубину задача отличается тем, что приходится сохранять рёбра, по которым мы возвращаемся, чтобы продолжить поиск в другом направлении. При обычном обходе в глубину они забываются сразу. да, amk, ты очень точно диагностировал проблему, которая возникла, т к рекурсия при обходе ДФС имеет разрывы (прыгает с уровня на уровень), в отличие, например, от какого-нибудь дерева, где можно спускаться последовательно, начиная от корня... |
Сообщ.
#11
,
|
|
|
Цитата FasterHarder @ причем все они передаются НЕ по ссылке, а по значению, чтобы на каждом уровне рекурсии сохранялось состояние своей копии матрицы смежности Именно. Ну то есть для экономии памяти можно делать это только когда было чего удалять, но нужность этого действа зависит от диаметра графа. Кстати, а какой он типичный? десятки, сотни, тысячи? |
Сообщ.
#12
,
|
|
|
Цитата Akina @ Именно. Ну то есть для экономии памяти можно делать это только когда было чего удалять, но нужность этого действа зависит от диаметра графа. Кстати, а какой он типичный? десятки, сотни, тысячи? вообще проблемы с памятью как бы нет, т е при решении этой задачки на это вообще можно НЕ обращать внимания. рассматриваются не big graph, а графы с максимальным кол-вом вершин 10 штук. Но при этом могут быть связные графы (каждая вершина связана с каждой другой) наверное, можно как-то используя комбинаторику посчитать максимально возможное кол-во обходов ДФС на связном графе с 10-ю вершинами, хотя я не знаю точно, как это сделать, может K = (n - 1)!/2, n = 10 но на память повторю, внимание можно не обращать как бы... P.S. мне представляется большей проблемой, когда у графа будет больше 1-й компоненты связности...хотя тоже не уверен Добавлено Akina, что насчет описанных параметров? я попробую написать псевдокод и показать, т к на данный момент многое непонятно остается и не вывезу решение дальше сам... |
Сообщ.
#13
,
|
|
|
Цитата FasterHarder @ что насчет описанных параметров? Перебор у тебя насчёт параметров. Передавать надо только текущее состояние графа и текущую вершину. Всё. Более того, граф можно хранить глобально, а передавать текущий полный путь - думаю, на каждом шаге на основе текущего пути строить список посещённых узлов будет не дороже, чем передавать его в готовом виде. |
Сообщ.
#14
,
|
|
|
Цитата Akina @ граф можно хранить глобально так, т е есть матрица смежности глобальной области видимости, поэтому толкать ее в ф-цию нет необходимости. Тут понятно. Цитата Akina @ передавать текущий полный путь вот тут не все ясно! для этого пути потребуется какая-то структура данных. Наверное, это будет очередь, которая запоминает номера вершин при обходе текущего ДФС. Я прав? во-первых, как понять, что текущий ДФС сформирован и его пора выводить на экран? Кол-во элементов очереди должно стать равно кол-ву вершин исходного графа? Если да, то это понятно, как сделать и так я даже пытался уже делать, но не мог вернуться на нужный уровень рекурсии. во-вторых, когда очередь распечатана, то нужно вернуться на развилочную вершину, чтобы пойти по-другому пути ДФС, но как ее найти, ведь она не последняя в очереди, как правило, а может быть где-то в середине, и пока до нее доберешься, то все промежуточные копии рекурсии будут закрыты/забыты (об этом коротко упомянул amk) В общем это, я пока не догоняю основную идею такого перебора, хотя сам принцип построения ДФС вроде понимаю нормально... |
Сообщ.
#15
,
|
|
|
Цитата FasterHarder @ для этого пути потребуется какая-то структура данных. Какая структура? зачем? или массив посещённых вершин, или вообще UNC в стрингах. Цитата FasterHarder @ как понять, что текущий ДФС сформирован и его пора выводить на экран? Да элементарно - количество узлов в пути равно количеству узлов графа. Цитата FasterHarder @ когда очередь распечатана, то нужно вернуться на развилочную вершину, чтобы пойти по-другому пути ДФС, но как ее найти Да просто возврат из рекурсии. А там на каждом уровне уже организован for each по доступным вершинам, он сам разберётся, обрабатывать следующую вершину, или они кончились, и надо возвращаться. Т.е. 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 |