Thuật toán xấp xỉ và ứng dụng tìm nghiệm bài toán thuộc lớp np

Thuật toán xấp xỉ và ứng dụng tìm nghiệm bài toán thuộc lớp np - khó

0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Đình Dũng Nguyễn

Ngôn ngữ: Vie

Ký hiệu phân loại: 510 Mathematics

Thông tin xuất bản: Tạp chí Khoa học và Công nghệ Đại học Thái Nguyên, 2021

Mô tả vật lý: 175-181

Bộ sưu tập: Metadata

ID: 403143

Thêm vào giỏ Liên kết toàn văn

Trong bài báo này, chúng tôi giới thiệu một số bài toán thuộc lớp NP - khó (NP - Hard) và đề xuất một thuật toán xấp xỉ tìm lời giải cho bài toán tìm tập con lớn nhất, tập con có số phần tử xác định trước. Đối với mỗi bài toán tối ưu tổ hợp, hiện nay có khá nhiều phương pháp hữu hiệu với chi phí khá thấp về thời gian tính toán để tìm lời giải, có thể kể đến như thuật toán xấp xỉ nhanh. Phương pháp này đã được ứng dụng rộng rãi để giải các bài toán mà không yêu cầu đòi hỏi phải tìm được nghiệm chính xác, bởi ngay từ dữ liệu đầu vào của bài toán có thể đã là dữ liệu xấp xỉ. Vì vậy tìm được thuật toán xấp xỉ giải bài toán có chi phí thời gian tính toán thấp mà vẫn đảm bảo độ chính xác theo yêu cầu là mục tiêu của bài báo này cần đạt được. Theo cách tiếp cận này, chúng tôi xây dựng được thuật toán có độ phức tạp về thời gian tính toán là đa thức khi bài toán được xét trong không gian Euclide và nghiệm tìm được có độ chính xác chấp nhận được., Tóm tắt tiếng anh, In this paper, we introduce some NP-hard problems and present an approximation algorithm to find a cluster (subset) of the largest cardinality and subset of points of a given cardinality. There is a radically different way of dealing with difficult optimization prob-lems: solve them approximately by a fast algorithm. This approach is particularly appealing for applications where a good but not necessarily optimal solution will suffice. Besides, in real-life applications, we often have to operate with inaccurate data to begin. Under such circumstances, going for an approximate solution can be a particularly sensible choice. Algorithm that is given is a polynomial-time approximation algorithm. This algorithm finds a feasible solution to problems when we consider the problem of searching a subset in a finite set of points of Euclidean space.

1. Đọc trực tuyến

1. Đọc trực tuyến

Tạo bộ sưu tập với mã QR