Liên quan đến các vấn đề NP-Complete đối với các vấn đề trong thế giới thực

Question

Tôi có một nắm bắt tốt về các vấn đề NP Complete; đó không phải là vấn đề. Những gì tôi không có là một ý thức tốt về nơi họ bật lên trong lập trình "thực sự". Một số (như knapsack và nhân viên bán hàng đi du lịch) là hiển nhiên, nhưng những người khác dường như không được kết nối rõ ràng với các vấn đề "thực".

Tôi đã có kinh nghiệm nhiều lần đấu tranh với một vấn đề khó khăn chỉ để nhận ra nó là một vấn đề NP hoàn chỉnh nổi tiếng đã được nghiên cứu rộng rãi. Nếu tôi đã nhận ra kết nối nhanh hơn, tôi có thể đã tiết kiệm được khá nhiều thời gian nghiên cứu các giải pháp hiện có cho vấn đề cụ thể của mình.

Có tài nguyên nào (trực tuyến hoặc in) kết nối riêng NP hoàn chỉnh với các phiên bản thực tế không?

Chỉnh sửa: Ví dụ, tôi đã làm việc trên một chương trình cố gắng phân chia học sinh thành các nhóm dựa trên độ tuổi, cấp lớp và trường gốc, về cơ bản là vấn đề phân vùng đồ thị. Tôi mất một lúc để nhận ra mối liên hệ.

Answer 1

Tôi đã tìm thấy rằng Computers and Intractability là tham chiếu chính xác về chủ đề này.

Answer 2

Thông thường các kết nối bạn đang nói về phải được chiết xuất với một cái gọi là giảm, ví dụ bạn giảm 3-SAT cho vấn đề bạn đang làm việc với và sau đó bạn có thể kết luận rằng vấn đề của bạn có cùng sự phức tạp của nó.

Đoạn này là không nhỏ, vì bạn phải chứng minh rằng bạn có thể biến mọi trường hợp vấn đề l của một tiếng NP-Hard vấn đề L vào một thể hiện c của vấn đề của bạn C sử dụng một thuật toán polinomyal xác định.

Vì vậy, ngoại trừ từ học tương quan basical của các vấn đề NP-Hard chung sử dụng bộ nhớ của bạn, không có cách nào để chắc chắn nếu một vấn đề tương tự như một NP-Hard mà không cố gắng đoán và sau đó chứng minh nó , bạn phải thông minh.

Answer 3

đây là một liên kết wiki: http://wapedia.mobi/en/List_of_NP-complete_problems Thông báo nó nói

Danh sách này là không có cách nào toàn diện (có hơn 3000 các vấn đề được biết đến NP-đầy đủ)

lẽ nó sẽ là một nhiệm vụ tuyệt vời nếu bất cứ ai có thể biên dịch danh sách đó.

Một nhà lý thuyết nên cố gắng hiểu/chứng minh vấn đề NP-Complete/Hard. Nhưng, một lập trình viên không có thời gian đó. Anh ta cần một danh sách.

Tôi có đúng không?

Tôi nghĩ bạn nên google nó. Và, đọc qua tất cả các liên kết. Thêm mọi sự cố mới được tìm thấy trong liên kết vào danh sách của bạn.

Hy vọng nó giúp

PS: Đừng quên gửi danh sách khi bạn đã hoàn tất: P

Answer 4

Đối với phát triển trực giác tốt hơn cuốn sách "Các Thuật toán thiết kế bằng tay, Second Edition" bởi Skiena (trích đoạn trên các cuốn sách của Google) đơn giản là tuyệt vời.

1. Danh sách ở phía sau với những vấn đề (bao gồm cả các vấn đề khó khăn), mà bao gồm một minh hoạ và một thảo luận (thường) với một thế giới thực dụ.
2. Bao gồm cả lý thuyết và mặt thực tế của sự vật, thường là nói về mã thực tế.

đọc excepts trực tuyến tại đây (xem một số ví dụ trong các chương 14): http://books.google.dk/books?id=7XUSn0IKQEgC&printsec=frontcover#v=onepage&q&f=false

Chương 16 (không trực tuyến) thảo luận về một số vấn đề khó khăn, trong đó có phân vùng đồ thị.