Chia sẻ bài báo qua Email THUẬT TOÁN XẤP XỈ VÀ ỨNG DỤNG TÌM NGHIỆM BÀI TOÁN THUỘC LỚP NP - KHÓ
Thông tin bài báo
Ngày nhận bài: 23/02/21 Ngày hoàn thiện: 24/05/21 Ngày đăng: 27/05/21Các tác giả
Nguyễn Đình Dũng
, Trường Đại học Công nghệ thông tin & Truyền thông - ĐH Thái Nguyên
Tóm tắt
Trong bài báo này, chúng tôi giới thiệu một số bài toán thuộc lớp NP – khó (NP – Hard) và đề xuất một thuật toán xấp xỉ tìm lời giải cho bài toán tìm tập con lớn nhất, tập con có số phần tử xác định trước. Đối với mỗi bài toán tối ưu tổ hợp, hiện nay có khá nhiều phương pháp hữu hiệu với chi phí khá thấp về thời gian tính toán để tìm lời giải, có thể kể đến như thuật toán xấp xỉ nhanh. Phương pháp này đã được ứng dụng rộng rãi để giải các bài toán mà không yêu cầu đòi hỏi phải tìm được nghiệm chính xác, bởi ngay từ dữ liệu đầu vào của bài toán có thể đã là dữ liệu xấp xỉ. Vì vậy tìm được thuật toán xấp xỉ giải bài toán có chi phí thời gian tính toán thấp mà vẫn đảm bảo độ chính xác theo yêu cầu là mục tiêu của bài báo này cần đạt được. Theo cách tiếp cận này, chúng tôi xây dựng được thuật toán có độ phức tạp về thời gian tính toán là đa thức khi bài toán được xét trong không gian Euclide và nghiệm tìm được có độ chính xác chấp nhận được.
Từ khóa
Toàn văn:
PDFTài liệu tham khảo
[1] M. Garey and D. Johnson, Computers and Intractability. A Guide to the theory of NP-completeness. W. H. Freeman and Company, NewYork, 1979.
[2] J. W. Osborne, Best Practices in Data Cleaning: A Complete Guide to Everything You Need to Do Before and After Collecting Your Data, 1st Edition, Los Angeles: SAGE Publication, 2013.
[3] C. Aggarwal, Data Mining. Springer International Publishing, 2015.
[4] V. V. Shenmaier, “Solving Some Vector Subset Problems by Voronoi Diagrams,” J. Appl. Indust. Math., vol. 10, no. 4, pp. 560-566, 2016.
[5] J. Kleinberg and E. Tardos, Algorithm Design. Addison Wesley, first edition, 2006.
[6] A. Aggarwal, H. Imai, N. Katoh, and S. Suri, “Finding k points with minimum diameter and related problems,” J. Algorithms, vol. 12, no. 1, pp. 38-56, 1991.
[7] A. V. Kelmanov and S. M. Romanchenko, “An Approximation Algorithm for Solving a Problem of Search for a Vector Subset,” J. Appl. Indust. Math., vol. 6, no. 1, pp. 90-96, 2012.
[8] V. V. Shenmaier, “An Approximation Scheme for a Problem of Search for a Vector Subset,” J. Appl. Indust. Math., vol. 6, no. 3, pp. 381-386, 2012.
[9] V. V. Shenmaier, “An Approximation Scheme for a Problem of Search for a Vector Subset,” J. Appl. Indust. Math., vol. 6, no. 3, pp. 381-386, 2012.
[10] B. Aronov and S. Har-Peled, “On Approximating the Depth and Related Problems,” SIAM J. Comput., vol. 38, no. 3, pp. 899-921, 2008.
[11] A. V. Kelmanov and A. V. Pyatkin, “NP-Completeness of Some Problems of Choosing a Vector Subset,” J. Appl. Indust. Math., vol. 5, no. 3, pp. 352-357, 2011.DOI: https://doi.org/10.34238/tnu-jst.4023
Các bài báo tham chiếu
- Hiện tại không có bài báo tham chiếu