вылезти из лабиринта

Question

Крыса помещается в лабиринт в неизвестном месте в лабиринте.

Все, что мы можем сделать, это идти вверх, вниз, вправо или влево. И у нас есть два метода:

• tryMove (), который возвращает false, если стена есть, и true, если мы можем двигаться.
• bool hasLadder (): возвращает true, если есть лестница, которую нужно убежать.

Мы должны написать функцию explore, которая возвращает true, если мы найдем выход, или false, если пути нет.

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

Answer 1

Для поиска как в ширину, так и в глубину требуется память, а простой алгоритм может зацикливаться бесконечно. Крыса, вероятно, имеет только O (1) памяти.

Один из способов решить эту проблему, не помня, где вы были, - это выбрать направление случайным образом. Время решения будет чрезвычайно долгим, но в конечном итоге оно должно достигать каждой достижимой площади. Это связано с 2D случайной прогулкой.

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

Answer 2

Алгоритм в основном USTCON (ненаправленная st-связность): учитывая ненаправленный граф G , определите, существует ли путь от узла s (начальная позиция крысы) к узлу т (выход).Эта проблема в классе сложности L , что означает, что для нее требуется логарифмический объем памяти .Так что, если у вас нет верхней границы размера лабиринта или вы не хотите приблизиться, это невозможно с постоянным пространством.

Answer 3

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

Answer 4

Забавно, что @mousey спрашивал о крысе ... anwyay.

Я уже видел эту проблему уже несколько раз.

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

Фактически, для каждого детерминированного порядка движений (например, 2L, 1R, 2L, 1R, ...) что я пытался (будучи в старшей школе, у меня было время) мы могли придумать лабиринт, который заставлял бы крысу бегать кругами.Конечно, чем сложнее цикл, тем сложнее лабиринт.

Поэтому, если у вас есть O (1) памяти, единственным выходом из лабиринта кажется случайное блуждание, как было предложеноМарк Байерс.К сожалению, вы не можете доказать, что невозможно выйти из лабиринта с помощью такого алгоритма.

С другой стороны, если у вас есть O (N) памяти, это сводится к созданию карты (каким-то образом).Стратегия, которую я наконец-то придумал, заключалась в том, чтобы оставить феромон (увеличивая счетчик) в каждом пройденном мной случае, и, когда у меня есть выбор в движении, выбирать среди наименее посещаемых случаев.Однако всегда можно было выбраться, поэтому мне никогда не приходилось думать о состоянии завершения в случае отсутствия выхода.

Вы также можете использовать алгоритм заливки ... Конечно, это было до того, как я узнало сроке БФС.Преимущество этого в том, что у вас есть условие завершения (когда не осталось ни одного случая для изучения).

Answer 5

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

Answer 6

Если я правильно помню, у меня было домашнее задание по рекурсии, как это давным-давно, однако оно не было ограничено O (1) памятью. Мы просто не могли построить «карты» того, где мы были, и должны были использовать рекурсию ... Я думаю, что это будет использовать память O (n), где n - кратчайшее расстояние до лестницы с начала.

while( 1 )
    {
    if( search( MOVE_LEFT, i ) ||
        search( MOVE_UP, i ) ||
        search( MOVE_RIGHT, i ) ||
        search( MOVE_DOWN, i ) )
         {
         return TRUE;
         }
    i++;
    }

/* recursive function */
bool search( move_type move, long int length )
{

doMove( move ); /* actually move the rat to requested place */

if( hasLadder() )
    return TRUE;

if( 0 == length )
    return FALSE;

switch( move ) /* check each and return rat to previous place */
    {
    case MOVE_LEFT:  
        if( tryMove( MOVE_LEFT ) && search( MOVE_LEFT, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_UP ) && search( MOVE_UP, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_DOWN ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;      
        doMove( MOVE_RIGHT ); break;
    case MOVE_UP:
        if( tryMove( MOVE_LEFT ) && search( MOVE_LEFT, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_UP ) && search( MOVE_UP, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_RIGHT ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE; 
        doMove( MOVE_DOWN ); break;
    case MOVE_RIGHT:
        if( tryMove( MOVE_UP ) && search( MOVE_UP, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_RIGHT ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_DOWN ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;      
        doMove( MOVE_LEFT ); break;
    case MOVE_DOWN:
        if( tryMove( MOVE_LEFT ) && search( MOVE_LEFT, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_RIGHT ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;
        if( tryMove( MOVE_DOWN ) && search( MOVE_RIGHT, length - 1 ) ) return TRUE;      
        doMove( MOVE_UP ); break;
    }

return FALSE;

}   /* search() */

Answer 7

Это классическая задача, часто используемая в качестве домашнего задания.

Попробуйте:

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

...

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

Answer 8

Вы должны запустить алгоритмы BFS.Единственная проблема, которую я вижу, это как определить график.Его можно определить с помощью окрестности фон Неймана .Узел определяется как пара X, Y.Псевдокод должен выглядеть следующим образом:

BFS
while (!Q.empty()){
    v = Q.top()
    neighbours = get_adj_list(v)
    foreach (w in neighbours){
        if (isWall(w) || isOutsideMaze(w)) skip
        if (isTerminal(w)) printPathAndExit
        if (dist[v] + 1 < dist[w])
            dist[w] = dist[v] + 1
            Q.push(w)
    }
}

GEN_NEIGHBOURS
dx = {-1,1}
dy = {-1,1}

get_adj_list(v)
    adj_list = []
    for (i in dx)
        for (j in dy)
            adj_list << node(v.x-i,v.y-j)
    return adj_list

РЕДАКТИРОВАТЬ : теперь я читаю ограничение памяти O (1).Поэтому я думаю, что вы должны следовать старому методу, чтобы всегда поворачивать направо, и в конечном итоге вы выйдете из лабиринта или вернетесь в исходное положение.

EDIT2 : из советов Corn Maze:

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