Home » Thuật toán

Thuật toán

Bài toán người du lịch

BÀI TOÁN NGƯỜI DU LỊCH Cho n thành phố đánh số từ 1 đến n và m tuyến đường giao thông hai chiều giữa chúng, mạng lưới giao thông này được cho bởi bảng C cấp nxn, ở đây C[i, j] = C[j, i] = Chi phí đi đoạn đường trực tiếp từ thành phối đến thành phốj. Giảthiết rằng ... Read More »

Thuật toán nhánh cận

Mô hình thuật toán nhánh cận Dựa trên mô hình thuật toán quay lui, ta xây dựng mô hình sau: Kỹ thuật nhánh cận thêm vào cho thuật toán quay lui khả  năng đánh giá theo từng bước, nếu tại bước thứ i, giá trị thử gán cho x[i]  không có hi vọng tìm thấy cấu hình tốt hơn BESTCONFIG ... Read More »

Bài toán xếp hậu (Backtracking)

quay lui

Bài toán xếp hậu: Xét bàn cờ tổng quát kích thước nxn. Một quân hậu trên bàn cờ có thể ăn được các quân khác nằm tại các ô cùng hàng, cùng cột, hoặc cùng đường chéo. Hãy tìm cách xếp n quân hậu trên bàn cờ sao cho không quân nào ăn quân nào. Ví dụ cách xếp 8 ... Read More »

Bài toán phân tích số

quay lui

Bài toán phân tích số: Cho một số nguyên dương n<=30, hãy tìm tất cả cách phân tích số n thành tổng của các số nguyên dương, các cách phân tích là hoán vị của nhau chỉ tính là 1 cách. Cách làm Bài toán phân tích số:  Dùng 1 mảng t[i] để lưu tổng giá trị của x từ ... Read More »

Liệt kê tổ hợp

quay lui

HD: Để liệt kê các tập con k phần tử của tập S = {1,2,…,n} ta có thể đưa về liệt kê các cấu hình x[1…n], ở đây các x[i] thuộc S và x[1] < x[2] < … < x[m]. Ta có nhận xét như sau:   x[m] <= n x[m-1] <= x[m]-1 <= n-1 … x[i] <= n-m+i … ... Read More »

Liệt kê hoán vị (PP quay lui)

Bài tập: Liệt kê hoán vị của {1,2,…,n} HD: Đáp số có dạng (x1,x2,…,x n). Khả năng của xi là 1,2,…,n Chấp nhận khả năng j của xi: chỉ chấp nhận khi chưa được sử dụng (xi khác x1,…,xi-1). Để theo dõi j sử dụng hay chưa ta dùng một mảng b: b[j]=false là chưa sử dụng j. Xác nhận xi ... Read More »

Liệt kê dãy nhị phân (PP quay lui)

Đề bài : Liệt kê dãy nhị phân có độ dài n. HD: Đáp số có dạng (x1,x2,…,x n). Khả năng của xi là 0,1. Chấp nhận khả năng j của xi: luôn chấp nhận. Xác định xi theo j: xi=j. Ghi nhận 1 đáp số: xuất dãy xi. Code tham khảo:  [crayon-5c149cd4b84d2977197518/]       Read More »

Thuật toán Quay lui (Backtracking Algorithms)

Ý tưởng: G/s đáp số của bài toán là một bộ có n thành phần (x1,x2,…,xn) và g/s đã xác định được i-1 thành phần x1,x2,…,xi-1. Để xác định xi, ta xét tất cả các khả năng có thể của xi, đánh số các khả năng này là 1,…,ni. Với mỗi khả năng j của xi ta kiểm tra xem khả năng j ... Read More »

Liệt kê hoán vị (PP Sinh)

Link bài: http://www.spoj.com/PTIT/problems/BCPERMU/ 9807. Liệt kê hoán vị (Cơ bản) Mã bài: BCPERMU Liệt kê hoán vị của n phần tử của một tập gồm các số từ 1->n. Input Dòng duy nhất chứa số n (1<=n<=8) Output Các hoán vị sắp xếp theo thứ tự từ điển tăng dần. Example Input: 3 Output: 123 132 213 231 312 321   ... Read More »

Share
Free WordPress Themes - Download High-quality Templates