Câu 2

so sánh tìm kiếm theo chiều rộng và theo chiều sâu

* Giống nhau

-độ phức tạp 0(bd)

-đều là thuật toán tk mù

* Khác nhau

a)      về ý tưởng:

+ theo chiều rộng:xét đỉnh đc sinh ra đầu tiên trong số các đỉnh đang chờ phát triển

+ theo chiều sâu: xét đỉnh đc sinh ra  sau cùng trong số các đỉnh đang chờ phát triển

b)      về cài đặt:

+ theo chiều rộng: sd ds L kiểu hàng đợi

+ theo chiều sâu: sd ds L kiểu ngăn xếp

c)      về thuật toán

+ theo chiều rộng: đưa vào cuối ds và lấy ra ở đầu ds

+ chiều sâu: đưa vào đầu và lấy ra ở đầu

d)      khả năng

+ chiều sâu: nếu có nghiệm thì chắc chắn tìm đc nghiệm

+ chiều sâu: có nghiệm nhưng chưa chắc chắn tìm ra nghiệm

so sánh tk tốt nhất và leo đồi

* Giống nhau

- Độ phức tạp: đều sử dụng 1 vòng lặp

- sắp xếp 0(n)

* Khác nhau

a) ý tưởng:

+ tốt nhất:kt hàm có giá trị min trong số tất cả các trạng thái đang chờ phát triển

+ leo đồi: kt đỉnh có giá trị hàm đánh giá min trong số các đỉnh con của đỉnh đang đc phát triển ở trước đó

b) cài đặt

+ tốt nhất: sd 1 ds L kiểu hàng đợi

+ leo đồi: sd 1 ds kiểu ngăn xếp

c) thuật toán

+ tốt nhất: chọn đỉnh đứng đầu ds để phát triển

+ leo đồi: loại phần tử đứng đầu ds L sau đó đưa các đỉnh con của nó vào L1 để sắp xếp

d) độ phức tạp

+ tốt nhất : 0(n) hay 0(n2) hay 0(n.log2n)

+ leo đồi: 0(n)

e) khả năng

+ tốt nhất: nếu có nghiệm thì sẽ tìm ra nghiệm

+ leo đồi: có nhưng chưa chắc tìm ra nghiệm

so sánh leo đồi và độ sâu

* Giống nhau

-đều là tk đc hướng dẫn bởi hàm đánh giá

-đều sd ds L kiểu ngăn xếp

- có nghiệm nhưng chưa chắc tìm ra nghiệm

- độ phức tạp 0(bd)

* Khác nhau

a) ý tưởng:

+ leo đồi:  kt đỉnh có giá trị hàm đánh giá min trong số các đỉnh con của đỉnh đang đc phát triển ở trước đó

+ chiều sâu: xét đỉnh đc sinh ra  sau cùng trong số các đỉnh đang chờ phát triển

b) thuật toán

+ leo đồi: khi ta phát triển 1 đỉnh u thì bước tiếp theo ta chọn trong số các đỉnh kề với u, đỉnh có nhiều lứ chọn nhất để phát triển, đỉnh này đc xđ bởi hàm đánh giá

+ chiều sâu: tại mỗi bước trạng thái đc chọn chờ phát triển là trạng thái đc sinh ra sau cùng trong số các trạng thái đang chờ phát triển

so sánh tốt nhất với chiều rộng

* Giống nhau

- độ phức tạp: 0(bd)

-đều là thuật toán tk mù

* Khác nhau

a) ý tưởng:

+ tốt nhất : đc hướng dẫn bởi hàm đánh giá cụ thể là tại mỗi bước ta sẽ kt hàm có giá trị min trong số tất cả các trạng thái đang chờ phát triển

+ chiều rộng : tại mỗi bước ta sẽ chọn trạng thái để phát triển là trạng thái  sinh ra đầu tiên trong số tất cả các trạng thái đang chờ phát triển

b) thuật toán

+ tốt nhất: chọn đỉnh tốt nhất đầu tiên đc xđ bởi hàm đánh giá( đỉnh có giá trị hàm đánh giá là nhỏ nhất)

+ chiều sâu: phát triển tất cả các đỉnh ở mức hiện tại để sinh ra các đỉnh ở mức tiếp theo

      5. so sánh leo đồi và A*

*Giống nhau

- đều là 2 tk đc hướng dẫn bởi hàm đánh giá, kt đỉnh có giá trị hàm đánh giá là nhỏ nhất

* Khác nhau

Thuật toán

   + leo đồi: ta sd 2 ds:ds L chứa tất cả các đỉnh đang chờ phát triển còn ds L1 để lưu giữ tạm thời các đỉnh con của đỉnh vừa đc phát triển. Tại mỗi bước ta sẽ loại phần tử đứng đầu ds L, sau đó đưa các đỉnh con của nó vào L1 tăng dần và đưa lần lượt các đỉnh vào đầu L khi đó phần tử đứng đầu của L chính là phần tử đứng đầu của L1 và nó có giá trị đánh giá min trong L1.

+ A*: tại mỗi bước sau khi kt đỉnh u nếu nó k0 phải là đỉnh kết thúc thì với mỗi đỉnh v là con của u ta sẽ tính các gia trị g(v), f(v) và đưa v vào ds L. Sau khi đưa tất cả các đỉnh con của u vào L ta sẽ sắp xếp L tăng dần theo f