Cách tiếp cận hiệu quả để giải quyết vấn đề câu đố 8 là gì?

Question

Câu đố 8 là một bảng vuông với 9 vị trí, được lấp đầy bởi 8 ô đánh số và một khoảng trống. Tại bất kỳ điểm nào, một gạch liền kề với khoảng cách có thể được chuyển vào khoảng trống, tạo ra một vị trí khoảng cách mới. Nói cách khác, khoảng cách có thể được hoán đổi với một gạch liền kề (theo chiều ngang và chiều dọc). Mục tiêu trong trò chơi là bắt đầu với một cấu hình tùy ý của các ô và di chuyển chúng để lấy các ô được đánh số theo thứ tự tăng dần hoặc chạy xung quanh chu vi của bảng hoặc được sắp xếp từ trái sang phải, với 1 ở trên cùng bên trái -hand vị trí.

Tôi đã tự hỏi cách tiếp cận nào sẽ hiệu quả để giải quyết vấn đề này?

Answer 1

Tôi sẽ cố gắng viết lại câu trả lời trước đó với nhiều chi tiết hơn về lý do tại sao nó tối ưu.

Các thuật toán A * lấy trực tiếp từ wikipedia là

  function A*(start,goal) 
        closedset := the empty set     // The set of nodes already evaluated.  
        openset := set containing the initial node // The set of tentative nodes to be evaluated. 
        came_from := the empty map     // The map of navigated nodes. 
        g_score[start] := 0      // Distance from start along optimal path. 
      h_score[start] := heuristic_estimate_of_distance(start, goal) 
        f_score[start] := h_score[start]   // Estimated total distance from start to goal through y. 
        while openset is not empty 
        x := the node in openset having the lowest f_score[] value 
        if x = goal 
      return reconstruct_path(came_from, came_from[goal]) 
        remove x from openset 
        add x to closedset 
      foreach y in neighbor_nodes(x) 
        if y in closedset 
        continue 
      tentative_g_score := g_score[x] + dist_between(x,y) 

        if y not in openset 
        add y to openset 
        tentative_is_better := true 
        elseif tentative_g_score < g_score[y] 
        tentative_is_better := true 
        else 
        tentative_is_better := false 
        if tentative_is_better = true 
        came_from[y] := x 
        g_score[y] := tentative_g_score 
      h_score[y] := heuristic_estimate_of_distance(y, goal) 
        f_score[y] := g_score[y] + h_score[y] 
        return failure 

      function reconstruct_path(came_from, current_node) 
        if came_from[current_node] is set 
        p = reconstruct_path(came_from, came_from[current_node]) 
      return (p + current_node) 
        else 
        return current_node 

Vì vậy, hãy để tôi điền vào tất cả các chi tiết ở đây.

heuristic_estimate_of_distance là hàm Σ d (x _i) trong đó d (.) Là khoảng cách Manhattan của mỗi vuông x _i từ trạng thái mục tiêu của nó.

Vì vậy, việc thiết lập

  1 2 3 
      4 7 6 
      8 5 

sẽ có một heuristic_estimate_of_distance của 1 + 2 + 1 = 4 vì mỗi người trong số 8,5 là một cách xa vị trí mục tiêu của họ với d (.) = 1 và 7 là 2 tránh xa trạng thái mục tiêu của nó với d (7) = 2.

Tập hợp các nút mà A * tìm kiếm được xác định là vị trí bắt đầu theo sau là tất cả các vị trí pháp lý có thể có. Đó là cho phép nói rằng vị trí bắt đầu x là như trên:

  x = 
      1 2 3 
      4 7 6 
      8 5 

thì hàm neighbor_nodes(x) tạo ra 2 động thái pháp lý có thể:

  1 2 3 
      4 7 
      8 5 6 

      or 

      1 2 3 
      4 7 6 
      8 5 

Chức năng dist_between(x,y) được định nghĩa là số lần di chuyển vuông mà mất địa điểm chuyển tiếp từ tiểu bang x sang y. Điều này chủ yếu sẽ bằng 1 trong A * luôn cho mục đích của thuật toán của bạn.

closedset và openset đều cụ thể cho các thuật toán A * và có thể được thực hiện sử dụng cấu trúc dữ liệu tiêu chuẩn (hàng đợi ưu tiên Tôi tin.) came_from là một cấu trúc dữ liệu dùng để tái tạo lại các giải pháp phát hiện bằng cách sử dụng chức năng reconstruct_path người là chi tiết có thể tìm thấy trên wikipedia. Nếu bạn không muốn nhớ giải pháp bạn không cần phải thực hiện điều này.

