Trung tâm cá nhân
cuốn sách gpt4 ai đã làm

thuật toán - Đây có phải là cách hiểu đúng về việc chứng minh một cái gì đó là NP Complete không?

In lại Tác giả: Taklimakan Thời gian cập nhật: 2023-11-03 03:31:28 26 4
mua khóa gpt4 Nike

Theo như tôi biết, có hai bước để chứng minh rằng một vấn đề là NP-đầy đủ:

  1. Đưa ra thuật toán có thể kiểm tra lời giải của bài toán trong thời gian đa thức. Nghĩa là, một thuật toán có đầu vào là giải pháp được đề xuất cho một vấn đề và đầu ra của nó là "là" hoặc "không" tùy thuộc vào việc đầu vào có phải là giải pháp hợp lệ cho vấn đề hay không.

  2. Chứng minh rằng một vấn đề là NP-hard - Ví dụ: giả sử bạn có một oracle có thể tính toán một vấn đề NP-đầy đủ đã biết khác trong một bước. Sử dụng điều này, hãy viết một thuật toán giải quyết vấn đề này trong thời gian đa thức.

Ví dụ: giả sử chúng ta muốn chứng minh rằng bài toán sau là NP-đầy đủ:

Cho một tập hợp số nguyên S, liệu có thể cô lập một tập hợp con của các phần tử hay không S', làm Tổng các phần tử trong S' Nó có chính xác bằng S không bao gồm trong S' Tổng các phần tử còn lại trong ?

Bước 1: Xác minh thuật toán

Verify_HalfSubset(Set S, Solution sol):
    tích lũy = 0
    cho mỗi phần tử i trong sol:
        tích lũy+=tôi
        tìm kiếm tuyến tính một phần tử có cùng giá trị với i trong S.
        nếu tìm thấy thì xóa nó khỏi s, nếu không tìm thấy thì trả về false
    kết thúc cho
    tích lũy2 = 0
    với mỗi phần tử i trong S:
        tích2+=i
    kết thúc cho
    nếu accum==accum2 trả về true, ngược lại trả về false

Rõ ràng điều này chạy trong thời gian đa thức: vòng lặp for đầu tiên chạy trong O(nm) chạy trong cái thứ hai trong TRÊN) chạy vào trong.

Bước 2: Giảm

Giả sử chúng ta có một nhà tiên tri O(Đặt S, int I) Tính một bước của bài toán tổng tập con (nghĩa là có tập con các phần tử trong S có tổng bằng I) không?

Sau đó, chúng ta có thể viết thuật toán thời gian đa thức để tính bài toán bán tập hợp con của mình:

HalfSubset(Bộ S):
    tích lũy = 0
    với mỗi s trong S:
        tích lũy+=S
    kết thúc cho
    if(tích lũy%2==1) 
    // câu hỏi này cấm "chia" các giá trị thành các phần không tách rời
        trả lại NO_ANSWER
    end if
    nửa1 = O(S, tích lũy/2)
    if(half1 == NO_ANSWER)
        trả lại NO_ANSWER
    end if
    với mỗi i trong nửa1:
        tìm kiếm tuyến tính một phần tử có cùng giá trị với Half1[i] trong S
        xóa nó khỏi S.
    kết thúc cho
    nửa2 = S
    trở lại (half1 và Half2)

Ai đó có thể cho tôi biết liệu tôi có mắc phải sai lầm nào trong quá trình thực hiện không? Đây là một câu hỏi trong bài ôn tập cuối kỳ của tôi mà tôi không chắc mình đã hiểu hết.

câu trả lời hay nhất

Phần thứ hai trong câu trả lời của bạn hơi sai. Điều bạn đã nói ở bước thứ hai là bạn có thể giảm vấn đề này thành bài toán NP-đầy đủ đã biết trong thời gian đa thức. Nghĩa là, bạn đang nói rằng vấn đề này khó nhất là vấn đề NP-đầy đủ.

Điều bạn đang muốn nói là bài toán NP-đầy đủ có thể được rút gọn thành bài toán ví dụ của bạn trong thời gian đa thức. Điều này cho thấy rằng nếu bạn có thể giải bài toán này trong thời gian đa thức thì bạn cũng có thể giải được bài toán NP-đầy đủ trong thời gian đa thức, chứng tỏ rằng bài toán ví dụ của bạn là NP-đầy đủ.

Về thuật toán - đây có phải là cách hiểu đúng về việc chứng minh điều gì đó là NP Complete không? , chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/20550623/

26 4 0
Bài viết khuyến nghị: android — Thuật toán/chiến lược tìm câu đố về khách sạn
Bài viết khuyến nghị: Làm cách nào để nâng cấp Java BigInteger lên khả năng BigInteger mà không cần thực hiện các thao tác mô-đun?
Bài viết khuyến nghị: Có trình dịch ngược Java nào có thể dịch ngược chính xác các cuộc gọi đến các phương thức bị quá tải không?
Bài viết khuyến nghị: Việc quay lui có thực sự cần thiết để phát hiện chu trình bằng DFS trong biểu đồ có hướng không?
Taklimakan
Hồ sơ

Tôi là một lập trình viên xuất sắc, rất giỏi!

Nhận phiếu giảm giá taxi Didi miễn phí
Phiếu giảm giá taxi Didi
Các bài viết phổ biến trên toàn bộ trang web
Chứng chỉ ICP Bắc Kinh số 000000
Hợp tác quảng cáo: 1813099741@qq.com 6ren.com
Xem sitemap của VNExpress