Завершить итеративный поиск в глубину с углублением

На данный момент у меня есть объект, который выглядит примерно так.

C#
public class Step {
  int id;
  List<Step> nextSteps;
}

И я пытаюсь преобразовать его в другой объект, который выглядит очень похоже, за исключением того факта, что он не допускает циклов.

Он должен обрабатывать циклы, не расширяя дочерние узлы узлов, которые уже появились на более высокой глубине. Итеративное углубление решает эту проблему (реализация поиска в глубину, но порядок поиска в ширину), но я борюсь с реализацией, используя следующую структуру.

Все реализации, которые я нашел, основаны на поиске некоторого целевого узла, тогда как мне нужно развернуть все дерево.

Любая помощь будет оценена по достоинству. :D


c# depth-first-search iterative-deepening
person Phil    schedule 09.08.2011    source источник
comment
en.wikipedia.org/wiki/Depth-first_search#Pseudocode   -  person sehe    schedule 09.08.2011
comment
Хм, это не совсем помогает :(   -  person Phil    schedule 09.08.2011
comment
Хм... есть en.wikipedia.org/wiki/Breadth-first_search#Pseudocode< /а> тоже? Вы знаете, что они оба проходят весь граф (доступный из исходного узла) и не нацелены на конкретный узел? Если у вас есть «лес», просто продолжайте повторять все узлы, пока не останется невидимого узла, и вы получите лес деревьев, покрывающий весь граф.   -  person sehe    schedule 09.08.2011

Ответы (1)


arrow_upward
1
arrow_downward

Добавьте Dictionary<Step, int> и каждый раз, когда вы расширяете узел, добавляйте его с его глубиной.

void ExpandStep(Step s, int d)
{
    int prevDepth;
    if (lookup.TryGetValue(s, out prevDepth) && prevDepth <= d)
      return;
    lookup.Add(s, d);
    ... 
}
person Henk Holterman    schedule 09.08.2011
comment
Я думаю, что вы прочитали вопрос лучше, чем я. Я все еще не уверен, хотя - person sehe; 09.08.2011
comment
Просто спросите, будет ли это prevDepth ‹ d, как если бы узел был равен глубине, которую мы видели в последний раз, мы все равно должны его расширить? - person Phil; 09.08.2011
comment
Да, я предполагал, что каждый узел следует расширять только один раз. Если вы хотите повторно расшириться с того же уровня, используйте < d. Или даже > d, в зависимости от того, как считать, вверх или вниз. - person Henk Holterman; 09.08.2011
comment
Я сохраняю словарь с увеличением глубины, поэтому в нем будет глубина предыдущих циклов. - person Phil; 09.08.2011