Bài viết sưu tầm

2.2 Các thuật toán giải quyết bài toán

Có nhiều phương pháp tiếp cận để giải bài toán người bán hàng tuy nhiên có hai giải thuật phổ biến dùng để giải bài toán này là giải thuật di truyền và giải thuật đàn kiến (Ant Colony).

2.2.1 Giải thuật di  truyền

            Giải thuật di truyền thường dùng để giải cho nhiều lớp bài toán và giải thuật này cũng có thể dùng để giải cho bài toán người bán hàng, tuy nhiên khi sử dụng giải thuật này và triển khai trên máy tính thì thời gian chạy chương trình khá lâu vì việc biểu diễn nhiễm sắc thể cho n thành phố mà người bán hàng đi qua là khá khó khăn, vì ta có n thành phố, nếu dùng chuỗi nhị phân để biểu diễn nhiễm sắc thể cho n thành phố đó thì ta tốn là n*log₂(n) bit với mỗi thành phố ta cần biểu diễn log₂(n) bit. Từ đó không gian tìm kiếm rất rộng và phức tạp nên bắt buộc người lập trình phải áp dụng thuật toán Greedy(thuật toán tham lam) nhiều lần vì vậy chương trình chạy khá chậm.

2.2.2. Giải thuật AntColony

            Bài toán người bán hàng hoàn toàn có thể giải bằng giải thuật AntColony, thuật toán này có thể áp dụng cho nhiều lớp bài toán. Để có thể hiểu hơn về thuật toán này chúng ta có thể tìm hiểu đặc điểm hoạt động trong tự nhiên của đàn kiến và từ đó có thể hiểu hơn về thuật toán AntColony.