Cuối cùng, tôi sẽ giải quyết vấn đề tối ưu. Hãy xem đoạn trích từ bài viết A * wikipedia:

"Nếu chức năng heuristic h được chấp nhận, nghĩa là nó không bao giờ đánh giá cao chi phí tối thiểu thực tế để đạt được mục tiêu, thì A * được chấp nhận (hoặc tối ưu) nếu chúng ta làm không sử dụng bộ kín nếu sử dụng bộ đóng, thì h cũng phải đơn điệu (hoặc nhất quán) cho A * để tối ưu, điều này có nghĩa là đối với bất kỳ cặp nút lân cận x và y, trong đó d (x, y) biểu thị độ dài của cạnh giữa chúng, chúng ta phải có: h (x) < = d (x, y) + h (y)"

Vì vậy, nó cũng đủ để chứng minh rằng dựa trên kinh nghiệm của chúng tôi là có thể chấp nhận và đơn điệu.Đối với cựu (chấp nhận), lưu ý rằng bất kỳ cấu hình nào của chúng tôi ước tính rằng mỗi ô vuông không bị ràng buộc bởi các động thái hợp pháp và có thể di chuyển tự do theo vị trí mục tiêu của nó. là chấp nhận (hoặc nó không bao giờ quá ước tính kể từ khi đạt đến một vị trí mục tiêu sẽ luôn lấy ít nhất bao nhiêu bước dự toán heuristic.)

yêu cầu đơn điệu tuyên bố bằng lời là: "chi phí phỏng đoán (ước tính khoảng cách đến trạng thái mục tiêu) của bất kỳ nút nào phải nhỏ hơn hoặc bằng chi phí chuyển đổi sang bất kỳ nút lân cận cộng với chi phí heuristic của nút đó. " Nó là chủ yếu để ngăn chặn khả năng của chu kỳ tiêu cực, nơi chuyển sang một nút không liên quan có thể làm giảm khoảng cách đến nút mục tiêu nhiều hơn chi phí thực sự chuyển đổi, cho thấy một heuristic nghèo.

Để thể hiện tính đơn điệu của nó khá đơn giản trong trường hợp của chúng tôi. Bất kỳ nút lân cận x, y nào có d (x, y) = 1 theo định nghĩa của chúng ta về d. Do đó chúng ta cần phải chứng minh

h (x) < = h (y) + 1

tương đương với

h (x) - h (y) < = 1

mà tương đương với

Σ d (x _i) - Σ d (y _i) < = 1

tương đương với

Σ d (x _i) - d (y _i) < = 1

Chúng tôi biết theo định nghĩa của chúng ta về neighbor_nodes(x) rằng hai nút hàng xóm x, y có thể có ít nhất vị trí của một hình vuông khác nhau, có nghĩa là trong khoản tiền của chúng tôi thuật ngữ

d (x _i) - d (y _i) = 0

cho tất cả trừ 1 giá trị i. Cho phép nói mà không mất tính tổng quát, điều này đúng với i = k. Hơn nữa, chúng tôi biết rằng đối với i = k, nút đã chuyển tối đa là một nơi, vì vậy khoảng cách của nó để trạng thái mục tiêu phải có ít nhất một trong hơn ở trạng thái trước đó như sau:

Σ d (x _i) - d (y _i) = d (x _k) - d (y _k) < = 1

thấy đơn điệu. Điều này cho thấy những gì cần thiết để được thể hiện, do đó chứng minh thuật toán này sẽ tối ưu (theo ký hiệu lớn hoặc cách tiệm cận.)

Lưu ý rằng tôi đã thể hiện sự tối ưu về ký hiệu big-O nhưng có vẫn còn rất nhiều phòng để chơi trong điều chỉnh các heuristic.Bạn có thể thêm các dấu xoắn bổ sung vào nó để ước tính gần đúng khoảng cách thực tế với trạng thái mục tiêu, tuy nhiên bạn phải thực hiện chắc chắn rằng heuristic luôn là số đánh giá thấp nếu không bạn mất tối ưu!

Answer 2

Kể từ khi OP không thể gửi một bức tranh, đây là những gì anh ấy nói về:

Theo như giải quyết câu đố này, đi, hãy nhìn vào các thuật toán iterative deepening depth-first search, như làm liên quan đến Bài toán 8 câu đố theo số this page.

Answer 3

