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

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.