2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Полный обход неизвестного лабиринта
Сообщение20.05.2015, 09:04 
Заслуженный участник


08/04/08
8556
whitefox в сообщении #1017569 писал(а):
Всё дело в стеке, из-за него агент не может быть конечным.
А, понятно. Нет, в случае ограниченного агента стека нету.

 Профиль  
                  
 
 Re: Полный обход неизвестного лабиринта
Сообщение20.05.2015, 09:17 


01/12/11

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

 Профиль  
                  
 
 Re: Полный обход неизвестного лабиринта
Сообщение20.05.2015, 09:42 


14/01/11
2916
whitefox в сообщении #1017569 писал(а):
Всё дело в стеке, из-за него агент не может быть конечным.

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

 Профиль  
                  
 
 Re: Полный обход неизвестного лабиринта
Сообщение20.05.2015, 12:40 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Sender в сообщении #1017682 писал(а):
Не нравится стек - в каждой вершине рисуйте на полу мелом стрелочку, куда возвращаться.

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

 Профиль  
                  
 
 Re: Полный обход неизвестного лабиринта
Сообщение20.05.2015, 15:47 


01/12/11

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

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

 Профиль  
                  
 
 Re: Полный обход неизвестного лабиринта
Сообщение20.05.2015, 16:18 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Skeptic в сообщении #1017842 писал(а):
Для любого ограниченного графа стек пройденного пути не может быть больше числа $n$ всех вершин. Т.е. стек всегда ограничен и его максимальная длина известна, она равна размерности графа.
Если я правильно понял ТС, то агент ничего не знает о графе, то есть $n$ ему не известно.

 Профиль  
                  
 
 Re: Полный обход неизвестного лабиринта
Сообщение21.05.2015, 15:30 


01/12/11

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

 Профиль  
                  
 
 Re: Полный обход неизвестного лабиринта
Сообщение22.05.2015, 07:34 


01/12/11

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

 Профиль  
                  
 
 Re: Полный обход неизвестного лабиринта
Сообщение22.05.2015, 08:35 


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

 Профиль  
                  
 
 Re: Полный обход неизвестного лабиринта
Сообщение22.05.2015, 08:41 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Skeptic в сообщении #1018281 писал(а):
Можно, вообще, обойтись без дополнительной памяти, если обходить лабиринт, держась одной рукой за стенку, и не делая никаких пометок.

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

 Профиль  
                  
 
 Re: Полный обход неизвестного лабиринта
Сообщение22.05.2015, 08:48 


24/05/09

2054
Skeptic в сообщении #1018281 писал(а):
Можно, вообще, обойтись без дополнительной памяти, если обходить лабиринт, держась одной рукой за стенку, и не делая никаких пометок.

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

 Профиль  
                  
 
 Re: Полный обход неизвестного лабиринта
Сообщение22.05.2015, 08:55 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Alexu007 в сообщении #1018295 писал(а):
Хи-хи, в памяти компьютера нет стенок, за которые можно держаться руками.

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу Пред.  1, 2

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group