LAB 5A · BACKTRACKING SEARCH

Tìm kiếm quay lui

CSP · MRV · Degree · LCV · Forward checking

KSSáng

CH?

HATối

MỤC ĐÍCH BÀI LAB

Sau Lab này bạn sẽ làm được gì?

Mô hình hóa lịch phân ca khảo sát du lịch thành bài toán thỏa mãn ràng buộc. Cài đặt backtracking đệ quy, sau đó kết hợp MRV, degree, LCV và forward checking để quan sát khả năng cắt giảm không gian tìm kiếm.

Khái niệm cốt lõi

CSP

Mỗi địa điểm là một biến. Miền giá trị là các ca biến được phép nhận: KS chỉ có Sáng, HA chỉ có Tối; các biến khác có cả ba ca. Chín cạnh yêu cầu hai đầu mút khác ca.

Kiến thức và công cụ cần chuẩn bị

Kiến thức

CSP: variables, domains, constraints; partial và complete assignment.
Backtracking search và kiểm tra consistent.
MRV, degree, LCV và forward checking.
Khôi phục miền khi quay lui, kiểm tra nghiệm hoàn chỉnh.

Công cụ

Python 3 · Google Colab hoặc Jupyter Notebook.

Thư viện chuẩn copy và Pandas để lưu trace, lập bảng so sánh.

Nội dung thực hành

PHÂN CA KHẢO SÁT DU LỊCH

7 địa điểm, 3 ca trong ngày

Ban tổ chức phân bảy hoạt động khảo sát vào các ca Sáng, Chiều, Tối. Hai địa điểm nối trực tiếp dùng chung một nhóm thiết bị lưu động nên không được xếp cùng ca.

KS · Khách sạnChỉ Sáng

HA · Phố cổ Hội AnChỉ Tối

State là partial assignment. Mỗi thao tác thử gán một ca cho biến chưa gán; mục tiêu là lịch đủ 7 địa điểm thỏa mọi ràng buộc.

INPUT

VARIABLES, SLOTS, EDGES, DOMAINS

use_mrv, use_lcv, use_fc

OUTPUT

solution, valid, recursive_calls, assignments_tried, backtracks, max_depth, trace

Hàm tìm kiếm trả solution, stats, trace; valid được tính bằng validate_solution.

Dữ liệu CSP bắt buộc7 variables · 9 cạnh · 17 giá trị miền

1VARIABLES = ["KS", "CR", "CH", "BMK", "ST", "NHS", "HA"]
2SLOTS = ["Sáng", "Chiều", "Tối"]
3EDGES = [("KS", "CR"), ("KS", "CH"), ("CR", "BMK"),
4         ("CR", "CH"), ("BMK", "ST"), ("BMK", "NHS"),
5         ("CH", "NHS"), ("CH", "HA"), ("NHS", "HA")]
6DOMAINS = {v: SLOTS.copy() for v in VARIABLES}
7DOMAINS["KS"] = ["Sáng"]
8DOMAINS["HA"] = ["Tối"]

Thứ tự biến: KS → CR → CH → BMK → ST → NHS → HA.

Thứ tự ca: Sáng → Chiều → Tối. NEIGHBORS được xây hai chiều theo thứ tự EDGES.

Quy ước đếm và cấu hình kiểm thử

recursive_calls tăng ở đầu mọi lời gọi, kể cả lời gọi phát hiện nghiệm.
assignments_tried tăng ngay trước mỗi lần kiểm tra giá trị.
backtracks tăng khi gỡ một phép gán đã thực hiện.
max_depth là số biến đã gán lớn nhất.

Cấu hình	use_mrv	use_lcv	use_fc	Output
Cơ sở	False	False	False	Trace: 15 dòng đầu + 10 dòng cuối
Tăng cường	True	True	True	Toàn bộ trace

Mô phỏng từng bước

ĐỒ THỊ RÀNG BUỘC

Cơ sở · Backtracking

0/ 496 vi bước

SángChiềuTốiViền đậm: biến đang xét

INITCODE 3 · 1.1

