Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.144.124.232] |
|
Страницы: (2) 1 [2] все ( Перейти к последнему сообщению ) |
Сообщ.
#16
,
|
|
|
этот код мне понятен и закодировал его на C# (скажу больше, у меня было нечто подобное, только для хранения пути использовал очередь) namespace ConsoleApplication1 { class Program { public const int N = 7; // количество вершин в исходном графе public static int[,] ms = new int[N, N] // матрица смежности графа { {0, 0, 1, 0, 1, 1, 0}, {0, 0, 0, 0, 1, 0, 1}, {1, 0, 0, 0, 1, 1, 0}, {0, 0, 0, 0, 0, 0, 1}, {1, 1, 1, 0, 0, 1, 0}, {1, 0, 1, 0, 1, 0, 0}, {0, 1, 0, 1, 0, 0, 0} }; public static void AllDFS(int current, ref string path) // получение всех ДФС рекурсивно { if (path.Length == N) // если текущий путь ДФС готов, то выводим его Console.WriteLine(path); else { for(int j = 0; j < N; j++) // просматриваем всех соседей текущей вершины if (ms[current - 1, j] == 1) // сосед обнаружен { char ch = (char)(j + 1 + 48); // перевод номер вершины в символ, чтобы засунуть в строковый путь ДФС if (path.Contains(ch) == false) // если эта смежная вершина еще не попала в путь, то { path += (j + 1).ToString(); // добавляем ее к пути AllDFS(j + 1, ref path); // рекурсивный вызов, но в качестве текущей вершины уже выступает сосед } } } } static void Main(string[] args) { int start = 1; // исходная вершина для получения всех ДФС string path = null; // отвечает за путь ДФС path += start.ToString(); AllDFS(start, ref path); // получение всех возможныхх ДФС Console.ReadKey(); } } } Akina, а вот сейчас у меня к тебе огромный вопрос, т к именно в этом моменте возникает главная проблема! тут у тебя псевдокод на бэйсике и непонятно, как передается currentpath по ссылке или по значению! Вот смотри, допустим, если передача ПО ЗНАЧЕНИЮ, тогда будем иметь состояние этого пути в каждой версии рекурсии: 0 уровень: 1 1 уровень: 13 2 уровень: 135 3 уровень: 1352 4 уровень: 13527 5 уровень: 135274 и идти от вершины №4 некуда, поэтому эта версия рекурсии закроется и вернемся на 4-й уровень рекурсии и вершина №4 потеряна из пути. Затем закроется 4 уровень - потеряется 7 вершина и т.д. Т е передавать по значению этот путь НЕЛЬЗЯ, верно? Допустим, передача по ССЫЛКЕ, тогда получим: 0 уровень: 1 1 уровень: 13 2 уровень: 135 3 уровень: 1352 4 уровень: 13527 5 уровень: 135274 и идти от вершины №4 некуда, поэтому эта версия рекурсии закроется и вернемся на 4-й уровень рекурсии. Поскольку передача была по ссылке, то на уровне №4 currentpath = 135274. В конце концов добавится последняя вершина под №6 и первый правильный путь ДФС будет выведен на экран! Но возникла дикая проблема, т к путь нужно очищать (перестраивать хвост пути), а к этому моменту рекурсивные версии закрылись и на них не выйти повторно и непонятно, что делать. Вот именно эта проблема возникла у меня изначально, именно из-за нее создал этот пост. Или я не прав фундаментально здесь? |
Сообщ.
#17
,
|
|
|
Цитата FasterHarder @ тут у тебя псевдокод на бэйсике и непонятно, как передается currentpath по ссылке или по значению! Конечно, по значению. Иначе некуда будет возвращаться - для каждого уровня рекурсии должна существовать своя переменная path со своим значением... |
Сообщ.
#18
,
|
|
|
Цитата Akina @ Конечно, по значению. Иначе некуда будет возвращаться - для каждого уровня рекурсии должна существовать своя переменная path со своим значением... я же описал проблему, которая возникает в этом случае Цитата FasterHarder @ Вот смотри, допустим, если передача ПО ЗНАЧЕНИЮ, тогда будем иметь состояние этого пути в каждой версии рекурсии: 0 уровень: 1 1 уровень: 13 2 уровень: 135 3 уровень: 1352 4 уровень: 13527 5 уровень: 135274 и идти от вершины №4 некуда, поэтому эта версия рекурсии закроется и вернемся на 4-й уровень рекурсии и вершина №4 потеряна из пути. Затем закроется 4 уровень - потеряется 7 вершина и т.д. Т е передавать по значению этот путь НЕЛЬЗЯ, верно? и тогда НЕВОЗМОЖНО построить путь, если вершины нельзя в процессе ДФС соединить последовательно поясни, плиз этот момент, т к это узкое горлышко моего понимания всей задачи! |
Сообщ.
#19
,
|
|
|
На самом деле, как я уже писал, можно обойтись без копирования графа. Для этого надо вести "журнал" перемещений по графу, в который записывать изменения в нём. Так же не надо выбрасывать из него рёбра, достаточно иметь список входящих в текущее дерево вершин.
На шаге "поиска в глубину" в журнал пишется текущая вершина, ребро, по которому делается переход, вершина в которую произведён переход. Вершина, в которой мы оказались в результате перехода отмечается, как находящаяся в дереве. Если из текущей вершины нельзя сделать переход в ещё не отмеченную вершину, то производится возврат по переходам до вершины, из которой такой переход сделать можно. Если в результате возврата, мы оказались в исходной вершине и не смогли сделать переход, значит построение очередного дерева завершено - можно выписать номера рёбер. Далее начинается чистка журнала, операции журнала последовательно (с последней) отменяются, с вершин, помеченных на соответствующем шаге снимается пометка, и делается попытка сделать шаг по другому ребру. Если такой шаг сделать не удаётся чистится следующая запись и т.д. Как только сделать другой шаг удаётся, это будет новый вариант поиска в глубину. Если при чиске мы доходим до начальной записи и не можем сделать альтернативный шаг, значит больше обходов не существует. |
Сообщ.
#20
,
|
|
|
Цитата FasterHarder @ будем иметь состояние этого пути в каждой версии рекурсии Ты забываешь, что на каждом уровне рекурсии организуется перебор достижимых вершин: Цитата FasterHarder @ 0 уровень: 1 1 уровень: 13 2 уровень: 135 3 уровень: 1352 4 уровень: 13527 5 уровень: 135274 А на самом деле так: 0 уровень: 1, текущая 1, достижимые вершины 3,5,6 1 уровень: 1/13, текущая 3, достижимые вершины 1 (посещена),5,6 2 уровень: 1/13/35, текущая 5, достижимые вершины 1 (посещена), 2, 3 (посещена),6 3 уровень: 1/13/35/52, текущая 2, достижимые вершины 5 (посещена), 7 4 уровень: 1/13/35/52/27, текущая 7, достижимые вершины 2 (посещена), 4 5 уровень: 1/13/35/52/27/74 текущая 4, достижимые вершины 7 (посещена), достижимых непосещённых нет, возврат и поиск непосещённой вершины 6 уровень: 1/13/35/52/27/74, текущая 7, достижимые вершины 2 (посещена), 4 (посещена), достижимых непосещённых нет, возврат и поиск непосещённой вершины 6 уровень: 1/13/35/52/27/74, текущая 2, достижимые вершины 5 (посещена), 7 (посещена), достижимых непосещённых нет, возврат и поиск непосещённой вершины 6 уровень: 1/13/35/52/27/74, текущая 5, достижимые вершины 1 (посещена), 2 (посещена), 3 (посещена), 6 6 уровень: 1/13/35/52/27/74/56, текущая 6, длина пути == количество вершин == 7, печать пути ... 2 уровень: 1/13/35, текущая 5, достижимые вершины 1 (посещена), 2 (посещена), 3 (посещена),6 ... |
Сообщ.
#21
,
|
|
|
Mwa-ha-ha. Я почти сломал мозг, но, похоже, нашел решение (во всяком случае, граф из первого сообщения обрабатывается правильно). Причем без рекурсии (если не учитывать имитацию в виде стека).
Для хранения текущего состояния используется (помимо сгенерированного пути) стек точек ветвления и флаг "есть решение". Элемент стека содержит длину сгенерированного пути, позицию точки ветвления в этом пути и номер последней выбранной смежной вершины. 1. При заходе в вершину проверяем, все ли вершины уже посещены. Если да, то выставляем флаг "есть решение", выводим путь, восстанавливаем из стека точку ветвления. 2. Ищем смежные вершины, отсутствующие в пути и еще не выбранные. Если такие вершины есть, то обходим их по порядку: сбрасываем флаг "есть решение", кладем в стек текущую точку ветвления, добавляем выбранную вершину к пути и заходим в нее. 3. Если идти (больше) некуда, то: а) если стек пуст, то мы нашли все возможные пути, завершаем работу; б) если флаг "есть решение" сброшен (остались непосещенные вершины), то возвращаемся в предыдущую вершину пути, сам сгенерированный путь при этом не меняется; в) если флаг "есть решение" выставлен, то восстанавливаем из стека точку ветвления. В виде кода будет примерно так: <html> <body> <script> var vertices = 7 var firstVertex = 1 var incidence = { 1: {3: 1, 5: 1, 6: 1}, 2: {5: 1, 7: 1}, 3: {1: 1, 5: 1, 6: 1}, 4: {7: 1}, 5: {1: 1, 2: 1, 3: 1, 6: 1}, 6: {1: 1, 3: 1, 5: 1}, 7: {2: 1, 4: 1} } function walk(vertices, incidence, firstVertex) { var inPath = new Array(vertices) inPath[firstVertex] = true var path = [firstVertex] var stack = [] // [{pathLen, forkPos, takenVertex}] var forkPos = 0 var takenVertex = 0 var gotSolution = false var pushStack = function () { stack.push({pathLen: path.length, forkPos: forkPos, takenVertex: takenVertex}) forkPos = path.length path.push(takenVertex) inPath[takenVertex] = true takenVertex = 0 } var popStack = function () { var item = stack.pop() takenVertex = item.takenVertex + 1 forkPos = item.forkPos while (path.length > item.pathLen) { var i = path.pop() inPath[i] = false } } while (true) { if (path.length >= vertices) { gotSolution = true document.writeln(path.join() + '<br>') popStack() continue } var neighbours = incidence[path[forkPos]] while ((!neighbours[takenVertex] || inPath[takenVertex]) && takenVertex <= vertices) { takenVertex++ } if (takenVertex <= vertices) { pushStack() gotSolution = false continue } if (!stack.length) return if (gotSolution) { popStack() } else { forkPos-- takenVertex = 1 } } } walk(vertices, incidence, firstVertex) </script> </body> </html> |
Сообщ.
#22
,
|
|
|
Цитата Akina @ 4 уровень: 1/13/35/52/27, текущая 7, достижимые вершины 2 (посещена), 4 5 уровень: 1/13/35/52/27/74 текущая 4, достижимые вершины 7 (посещена), достижимых непосещённых нет, возврат и поиск непосещённой вершины вот, давай посмотрим на уровень №5, активная вершина №4 и идти от нее НЕКУДА и происходит ВОЗВРАТ, т е мы должны перейти на уровень №4, а не уровень №6 (ведь рекурсия начинает обратное движение, схлапывание). А чему равно значение path на уровне №4? Правильно, вот оно: Цитата Akina @ 4 уровень: 1/13/35/52/27 и ЧЕТВЕРКА ведь теряется! И до нее уже НЕ добраться в текущем обходе ДФС. или я не прав абсолютно? Добавлено я даже в отладчике посидел и там четко видно, что при обратном ходе path теряет хвост, что вообще не позволяет добиться состояние формирования полного ДФС, когда есть разрыв рекурсионный при обходе... |
Сообщ.
#23
,
|
|
|
Цитата FasterHarder @ при обратном ходе path теряет хвост, что вообще не позволяет добиться состояние формирования полного ДФС, когда есть разрыв рекурсионный при обходе... У тебя формируется разрывный путь. Поэтому на каждом витке рекурсии тебе надо рассматривать все непосещённые вершины, доступные из хотя бы одной из посещённых, а не просто все доступные из текущей. И соответственно то, что кончились узлы, доступные из текущей вершины, ещё не повод завершить уровень рекурсии. |
Сообщ.
#24
,
|
|
|
Akina, я, кажется понял и немного доделал программку и уже печатает частично правильно, НО, есть уточнения:
1. когда ты ссылаешься на текущую вершину, ведь она имеет статус посещенной? Как я понимаю, да 2. А зачем вообще передавать в рекурсию текущую вершину, если она записывается В КОНЕЦ пути. Ведь, если требуется перебрать всех непосещенных соседей для посещенных вершин, то ведь достаточно просмотреть все вершины от конца к началу, которые хранятся в пути и автоматически будет обработана и текущая, которая стоит в конце пути псевдокод: void Все_ДФС(string path) { если длина path равна кол-ву вершин графа, то вывести путь иначе просмотреть все вершины в переменной path от конца к началу просмотреть всех возможных непосещенных соседей текущей вершины если сосед не входит в путь, то { добавить соседа в конец пути вызов Все_ДФС(path) } } уже почти все понятно и почти все работает...ключевое слово почти... Добавлено и, кстати, дубликатные пути распечатываются иногда, но это так, к слову... |
Сообщ.
#25
,
|
|
|
Цитата FasterHarder @ А зачем вообще передавать в рекурсию текущую вершину, если она записывается В КОНЕЦ пути. Ну не передавай. Цитата FasterHarder @ дубликатные пути распечатываются иногда Трассировка в помощь. |
Сообщ.
#26
,
|
|
|
Как-то подобный вопрос уже поднимался, и я его решал. Код остался. Вот программка, которая печатает все пути в графе. Посмотри, возможно что-то из нее пригодится: #include <iostream> #include <vector> #include <map> typedef std::vector<uint> PathType; typedef std::map<uint,bool> VisType; typedef std::map<uint,std::vector<uint>> RelType; void PrintPath(uint I, PathType P, VisType V, RelType &R) { if (V.find(I) != V.end()) return; P.push_back(I); V[I]=true; for(const auto& x: P) std::cout << ":" << x; std::cout << std::endl; for(const auto& i: R[I]) PrintPath(i,P,V,R); } int main() { VisType Vis; PathType Path; RelType Rel = { {0,{1,5,6}}, {1,{0,2,6}}, {2,{1,3,6}}, {3,{2,4,6}}, {4,{3,5,6}}, {5,{0,4,6}}, {6,{0,1,2,3,4,5}} }; for(auto const& i:Rel) PrintPath(i.first,Path,Vis,Rel); } |