lấy chuột ra khỏi mê cung

Question

Một con chuột được đặt trong mê cung tại một số vị trí không xác định trong mê cung.

Tất cả những gì chúng tôi có thể thực hiện là hướng lên, xuống, phải hoặc trái. Và chúng tôi có hai phương pháp:

• tryMove (< hướng >) trả về false nếu có một bức tường và đúng nếu chúng ta có thể di chuyển.
• bool hasLadder(): trả về true nếu có thang thoát.

Chúng ta phải viết một hàm khám phá trả về đúng nếu chúng ta tìm ra cách hoặc sai nếu không có cách nào.

Đây là một vấn đề đồ thị đơn giản và có thể được giải quyết bằng cách sử dụng thuật toán bfs hoặc dfs nếu chúng tôi có thể tìm thấy đánh dấu các địa điểm này. Nếu chúng ta không thể đánh dấu những nơi này, chúng ta có thể di chuyển trong các chu kỳ đến thăm những nơi giống nhau. Một số người có thể giúp tôi để có được chuột ra khỏi mê cung xin vui lòng nếu nó không được đánh dấu? Có thể không?

Answer 1

Cả hai tìm kiếm đầu tiên và chiều sâu đều yêu cầu bộ nhớ và thuật toán ngây thơ có thể lặp vô thời hạn. Một con chuột có lẽ chỉ có O (1) bộ nhớ.

Một cách để giải quyết nó mà không nhớ nơi bạn đã đến là chọn một hướng ngẫu nhiên. Thời gian giải quyết sẽ rất dài, nhưng cuối cùng nó sẽ đạt tới mọi hình vuông có thể tiếp cận. Điều này liên quan đến việc đi bộ 2D random.

Thật ngạc nhiên, nó đã được chứng minh rằng trên mạng hai chiều, đi bộ ngẫu nhiên có xác suất thống nhất đạt tới bất kỳ điểm nào (kể cả điểm xuất phát) khi số bước tiếp cận vô cùng.

Answer 2

Bạn nên chạy thuật toán BFS. Vấn đề duy nhất tôi thấy là làm thế nào để xác định đồ thị. Nó có thể được xác định với von Neumann neighborhood. Nút được định nghĩa là cặp X, Y. Pseudo code sẽ giống như thế:

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 

EDIT: bây giờ tôi đọc các giới hạn bộ nhớ là O (1). Vì vậy, tôi đoán bạn nên làm theo phương pháp cũ để luôn luôn chuyển sang bên phải và cuối cùng bạn sẽ nhận được ra khỏi mê cung hoặc quay trở lại vị trí bắt đầu.

EDIT2: từ ngô Mê lời khuyên:

Như với bất kỳ mê cung, nếu liên tục mất một trong hai bên phải hoặc tay trái biến, bạn cuối cùng sẽ tìm được lối ra. Chạy ngón tay của bạn dài bức tường của mê cung mà không cần nâng nó sẽ giữ cho bạn đi đúng hướng.

Answer 3

Đây là sự cố cổ điển thường được sử dụng như một bài tập về nhà.

Hãy thử điều này:

1. Bạn có thể cho biết nếu bạn đang ở đường ra ngay bây giờ?
2. Khi bạn có điều đó, bạn cần phải làm gì để tìm hiểu xem bạn có đang trong vòng một bước di chuyển không?
3. Còn nếu bạn đang trong vòng 2 bước di chuyển?

...

Như Mark notes, các phiên bản đơn giản của thuật toán tôi đang cố gắng để dẫn bạn đến có thể bị khóa trong một vòng lặp. Làm thế nào bạn có thể giải quyết vấn đề này?

Answer 4

Nếu tôi nhớ chính xác, tôi đã có bài tập về nhà đệ quy như thế này từ lâu, tuy nhiên nó không bị giới hạn trong bộ nhớ O (1). Chúng tôi chỉ không thể xây dựng 'bản đồ' của nơi chúng tôi đã và đã phải sử dụng đệ quy ... Tôi đoán điều này sẽ sử dụng O (n) bộ nhớ, trong đó n là khoảng cách ngắn nhất để các bậc thang từ đầu.

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 5

Xác định xem có cách nào có âm thanh giống như sự cố tạm dừng đối với tôi hay không. Nó có thể được giải quyết cho tất cả các trường hợp tầm thường và nhiều trường hợp không tầm thường nhưng đối với nhiều bản đồ trừ khi bạn có thể đánh dấu nơi bạn đã không thể chứng minh rằng bản đồ không phải là vô hạn.

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

Answer 6

Với không có ký ức giải pháp duy nhất là một ngẫu nhiên và đó là khủng khiếp. Nếu bạn biết mê cung chỉ được kết nối đơn lẻ, bạn có thể sử dụng phương pháp tiếp cận theo tường nhưng điều đó có thể đi vào vòng lặp vô hạn nếu mê cung chứa một vòng lặp.

Answer 7

Thuật toán về cơ bản là USTCON (vô hướng st-kết nối): cho trước một đồ thị vô hướng G, xác định xem có một con đường từ (vị trí bắt đầu của con chuột) nút s đến nút t (lối ra) . Vấn đề này là trong complexity class L, có nghĩa là nó yêu cầu logarithmic amount of memory. Vì vậy, trừ khi bạn có một giới hạn trên trên kích thước của mê cung, hoặc sẵn sàng để gần đúng, nó là không thể với không gian liên tục.

Answer 8

Hài hước rằng @mousey sẽ hỏi về một con chuột ... anwyay.

Tôi đã thấy sự cố này tăng lên một số lần.

Giải pháp đầu tiên (và ngây thơ) là đi theo bức tường bên trái (hoặc phải), tuy nhiên có thể tạo ra những mê cung cụ thể nơi con chuột cuối cùng chạy trong vòng tròn.

Thực tế, với mọi thứ tự xác định di chuyển (như 2L, 1R, 2L, 1R, ...) mà tôi đã thử (đang học trung học tôi có thời gian), chúng ta có thể tìm ra một mê cung chuột chạy trong vòng tròn. Tất nhiên, chu kỳ phức tạp hơn, mê cung phức tạp hơn.

Vì vậy, nếu bạn có bộ nhớ O (1), giải pháp duy nhất để thoát khỏi mê cung có vẻ là một bước đi ngẫu nhiên, như đề xuất của Mark Byers. Thật không may bạn không thể chứng minh nó không thể thoát ra khỏi mê cung với một thuật toán như vậy.

Mặt khác, nếu bạn có bộ nhớ O (N), nó sẽ cuộn xuống để tạo bản đồ (bằng cách nào đó). Chiến lược cuối cùng tôi đưa ra là để lại pheromon (tăng số lượt truy cập) trên mỗi trường hợp tôi đã qua, và khi có sự lựa chọn trong một động thái, để chọn trong số các trường hợp ít được truy cập nhất. Tuy nhiên nó luôn luôn có thể để có được ra vì vậy tôi không bao giờ phải suy nghĩ về một điều kiện chấm dứt trong trường hợp không có lối ra.

Bạn cũng có thể sử dụng thuật toán lấp đầy lũ lụt ... Tất nhiên, đó là trước khi tôi biết về thuật ngữ BFS. Điều này có lợi thế là bạn có một điều kiện chấm dứt (khi không còn bất kỳ trường hợp nào để khám phá).