Assignment rỗng; KS có miền {Sáng}, HA có miền {Tối}.

Mã địa điểm và danh sách kề

KSKhách sạnCR · CH

CRCầu RồngKS · BMK · CH

CHChợ HànKS · CR · NHS · HA

BMKBiển Mỹ KhêCR · ST · NHS

STBán đảo Sơn TràBMK

NHSNgũ Hành SơnBMK · CH · HA

HAPhố cổ Hội AnCH · NHS

Terminal Outputprint(variant) + print_trace()

Phần output của cấu hình đang chọn; trace chỉ in sau khi tìm kiếm kết thúc. Bước 5 in cả hai cấu hình và DataFrame.

Trace đã ghi0 dòng · snapshot hiện tại

Step	Depth	Event	Variable	Value	Assignment
Chưa có dòng trace.

So sánh hai cấu hìnhCơ sở / Tăng cường

Variant	Solution	Valid	Recursive_Calls	Assignments_Tried	Backtracks	Max_Depth
Cơ sở	KS=Sáng, CR=Tối, CH=Chiều, BMK=Chiều, ST=Sáng, NHS=Sáng, HA=Tối	True	27	52	19	7
Tăng cường	KS=Sáng, HA=Tối, CH=Chiều, CR=Tối, NHS=Sáng, BMK=Chiều, ST=Sáng	True	8	7	0	7

Các bước thực hiện

BƯỚC 01

Biểu diễn và kiểm tra CSP

Xây dựng NEIGHBORS hai chiều theo thứ tự xuất hiện của EDGES.
Kiểm tra 7 biến, 9 cạnh không lặp, miền không rỗng và tổng kích thước miền bằng 17.
Viết validate_solution để kiểm tra đủ biến, hai ràng buộc cố định và mọi cạnh khác ca.

Code khungPython 3

1def build_neighbors(variables, edges):
2    # TODO: tạo dict danh sách kề hai chiều
3    pass
4
5def validate_solution(assignment, variables, domains, edges):
6    # TODO: kiểm tra complete và consistent
7    pass

KẾT QUẢ MONG ĐỢI

7 variables · 9 cạnh không lặp · 17 giá trị miền. KS chỉ nhận Sáng; HA chỉ nhận Tối.

Tiêu chí đánh giá

Rubric của bài Lab10 điểm

TT	Tiêu chí	Minh chứng cần có	Điểm
1	Biểu diễn CSP	Dữ liệu, NEIGHBORS và kiểm tra 7 biến/9 cạnh/17 giá trị đúng.	1,5
2	Backtracking cơ sở	Goal test, consistent, đệ quy và quay lui đúng; có trace.	2,0
3	MRV, degree và LCV	Ba quy tắc chọn biến/giá trị và tie-break đúng.	2,0
4	Forward checking	Xóa miền, phát hiện miền rỗng và khôi phục đầy đủ.	2,0
5	Kiểm thử và đối chiếu	Hai nghiệm hợp lệ; bảng 2 dòng và bộ đếm khớp.	1,5
6	Trình bày và minh chứng	Notebook đúng tên; output và ảnh tổng hợp rõ ràng.	1,0
Tổng			10

Sản phẩm phải nộp

.ipynb

Notebook

AI2004_Lab5A_MSSV_HoTen.ipynb

Họ tên, mã số sinh viên, lớp và tên Lab.
Phần mô hình hoặc phân tích bắt buộc trong các bước thực hiện.
Code hoàn thành, output tương ứng và các bảng kết quả được yêu cầu.

01 ảnh

Ảnh tổng hợp gửi nhóm Zalo

Output kiểm tra 7 variables, 9 cạnh, tổng kích thước miền 17.
Trace cơ sở có ASSIGN, REJECT và BACKTRACK.
Trace 8 dòng của cấu hình tăng cường.
Bảng so sánh 2 cấu hình kèm hai nghiệm Valid = True.

Ghép toàn bộ output quan trọng thành 01 ảnh duy nhất, chữ và số đọc được. Ảnh không thay thế notebook.