2.1.2 Các nghiên cứu liên quan
Bài toán OCST đã được chứng minh là bài toán NP-khó [9], điều này có nghĩa là không
tồn tại thuật toán giải chính xác bài toán với thời gian đa thức, trừ khi P = NP. Trên thực tế,
những thuật toán chính xác đã được đề xuất cũng không thể giải quyết những bài toán có kích8
thước nhỏ với thời gian chấp nhận được [5]. Do đó hiện nay việc phát triển thuật toán tìm
kiếm hiệu quả đưa ra những lời giải chất lượng cao cho bài toán OCST là hướng nghiên cứu
đang được quan tâm.
Để giải bài toán OCST, một số thuật toán chính xác được đề xuất điển hình là thuật toán
nhánh cận của Ahuja và Murty [21], tuy nhiên chúng không thật sự hiệu quả khi giải quyết
bài toán kể cả với những bài toán kích thước nhỏ [12]. Rất nhiều những giải thuật xấp xỉ đã
được phát triển tuy nhiên chất lượng lời giải khá giới hạn. Giải thuật heuristic đầu tiên được
Palmer và Kershenbaum [2] đề xuất. Trong [8], Chou và cộng sự đã dựa trên mã hóa của người
tiền nhiệm tạo ra một số nhiễm sắc thể bất hợp pháp (nghĩa là không phải cây bao trùm). Kết
hợp khởi tạo ngẫu nhiên đơn giản, hầu hết các nhiễm sắc thể sẽ là bất hợp pháp bởi ba lý do:
thiếu nút I, tự vòng lặp, hoặc có chu kỳ. Quy trình sửa chữa phức tạp sẽ được sử dụng ở mỗi
thế hệ (chi phí điện toán), và sau khi sửa chữa, con cái của các xuyên chéo và đột biến khó mà
biểu trưng cho các giải pháp mà kết hợp cấu trúc bên dưới của bố mẹ chúng (vị trí và khả năng
di truyền xấu nhất). Lin Lin và Misuo Gen trong [15] đã đề xuất một cách mã hóa dựa trên
PrimPred, mã hóa dựa trên người tiền nhiệm có cải tạo. Việc khởi tạo phụ thuộc vào một thuật
toán cây bao trùm ngẫu nhiên cơ bản. Quy trình cụ thể của cách mã hóa và giải mã này được
giới thiệu trong [10].
<p>MỤC LỤC</p> <p>Trang phụ bìa</p> <p>Lời cam đoan</p> <p>Lời cảm ơn</p> <p>Mục lục</p> <p>Danh mục các chữ viết tắt</p> <p>Danh mục các bảng</p> <p>Dan ...
<p>MỤC LỤC</p> <p>PHẦN MỞ ĐẦU . 1</p> <p>1. Tính cấp thiết của đề tài.1</p> <p>2. Mục đích, ý nghĩa của việc nghiên cứu đề tài luận án .2</p> <p>3. Kết cấu ...
<p>MỤC LỤC</p> <p>LỜI CAM ĐOAN . 1</p> <p>LỜI CẢM ƠN . 2</p> <p>MỤC LỤC . 3</p> <p>DANH MỤC CÁC CHỮ VIẾT TẮT. 5</p> <p>MỞ ĐẦU. 6</p> <p>1. Những ghi nhận ...
<p>Chương 2. CƠ SỞ LÝ LUẬN VỀ XÂY DỰNG MÔ HÌNH KẾ</p> <p>TOÁN QUẢN TRỊ CHI PHÍ TRONG CÁC DOANH NGHIỆP</p> <p>XÂY DỰNG GIAO THÔNG</p> <p>2.1 Khái quát cơ sở l ...
<p>1.2. NỘI DUNG KẾ TOÁN TRÁCH NHIỆM TRONG DOANHNGHIỆP</p> <p>1.2.1. Khái niệm và bản chất của trung tâm trách nhiệm</p> <p>a. Khái niệm trung tâm trách nhiệm ...
Hỗ trợ download nhiều Website
Hỗ trợ nạp thẻ qua Momo & Zalo Pay
Khi đăng ký & nạp thẻ ngay Hôm Nay
