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

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

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

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

Попробуйте следующее:

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

...

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

Вам следует запускать алгоритмы 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). Так что я думаю, вам следует следовать старому методу: всегда поворачивать вправо, и в конечном итоге вы выйдете из лабиринта или вернетесь в исходное положение.

РЕДАКТИРОВАТЬ2 : из советов по кукурузному лабиринту:

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

Если я правильно помню, у меня было подобное домашнее задание по рекурсии давным-давно, однако оно не ограничивалось 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() */

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

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

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

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

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

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

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

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

http://en.wikipedia.org/wiki/Halting_problem