Donut's got it! IDDFS sẽ thực hiện thủ thuật, xem xét không gian tìm kiếm tương đối hạn chế của câu đố này. Nó sẽ có hiệu quả do đó đáp ứng với câu hỏi của OP. Nó sẽ tìm ra giải pháp tối ưu, nhưng không nhất thiết phải ở độ phức tạp tối ưu.

Thực hiện IDDFS sẽ là một phần phức tạp của vấn đề này, tôi chỉ muốn đề xuất một cách tiếp cận đơn giản để quản lý bảng, các quy tắc trò chơi v.v. Điều này đặc biệt giải quyết một cách để có được trạng thái ban đầu cho câu đố . Một gợi ý trong các ghi chú của câu hỏi, không phải tất cả các mệnh đề ngẫu nhiên của 9 tites (xem xét các khe trống một gạch đặc biệt), sẽ mang lại một câu đố giải quyết được. Đây là vấn đề về tính chẵn lẻ toán học ... Vì vậy, đây là một đề xuất để mô hình trò chơi:

Lập danh sách tất cả các ma trận hoán vị 3x3 thể hiện "di chuyển" hợp lệ của trò chơi. Danh sách như vậy là một tập con của 3x3s w/tất cả số không và hai số. Mỗi ma trận nhận được một ID sẽ khá thuận tiện để theo dõi các di chuyển, trong cây tìm kiếm IDDFS. Một giải pháp thay thế cho ma trận, là có hai bộ số vị trí xếp kề để hoán đổi, điều này có thể dẫn đến việc triển khai nhanh hơn.

Các ma trận như vậy có thể được sử dụng để tạo trạng thái câu đố ban đầu, bắt đầu với trạng thái "giành chiến thắng" và chạy một số hoán vị tùy ý được chọn ngẫu nhiên. Ngoài việc đảm bảo rằng trạng thái ban đầu là khả năng giải được, phương pháp này cũng cung cấp một số di chuyển chỉ định mà một câu đố đã cho có thể được giải quyết.

Bây giờ chúng ta hãy chỉ thực hiện IDDFS algo và [đùa] trả lại assignement cho điểm A + [/ đùa] ...

Answer 4

Bạn có thể sử dụng heuristic dựa trên vị trí của các con số, đó là cao hơn tổng số tổng của tất cả các khoảng cách của mỗi chữ cái từ trạng thái mục tiêu của nó là, giá trị heuristic càng cao. Sau đó, bạn có thể thực hiện tìm kiếm A * có thể được chứng minh là tìm kiếm tối ưu về mặt thời gian và không gian phức tạp (miễn là heuristic là đơn điệu và chấp nhận được.) http://en.wikipedia.org/wiki/A*_search_algorithm

Answer 5

Đây là một ví dụ về thuật toán đường đi ngắn nhất cổ điển. Bạn có thể đọc thêm về đường đi ngắn nhất here và here.

Tóm lại, hãy suy nghĩ về tất cả các trạng thái có thể có của câu đố dưới dạng các đỉnh trong một số biểu đồ. Với mỗi lần di chuyển, bạn thay đổi trạng thái - vì vậy, mỗi lần di chuyển hợp lệ thể hiện một cạnh của biểu đồ.Kể từ khi di chuyển không có bất kỳ chi phí, bạn có thể nghĩ đến chi phí của mỗi di chuyển là 1. sau đây C++ - như pseudo-code sẽ làm việc cho vấn đề này:

{ 
int[][] field = new int[3][3]; 
// fill the input here 
map<string, int> path; 
queue<string> q; 
put(field, 0); // we can get to the starting position in 0 turns 
while (!q.empty()) { 
    string v = q.poll(); 
    int[][] take = decode(v); 
    int time = path.get(v); 
    if (isFinalPosition(take)) { 
     return time; 
    } 
    for each valid move from take to int[][] newPosition { 
     put(newPosition, time + 1); 
    } 
} 
// no path 
return -1; 
} 

void isFinalPosition(int[][] q) { 
    return encode(q) == "123456780"; // 0 represents empty space 
} 
void put(int[][] position, int time) { 
    string s = encode(newPosition); 
    if (!path.contains(s)) { 
     path.put(s, time); 
    } 
} 

string encode(int[][] field) { 
    string s = ""; 
    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) s += field[i][j]; 
    return s; 
} 

int[][] decode(string s) { 
    int[][] ans = new int[3][3]; 
    for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) field[i][j] = s[i * 3 + j]; 
    return ans; 
} 

Answer 6

Xem liên kết này cho tôi parallel iterative deepening search for a solution to the 15-puzzle, mà là anh trai lớn của trò chơi 8 câu đố.