Bài viết 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. | TNU Journal of Science and Technology 226 07 175 - 181 APPROXIMATION ALGORITHM AND APPLICATION FOR A NP-HARD PROBLEM SOLVING Nguyen Dinh Dung TNU - University of Information Technology and Communication ARTICLE INFO ABSTRACT Received 23 02 2021 In this paper we introduce some NP-hard problems and present an approximation algorithm to find a cluster subset of the largest Revised 24 5 2021 cardinality and subset of points of a given cardinality. There is a Published 27 5 2021 radically different way of dealing with difficult optimization prob- lems solve them approximately by a fast algorithm. This approach is KEYWORDS particularly appealing for applications where a good but not necessarily optimal solution will suffice. Besides in real-life Polynomial-time algorithm applications we often have to operate with inaccurate data to begin. Approximation algorithm Under such circumstances going for an approximate solution can be a NP Hard particularly sensible choice. Algorithm that is given is a polynomial- time approximation algorithm. This algorithm finds a feasible solution Euclide space to problems when we consider the problem of searching a subset in a Fast Approximate finite set of points of Euclidean space. 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Ó Nguyễn Đình Dũng Trường Đại học Công nghệ thông tin và Truyền thông - ĐH Thái Nguyên THÔNG TIN BÀI BÁO TÓM TẮT Ngày nhận bài 23 02 2021 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 Ngày hoàn thiện 24 5 2021 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. Ngày đăng 27 5 2021 Đố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 TỪ KHÓA 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 Thuật toán đa thức hỏi phải tìm được nghiệm chính
