Thuật toán Loang

Thuật toán Loang
Thuật toán Loang thường được ứng dụng vào việc biến đổi trạng thái Otomat cũng như các bài toán tìm kiếm trên đồ thị trong trường hợp yêu cầu bài toán là: số phép biến đổi là ít nhất.
ưu điểm của nó là: rất dễ cài đặt và cho lời giải tối ưu. Tuy nhiên nó lại chứa đựng một nhược điểm rất lớn là khi số lượng cấu hình lưu trữ quá lớn sẽ gây tràn bộ nhớ. Tất nhiên cũng có những cách để khắc phục nhược điểm này nhưng chúng ta sẽ bàn sau.
ý tưởng của thuật toán là ở chỗ: từ một trạng thái ban đầu, chúng ta sẽ tạo lần lượt các trạng thái có thể có từ trạng thái đã cho và các trạng thái được tạo ra lại tạo tiếp các trạng thái khác (chính vì vậy thuật toán mới có tên là Loang!). Các trạng thái mới được tạo ra sẽ được lưu vào một hàng đợi Queue. Như vậy, rõ ràng:
- Nếu để thực hiện đến hết chúng ta thu được mọi trạng thái từ trạng thái ban đầu.
- Nếu cần biến đổi đến một trạng thái nào đó thì nhờ thứ tự duyệt cấu hình theo kiểu "Vào trước ra trước" (First in First out) như vậy mà khi dừng ở trạng thái đó thì số lượng phép biến đổi là cực tiểu.
Để dễ hiểu ta xét ví dụ sau đây:
Ví dụ 1: Có một Otomat được ghép từ các chi tiết có một trong hai trạng thái 0 hay 1 như hình 1. Otomat có cấu trúc như hình 2 gồm 8 chi tiết G1,...,G8 với ba lối và A,B,C. Trạng thái của Otomat được thể hiện bởi một xâu nhị phân độ dài 8 là các trạng thái tương ứng của G1,...,G8.


Otomat hoạt động như sau: Khi thả một quả cầu vào một lối vào nào đó, sau khi quả cầu đi từ một chi tiết nào đó, chi tiết đó thay đổi trạng thái từ 0 thành 1 hoặc từ 1 thành 0. Hoạt động của Otomat được thể hiện bởi một xâu ký tự S chỉ gồm các chữ cái hoa A,B,C mà mỗi ký tự trong xâu S thể hiện việc ta thả quả cầu vào lối vào với tên ký tự đó. Ví dụ S=AABC có nghĩa là ta lần lượt thả quả cầu vào các lối A,A,B,C.


Bài toán đặt ra như sau: Cho hai trạng thái bất kỳ T1 và T2 của Otomat. Hãy tìm một xâu ký tự S ngắn nhất có thể được thể hiện hoạt động của Otomat chuyển từ trạng thái T1 đến trạng thái T2.
Các xâu T1 và T2 nhập từ bàn phím và viết xâu S ra màn hình.
Phân tích bài toán: Đây là bài toán "mẫu mực" về thuật toán Loang.
Mỗi trạng thái là một xâu nhị phân độ dài 8 được khai báo:
Type Otomat=String[8]
Dễ thấy, số lượng trạng thái là 28 = 256 không quá lớn cho nên chúng ta có thể dùng một hàng đợi Queue 256 phần tử để chứa từng trạng thái được tạo thành. Ta khai báo như sau:
Type QueueType: Array[1..256] of otomat;
Var  Queue: QueueType;
Quá trình loang được thực hiện cho đến khi xây dựng được trạng thái đích T2 hoặc hàng đợi rỗng thì dừng. Quá trình này được quản lý bằng hai biến First (đầu) và Last (cuối):
-Biến First trỏ đến vị trí trạng thái đang xét để loang ra các trạng thái mới
-Biến Last trỏ đến vị trí trạng thái mới nhất được tạo ra trong Queue.
Khởi tạo ban đầu: First:=1 và Last:=1;
Hàm EmptyQueue cho biết hàng đợi có rỗng không.
Function EmptyQueue (Queue: QueueType):Boolean;
Begin
   Empty:=(First>Last);
End;
Ta lại cần thêm 2 thủ tục là: Lấy một trạng thái ra khỏi hàng đợi để biến đổi (Remove) và nạp một trạng thái mới vào hàng đợi (Ađ)
(******Lay khoi Queue******)
Procedure Remove(Var CurrentOtomat:Otomat;Queue:QueueType);
Begin
  CurrentOtomat:=Q[First]; Inc(First);
End;
(******Nap vao Queue******)
Procedure Ađ(NewOtomat:Otomat;Var Queue:QueueType);
Begin
  Inc(Last); Q[Last]:=NewOtomat;
End;
Công việc quan trọng nhất là: biến đổi từ một trạng thái bất kỳ Ti thành các trạng thái có thể có, bằng cách ta xét 3 khả năng: Thả quả cầu vào lối A, lối B, lối C. Tác động này lên trạng thái Tưi tạo thành các trạng thái mới Tk,Tk+1,Tk+2.
Tuy nhiên cần chú ý rằng: 3 trạng thái mới tạo này có thể đã được tạo từ trước cho nên để tránh khả năng loang lại trạng thái cũ (mà điều này có thể dẫn đến thuật toán không dừng!?) ta phải dùng