Bài toán Traveling Salesman dùng GA
1. Giới thiệu bài toán người đưa thư (phát biểu khác là bài toán người đi buôn - Traveling Salesman Problem – TSP )Đây là một bài toán kinh điển trong lí thuyết đồ thị và khoa học máy tính bởi độ phức tạp đa thức của nó nếu tính toán theo phương pháp thông thường .
Để tìm được đường đi ngắn nhất qua tất cả các đỉnh , sao cho mỗi đỉnh chỉ đi qua đúng một lần và sau đó trở về đỉnh đầu xuất phát . Trước tiên là ta tìm tất cả các con đường thỏa mãn điều kiện trên , trong số các con đường đó , ta tiến hành so sánh và tìm ra con đường ngắn nhất .
Như vây rõ rảng để tìm được lời giải bải toán , ta phải tiến hành vét cạn hết tất cả các khả năng có thể xảy ra đối với đường đi . Đó sẽ là sự hoán vị của n đỉnh . Kết quả cuối cùng là một tập hợp có thứ tự các đỉnh sao cho đường đi tạo từ các đỉnh đó là đường ngắn nhất .
/4.png "machinelearning-clustering-(gmm)")
.jpg "SVM (SUPPORT VECTORMACHINE)")
.jpg "PHƯƠNG PHÁP TẠO CÂY ĐỊNH DANH ID3")
