Sử dụng ngăn xếp để di chuyển và giải quyết mê cung - Java

Question

Vì vậy, tôi đang cố tạo một chương trình giải quyết mê cung có thể giải quyết một mê cung của X và O. Những gì tôi muốn làm là tạo ra một lớp các điểm, để tôi có thể tạo ra một mảng 2-chiều của các điểm mà sẽ cho phép in ấn một trang đầu ra cũng như thực hiện ngăn xếp để được tương đối đơn giản.

Thuật toán đơn giản nhất của ý tưởng chung tôi muốn thực hiện trong chương trình thực tế bản thân tôi tin rằng cần phải:

1) Move forward 
2) Are you at a wall? 
2a) If yes, turn left 
3) Are you at the finish? 
3a) If no, go to 1 
3b) If yes, solved 

Nhưng tôi đang gặp rắc rối đến với một sâu hơn thuật toán, cũng như nhận được điểm lớp của tôi nằm. Tôi biết cho các điểm tôi nên đã thiết lập tọa độ X, và thiết lập Y phối hợp cũng như getters cho cả hai là tốt. Bạn có nghĩ tôi cần nhiều phương pháp hơn hai phương pháp này không? Giống như, tôi có nên tạo một phương thức chuyển một tham số x, và y như là các tham số để tôi có thể chỉ đẩy các phương thức đó lại với nhau, thay vì thiết lập x và y riêng lẻ?

Đây là những gì một mê cung mẫu sẽ trông như thế nào, nơi bạn bắt đầu ở góc dưới bên và cố gắng đi qua để phía trên bên trái, với X là bức tường, và không gian như mở O trong mê cung:

O O O O O X O 
X X O X O O X 
O X O O X X X 
X X X O O X O 
X X X X O O X 
O O O O O O O 
X X O X X X O 

Answer 1

Bạn có thể sử dụng số

Stack<Point> points = new Stack<>(); 

// add a point 
Point p = new Point(x, y); 
if (points.contains(p)) 
    // been here before, in circles. 
else 
    points.add(p); 

Answer 2

Bạn có chắc chắn thuật toán của mình sẽ giải quyết được bất kỳ mê cung nào không? Tôi nghĩ rằng nó sẽ gặp khó khăn trong việc này đơn giản mock-up (trong đó S là bắt đầu và F là kết thúc):

xxxxxxxxxx 
Sooooooxxx 
xxxxxxoxxx 
xxxxxxFxxx 

thuật toán của bạn sẽ tiến hành dọc hành lang đầu tiên cho đến khi nó phải đối mặt với sự sụp đổ, rẽ trái, phải đối mặt với "phía bắc" bức tường, rẽ trái một lần nữa, và đi bộ trở lại hành lang đầu tiên, nơi nó sẽ rẽ trái hai lần nữa và tiếp tục lặp lại vấn đề này.

Thuật toán quy tắc bên phải (xem wikipedia page, cũng như các phần khác để biết thêm các mê cung) nên giải quyết bất kỳ mê cung nào mà không có vòng lặp và phải khá dễ thực hiện trong java.

Answer 3

Đối với các thuật toán bạn có thể sử dụng backtracking (EDIT mặc dù nó không hoàn toàn phù hợp với ý tưởng chung của bạn.) Bạn chỉ phải nhận ra chuyển động của bạn được "đẩy" vào một chồng ảo, và họ phải unpushed (và do đó bạn có thể phải tự mình thực hiện ngăn xếp nếu "robot" là một đối tượng thực sự di chuyển, nhưng bạn có thể dựa vào ngăn xếp cuộc gọi nếu bạn chỉ muốn giải quyết mê cung.

Answer 4

Đối với phần thuật toán, độ sâu đệ quy đầu tiên thông qua ngăn xếp được ưu tiên. Một cái gì đó dọc theo dòng:

currentSpot = (0,0) // The starting point // 

while(! currentSpot.isExit()) { 

    if (! currentSpot.left().isWall()) stack.push(currentSpot.left()); 
    if (! currentSpot.forward().isWall()) stack.push(currentSpot.forward()); 
    if (! currentSpot.right().isWall()) stack.push(currentSpot.right()); 

    currentSpot = stack.pop(); // Get the next location // 
} 

Bạn sẽ muốn lớp điểm trở lại điểm tiếp theo theo từng hướng nhất định (trừ lùi), cũng như phát hiện khi bạn ở các cạnh của mê cung. Có thể bạn sẽ muốn một lớp Maze chứa tất cả các điểm, in ấn, lưu trữ X/O, vv Vì vậy, bạn có thể thay thế currentSpot = (0,0) ban đầu bằng currentSpot = Maze.getStartingSpot() ;

Answer 5

Đối với thuật toán của bạn, bạn không cần ngăn xếp. Chỉ khi bạn sử dụng backtracking để hoàn tác quyết định truyền tải, bạn sẽ cần một ngăn xếp.

Answer 6

Sử dụng thuật toán tường theo: http://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower

Answer 7

Chúng tôi giải quyết vấn đề này một lần khi tôi còn đi học và chúng tôi sử dụng một giải pháp tương tự ở bên phải/quy tắc bàn tay trái. Tôi tin rằng chúng tôi đã làm điều này trong khi tìm hiểu về Danh sách được liên kết. Tóm lại, thuật toán giống như sau:

1. Chuyển sang trái. Nếu có thể, hãy lặp lại.
2. Nếu không, hãy đi thẳng. Nếu có thể, hãy quay lại bước 1.
3. Nếu không, hãy đi thẳng. Nếu có thể, hãy quay lại bước 1.

Ở mỗi bước, bạn cũng kiểm tra xem vị trí bạn đang đứng là kết thúc hay không. Nếu bạn không thể tiếp tục (ví dụ, không thể đi sang trái, thẳng, hoặc phải), bạn đánh dấu vị trí bạn đang đứng trên là 'đã truy cập' và sao lưu. Rửa sạch và lặp lại.