Поиск с ограниченной глубиной - логика - как нам прекратить возвращаться назад?

Нужны некоторые логические советы. Я выполняю поиск с ограниченной глубиной, чтобы перейти из начального состояния в конечное. Я расширяю все возможные ходы от каждого узла, который на глубине> 0 включает в себя исходный узел (это проблема).

Я пытался сохранить предыдущие состояния и включить его в качестве условия не расширяться. Однако это также сводит на нет способность других ветвей расширения проходить через это состояние.

С логической точки зрения, как я могу избежать этой проблемы и в то же самое время избежать обратного торгования?

@acelent comment (здесь) дал мне идею создать класс configDepth, который будет хранить каждое посещенное состояние и его соответствующую глубину. Тогда в следующей рекурсии -

IF newState(depth) == state(depth-1) THEN !expand 

Что вы думаете об этом решении? Я спустился по многим тупикам и мне нужны свежие мнения и идеи.

Спасибо.

1 ответ

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

Для этого вам понадобится либо узнать вершины по глубине от создания дерева, либо вы можете просто вычислить их, когда вы спускаетесь с рекурсией.

Другие вопросы по тегам