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

[Sonic86]

Каков оптимальный алгоритм обхода неизвестного лабиринта?

Подробнее: пусть задан конечный связный граф $G$, выбрана какая-то вершина $v$. В ней находится агент. Агент может быть ограниченный или неограниченный (по памяти) (в литературе почему-то пишут "конечный"). Агент запоминает те вершины и ребра, по которым он прошел. Длины всех ребер равны 1. $L$ - сумма всех длин ребер графа (число ребер). $S=S(G,v)$ - максимальная длина пути, которую должен пройти агент, чтобы пройти все вершины (не ребра!). Интересует оценка $S$ через $L$ сверху.
Например, если граф известен, то $S\leqslant 2L$, т.к. выбирая и обходя покрывающее дерево, мы побываем во всех вершинах графа, обход делается за $2L-\epsilon$ шагов и эта оценка ясно неулучшаемая.
А вот если граф неизвестен, то я что-то не могу понять, какова оценка и не вижу оптимальный алгоритм, из которого тоже не могу найти оценку.

Нагуглил что-то такое: http://www.burdonov.ru/doctor/papers_2004/2/1.pdf
Но тут уже в аннотации утверждается, что известна оценка $S=O(Ln)$, где $n$ - число вершин. Мне эта оценка неочевидна. Откуда она следует или где она есть?

В CS не силен, литературу не читал. Буду рад, если тыкните в литературу.

[Sender]

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

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

[Geen]

Худший вариант, когда наш граф и есть дерево.
При этом, если требуется вернуться в исходную точку, мы пройдём каждое ребро дважды.
Если не требуется, то в худшем варианте мы можем сэкономить один проход по одному ребру (если последняя непроверенная ветка окажется единичной глубины).

[Sender]

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

[aa_dav]

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

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

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

[Sender]

Изначально речь шла о лабиринте. Я не думаю, что Минотавр стал бы афишировать своё местонахождение .

[aa_dav]

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

[Sonic86]

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

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

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

Sender, спасибо! Значит в общем случае $S\leqslant 2L$, и в статье что-то не то.
Путь обхода получается не совсем остовное дерево, либо остовное, но для графа, получаемого из $G$ растождествлением вершин по ребрам. Но все равно прекрасно!

Остается только случай ограниченного агента.

[Xaositect]

Там в статье надо обойти все вершины и все дуги, понятно, что получается больше.

[Sender]

Просмотрел статью, там рассматриваются ориентированные графы, для которых всё несколько сложнее - вернуться назад по тому же ребру не получится. А что понимается под ограниченным агентом? Сколько и чего он способен запомнить?

[Geen]

Sonic86 в сообщении #1015956 писал(а):

Остается только случай ограниченного агента.

А в этом случае вообще возникает вопрос остановки алгоритма....

[Sonic86]

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

А что понимается под ограниченным агентом? Сколько и чего он способен запомнить?

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

Geen в сообщении #1015979 писал(а):

А в этом случае вообще возникает вопрос остановки алгоритма....

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

[whitefox]

Sonic86 в сообщении #1015956 писал(а):

Остается только случай ограниченного агента.

Можно модифицировать алгоритм, предложенный Sender, так чтобы агент не использовал стек. Для этого достаточно по мере прохождения лабиринта помечать рёбра как "пройдено", "пройдено дважды".

1. Находясь в некоторой вершине, где раньше не были, помечаем её как посещённую, далее п.2.
2. Если находимся в вершине, где уже были, переходим по любому исходящему из неё не помеченному ребру, помечая его как "пройденное", далее п.3. Если таких рёбер нет, переходим по любому "пройденному" ребру, помечая его как "пройденное дважды", далее п.2; если же все рёбра "пройдены дважды", обход закончен.
3. Если при переходе по не помеченному ребру попали в ранее посещённую вершину, возвращаемся по этому же ребру обратно (при этом двойном проходе ребро становится "пройденным дважды"). Если же попали в вершину, ранее не посещавшуюся, переходим к п.1.

[Sonic86]

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

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

Не понимаю: число ребер графа не ограничено. (внешняя память не существует)

[whitefox]

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