Полный обход неизвестного лабиринта

[Sonic86]

whitefox в сообщении #1017569 писал(а):

Всё дело в стеке, из-за него агент не может быть конечным.

А, понятно. Нет, в случае ограниченного агента стека нету.

[Skeptic]

Если граф неограничен, то время его обхода - бесконечно, и решение задачи не существует, т.к. его нельзя получить.

[Sender]

whitefox в сообщении #1017569 писал(а):

Всё дело в стеке, из-за него агент не может быть конечным.

Не нравится стек - в каждой вершине рисуйте на полу мелом стрелочку, куда возвращаться. Пометки в лабиринте - это и есть внешняя память. Вопрос в том, как обойтись общим объёмом памяти, ограниченным некоторой константой.

[whitefox]

Sender в сообщении #1017682 писал(а):

Не нравится стек - в каждой вершине рисуйте на полу мелом стрелочку, куда возвращаться.

Собственно, это и делает предложенная модификация Вашего алгоритма.

[Skeptic]

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

Можно уменьшить память, не используя стек, а помечая пройденные вершины специальным образом.
Имеем матрицу смежности графа. В ней вес каждой вершины равен 1. При посещении вершины в прямом направлении присваиваем ей в матрице смежности вес равный 2, при обратном движении - 3. Находясь в какой-либо вершине, можно продолжить путь только через вершины с весом 1, а возвращаться только через единственную вершину с весом 2.

[whitefox]

Skeptic в сообщении #1017842 писал(а):

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

Если я правильно понял ТС, то агент ничего не знает о графе, то есть $n$ ему не известно.

[Skeptic]

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

[Skeptic]

Можно, вообще, обойтись без дополнительной памяти, если обходить лабиринт, держась одной рукой за стенку, и не делая никаких пометок.

[Sender]

А теперь придумайте лабиринт, для которого этот метод не сработает.

[whitefox]

Skeptic в сообщении #1018281 писал(а):

Можно, вообще, обойтись без дополнительной памяти, если обходить лабиринт, держась одной рукой за стенку, и не делая никаких пометок.

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

[Alexu007]

Skeptic в сообщении #1018281 писал(а):

Можно, вообще, обойтись без дополнительной памяти, если обходить лабиринт, держась одной рукой за стенку, и не делая никаких пометок.

Хи-хи, в памяти компьютера нет стенок, за которые можно держаться руками.

[whitefox]

Alexu007 в сообщении #1018295 писал(а):

Хи-хи, в памяти компьютера нет стенок, за которые можно держаться руками.

Тут имеется ввиду, что множество соседей каждой вершины упорядочено. И если в текущую вершину пришли из $i$-го соседа, то дальше переходим в $(i+1)$-го, а из последнего соседа переходим в первого.