bicriteria 최단 경로 문제가 np 완료되었음을 증명할 수있는 방법을 찾고 있습니다. , 길이와 무게와 그래프가 주어집니다 는, 나는 내가해야 내가 아는 총 길이 < = L 및 무게 < = W.간단한 감소 (NP 완전성)
를 T로 A는 s의 그래프에서 경로가 존재하는지 알 필요가 NP 완전한 문제를 가져 와서이 것을 줄이십시오. 3-SAT, 독립 세트, 정점 커버, 해밀턴 사이클 및 3 차원 매칭과 같은 문제를 선택할 수 있습니다.
어떤 아이디어가 실행될 수 있습니까?
감사합니다.
Google을 사용해 보셨습니까? 3 명중는 다음과 같습니다
http://www.jstage.jst.go.jp/article/ieejeiss/128/3/128_416/_article
기사는 유료이지만, 구글 캐시는 선행 중요한 비트 공급 :
는 "불행하게도합니다 (bicriteria 케이스 포함) 다목적 경우 NP입니다 . - 전체 (3)
과 기준 포인트 :
(3) M. Garey 및 D. 존슨 : 컴퓨터 및 다루기 힘듦 : NP-완전성 (Completeness), 뉴욕의 이론에 대한 가이드 : 프리먼 (1979)
이 양식의 질문에 대한 표준 참조 서입니다.
그래서 ... 개리와 존슨을 보셨나요? 확인을 위해 여기에 사본이 없습니다.하지만 내가 컴피 스를 할 때 그것은 나의 가야했습니다.
Garey와 Johnson이 NP 유용성 문제에 대한 대대적 인 개괄을하는 데 정말 유용합니다. 종종 문제가 거기에있을 것입니다 (저는 교수님이 이것을 체크했을 것이라고 생각합니다). 그렇지 않으면 문제의 근원이되어 여러분이 가지고있는 것을 줄일 수 있습니다. 이 경우 학생은 5 가지 문제를 선택합니다.이 문제는 G & J에서 수백 가지 (문자 그대로)보다 처리하기가 훨씬 쉽습니다. –
때때로 G & J는 파생 체인을 더 친숙한 문제 중 하나에 직접 제안하거나 직접 증명을 구축하기위한 전략을 제안하는 중간 문제를 통해 이러한 문제를 해결합니다. – Eric
교수님의 근무 시간에 들러보고 싶을 수 있습니다. 컴퓨터 과학과 1-1 시간은 당신의 교육에서 귀중한 부분입니다. 당신은 할 수있는 동안 그것을 활용해야합니다. –
불행히도, 여기에 Garey와 Johnson의 복사본이 없으며 이러한 문제 중 일부가 무엇인지 기억하지 못합니다. 빠른 정의를 제공하도록 질문을 편집하면 사람들이 쉽게 찾을 수 있습니다. (예 : 3-SAT : 부울 변수 집합과 3 개의 변수를 OR로 묶은 집합이 주어지며 일부는 무효화 될 수 있습니다. 모든 절이 참이되도록 변수에 진리 값을 할당 할 수 있습니까?) –