tailieunhanh - Thuật Toán Và Thuật Giải part 3

Better:=FALSE; WHILE (Better=FALSE) AND (STOP=FALSE) DO BEGIN IF THEN BEGIN ; Stop:=TRUE; END; ELSE BEGIN Tk := ; IF THEN BEGIN Ti :=Tk; Better:=TRUE; END; END; END; {WHILE} END; {ELSE} END;{WHILE} Mệnh đề "h’(Tk) tốt hơn h’(Ti)" nghĩa là gì? Đây là một khái niệm chung chung | Better FALSE WHILE Better FALSE AND STOP FALSE DO BEGIN IF không tồn tại trạng thái kế tiếp hợp lệ của Ti THEN BEGIN không tìm được kết quả Stop TRUE END ELSE BEGIN Tk một trạng thái kế tiếp hợp lệ của Ti IF h Tk tốt hơn h Ti THEN BEGIN Ti Tk Better TRUE END END END WHILE END ELSE END WHILE Mệnh đề h Tk tốt hơn h Ti nghĩa là gì Đây là một khái niệm chung chung. Khi cài đặt thuật giải ta phải cung cấp một định nghĩa tường minh về tốt hơn. Trong một số trường hợp tốt hơn là nhỏ hơn h Tk h Ti một số trường hợp khác tốt hơn là lớn hơn h Tk h Ti .Chẳng hạn đối với bài toán tìm đường đi ngắn nhất giữa hai điểm. Nếu dùng hàm h là hàm cho ra khoảng cách theo đường chim bay giữa vị trí hiện tại trạng thái hiện tại và đích đến trạng thái đích thì tốt hơn nghĩa là nhỏ hơn. Vấn đề cần làm rõ kế tiếp là thế nào là một trạng thái kế tiếp hợp lệ của Ti Một trạng thái kế tiếp hợp lệ là trạng thái chưa được xét đến. Giả sử h của trạng thái hiện tại Ti có giá trị là h Ti và từ Ti ta có thể biến đổi sang một trong 3 trạng thái kế tiếp lần lượt là Tk1 Tk2 Tk3 với giá trị các hàm h tương ứng là h Tk1 h Tk2 h Tk3 . Đầu tiên Tk sẽ được gán bằng Tk1 nhưng vì h Tk h Tk1 h Ti nên Tk không được chọn. Kế tiếp là Tk sẽ được gán bằng Tk2 và cũng không được chọn. Cuối cùng thì Tk3 được chọn. Nhưng giả sử h Tk3 thì cả Tk3 cũng không được chọn và mệnh đề không thể sinh ra trạng thái kế tiếp của Ti sẽ có giá trị TRUE. Giải thích này có vẻ hiển nhiên nhưng có lẽ cần thiết để tránh nhầm lẫn cho bạn đọc. Để thấy rõ hoạt động của thuật giải leo đồi. Ta hãy xét một bài toán minh họa sau. Cho 4 khối lập phương giống nhau A B C D. Trong đó các mặt M1 M2 M3 M4 M5 M6 có thể được tô bằng 1 trong 6 màu 1 2 3 4 5 6 . Ban đầu các khối lập phương được xếp vào một hàng. Mỗi một bước ta chỉ được xoay một khối lập phương quanh một trục X Y Z 900 theo chiều bất kỳ nghĩa là ngược chiều hay thuận chiều kim đồng hồ cũng được . Hãy xác định số bước quay ít nhất sao cho tất cả các mặt của khối lập