Thuật toán để chuyển đổi một từ thành từ khác bằng cách thay đổi từng chữ cái cho mỗi lần lặp lại, nó sẽ tạo thành từ khác có ý nghĩa?

Question

Tôi muốn tạo một thuật toán để thay đổi một từ thành từ khác. Ví dụ, từ đã cho là "MUD" và tôi cần chuyển nó thành "BED". Đối với mỗi lần lặp, tôi có thể thay đổi một ký tự, nhưng điều đó sẽ tạo thành một từ có ý nghĩa khác. Ví dụ "MUD" có thể thay đổi thành "MAD". Như thế này tôi cần tìm đường đi ngắn nhất để chuyển đổi "MUD" thành "BED".

Một phương pháp riêng được cung cấp để tìm từ hợp lệ. IsWord() là một phương thức mà sẽ cho chúng ta kết quả boolean cho dù chuỗi đã cho là hợp lệ hay không. Vì vậy, không cần phải lo lắng về điều đó.

Tôi cũng không cần phải lo lắng về hiệu quả hoặc dòng mã, v.v. Làm bất kỳ ai có bất kỳ ý tưởng làm thế nào để làm cho thuật toán này. Nếu vậy xin hãy giúp tôi.

Cảm ơn trước.

(Tôi biết rằng chúng ta phải sử dụng cây và phải làm traversal nhị phân, nhưng tôi không có ý tưởng làm thế nào để sử dụng nó trong thuật toán này)

Answer 1

Đây được gọi là word ladder. Xem bài đăng The Longest Word Ladder Puzzle Ever trên Blog Wolfram.

Answer 2

Tạo một biểu đồ theo cách sau:

Mỗi từ là một nút và hai nút được kết nối nếu bạn có thể chuyển từ một từ này sang một từ khác trong một bước.

Bây giờ, hãy tìm khoảng cách và đường đi ngắn nhất giữa từ gốc và từ cuối cùng.

Xem: http://en.wikipedia.org/wiki/Shortest_path_problem về cách tính đường đi ngắn nhất.

Answer 3

Trong mỗi lần lặp lại, làm cho tất cả các từ mới có thể tạo thành các từ bạn có và thu thập chúng trong một danh sách, bộ hoặc bất kỳ thứ gì. Lọc ra các từ và bản sao bạn đã có trước đây. Ví dụ:

1. (BED) 
2. (BAD, BET, ....) 
3. (MAD, BAN, ...., BUT, BOT, ....) 

Bạn kết thúc bằng danh sách trống, thì vấn đề không thể giải quyết được hoặc từ được tìm kiếm nằm trong danh sách.

Answer 4

Bạn bắt đầu bằng cách có hàng đợi được sắp xếp với các thành phần (chuỗi). Mỗi phần tử có một xếp hạng/khoảng cách (theo một từ heuristic) đến từ đích. Đây có thể là Hamming Distance. Và hàng đợi được sắp xếp sử dụng khoảng cách này để đẩy lên trên từ gần nhất với mục tiêu.

Bạn lấy từ đầu tiên của mình, thêm từ đó vào hàng đợi. Trích xuất từ ​​hàng đợi thành phần đầu tiên, mở rộng tất cả các phần tử con của nó (các từ có thể lấy từ nó thông qua một chuyển đổi đơn) và đặt chúng vào hàng đợi. Làm điều này cho đến khi phần tử bạn nhận được từ hàng đợi là phần bạn đang tìm kiếm hoặc hàng đợi trống.