2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




На страницу Пред.  1, 2
 
 Re: Полный обход неизвестного лабиринта
Сообщение20.05.2015, 09:04 
whitefox в сообщении #1017569 писал(а):
Всё дело в стеке, из-за него агент не может быть конечным.
А, понятно. Нет, в случае ограниченного агента стека нету.

 
 
 
 Re: Полный обход неизвестного лабиринта
Сообщение20.05.2015, 09:17 
Если граф неограничен, то время его обхода - бесконечно, и решение задачи не существует, т.к. его нельзя получить.

 
 
 
 Re: Полный обход неизвестного лабиринта
Сообщение20.05.2015, 09:42 
whitefox в сообщении #1017569 писал(а):
Всё дело в стеке, из-за него агент не может быть конечным.

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

 
 
 
 Re: Полный обход неизвестного лабиринта
Сообщение20.05.2015, 12:40 
Аватара пользователя
Sender в сообщении #1017682 писал(а):
Не нравится стек - в каждой вершине рисуйте на полу мелом стрелочку, куда возвращаться.

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

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

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

 
 
 
 Re: Полный обход неизвестного лабиринта
Сообщение20.05.2015, 16:18 
Аватара пользователя
Skeptic в сообщении #1017842 писал(а):
Для любого ограниченного графа стек пройденного пути не может быть больше числа $n$ всех вершин. Т.е. стек всегда ограничен и его максимальная длина известна, она равна размерности графа.
Если я правильно понял ТС, то агент ничего не знает о графе, то есть $n$ ему не известно.

 
 
 
 Re: Полный обход неизвестного лабиринта
Сообщение21.05.2015, 15:30 
Я показал, что агенту не нужна собственная память, для этого можно писать "на стенах лабиринта".

 
 
 
 Re: Полный обход неизвестного лабиринта
Сообщение22.05.2015, 07:34 
Можно, вообще, обойтись без дополнительной памяти, если обходить лабиринт, держась одной рукой за стенку, и не делая никаких пометок.

 
 
 
 Re: Полный обход неизвестного лабиринта
Сообщение22.05.2015, 08:35 
А теперь придумайте лабиринт, для которого этот метод не сработает.

 
 
 
 Re: Полный обход неизвестного лабиринта
Сообщение22.05.2015, 08:41 
Аватара пользователя
Skeptic в сообщении #1018281 писал(а):
Можно, вообще, обойтись без дополнительной памяти, если обходить лабиринт, держась одной рукой за стенку, и не делая никаких пометок.

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

 
 
 
 Re: Полный обход неизвестного лабиринта
Сообщение22.05.2015, 08:48 
Skeptic в сообщении #1018281 писал(а):
Можно, вообще, обойтись без дополнительной памяти, если обходить лабиринт, держась одной рукой за стенку, и не делая никаких пометок.

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

 
 
 
 Re: Полный обход неизвестного лабиринта
Сообщение22.05.2015, 08:55 
Аватара пользователя
Alexu007 в сообщении #1018295 писал(а):
Хи-хи, в памяти компьютера нет стенок, за которые можно держаться руками.

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

 
 
 [ Сообщений: 27 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group