NP- 완성 문제로 판명 된 사업 요구 사항이 있습니까?

Question

NP- 완전성은 나에게 대부분의 이론적이며 실제로는 정상적인 작업 환경에서 겪는 것이 아닌 것들 중 하나처럼 보입니다.

그래서 나는 누군가가 NP가 완성 된 것으로 판명 된 직장에서 문제를 해결하고 디자인을 수용하기 위해 변경해야한다는 것이 궁금합니다.

Answer 1

다른 사람들이 언급했듯이,화물을 포장하는 데 크 랩싱과 여행 판매원 문제가 아마도 가장 일반적인 "실제"NP- 완성 문제 일 것입니다.

나는 직장에서 NP가 잘 정의되지 않았기 때문에 완전하거나 불완전한 것으로 판명 될 수없는 문제를 해결하는 경향이 있습니다.

Answer 2

두 곳 이상에서 최적의 여행 지점을 찾아야하는 모든 종류의 매핑 도구는 변경없이 NP- 완료 문제

Answer 3

창고에서 파도를 최적화하는 문제는 여행 세일즈맨 문제.

즉, 당신은 선택을 기다리는 n-order가 있고, 여행 거리를 최소화하기 위해 N 최고의 주문을 찾고 있습니다.

나는 최근 에이 문제를 발견했다. 우리는 평균 사례에 잘 어울리는 근사치를 펀칭하고 사용했지만 때로는 최적의 결과를 제공 할 수 있습니다.

Answer 4

또한 Knapsack 문제 (NP-Hard)가 상당히 자주 나타납니다. 사물을 최적화하려는 유혹적인 함정입니다.

Answer 5

시뮬레이션 된 어닐링 및 압축 어닐링과 같은 NP- 완성 문제에 대한 "충분한"답변을 얻기위한 휴리스틱 근사 기술이 있다는 점은 주목할 가치가 있습니다. NP- 완료 문제를 여행 세일즈맨 문제로 줄일 수 있다면 이러한 접근 방식을 사용할 수 있습니다. (모든 NP- 완료 문제는 다른 NP- 완료 문제로 줄일 수 있지만 실제로하는 것은 때때로 엉덩이의 고통입니다.)

어쨌든, 시뮬레이션-발병 및 압축-나누기 구현이있다. 그런 것 중 하나입니다 Djinni, C ++로 작성되었으며 파이썬 바인딩이 있습니다.

Answer 6

나는 1 학년 대학생이었을 때 친구의 아버지를위한 소프트웨어를 작성하기로 동의했습니다. 리소스 예약을위한 것이 었습니다. 나는 당시에 그것을 깨닫지 못했지만 NP 완전한 문제로 판명되었습니다.

고맙게도 솔루션을 찾는 것이 허용되었습니다. 최적의 솔루션을 찾을 필요는 없었습니다. 프로그램이 실행 중이며 문제를 해결하려고하는 동안 변경 될 수있는 휴리스틱을 쓰는 것은 재미있었습니다.

나는 여름에 해결책을 제시했지만 연말마다 새로운 버전에서 작업했습니다. 그것을 팔려는 큰 계획은 평평 해졌다. 나는 마케팅 담당자보다 더 나은 개발자였습니다.

그것은 많은 재미가 있었고 실제 개발 - (최종 사용자, 요구 사항 수집, 테스트 등 - CS에서 얻지 못하는 많은 것들)에 대해 많은 것을 가르쳐주었습니다.

귀하의 질문을 해결하기 위해 - 학생들에게 특별 교육을 예약 해야하는 교사를위한 것이 었습니다. 그는 언어 치료사이자 청력 학자 였지만 비슷한 분야에 적용될 수 있습니다. 그는 기존의 교사, 교실 및 학생 활동을 통해 일할 수 있었고 학생들과 일주일에 특정 시간을 충족시켜야했습니다. 배낭 문제 또는 기타 유사한/동등한 스케줄링 문제입니다.

다시 말하지만, 해결책을 얻는 것이 괜찮 았습니다. 우리는 모든 것을 극대화하거나 최소화 할 필요가 없었습니다. 우리는 모든 학생들을 수용해야했습니다.

시나리오를 실행하는 데 사용한 테스트 사례를 해결할 수 없다는 것을 기억할 수 있습니다.

나는 그것을 마케팅 할 수 없었습니다. 대부분 내가 무엇을하고 있는지 전혀 몰랐기 때문에 시장/구매자에게 어떻게 도달 해야할지 확신하지 못했기 때문입니다.

Answer 7

여행 세일즈맨 문제는 완벽한 예입니다. 동일한 종류의 물류 문제가 항공사, 우체국 및 모든 종류의 산업에 적용됩니다.

Answer 8

또 다른 예는 지역 유통 센터, 특히 고객에게 직접 제공하는 회사 (예 : Netflix)가있는 회사는 시설 위치.

실제로, NP- 완성 문제가 현실 세계에서 관련이 있다는 생각은 운영 연구 저널에 자주 나타나는 근사 알고리즘이 나타난다는 사실에 의해 입증됩니다.

Answer 9

나는 몇 년 전에 기본 Google지도와 같이 매핑 프로그램을 진행하고있었습니다. 위치에 대한지도에 마커를 거의 넣지 만 특정 위치에서 많은 마커가 밀접하게 클러스터링되었습니다. 내 상사는 "마커를 조금만 끌 수 있도록하자"(그리고 마커에서 실제 위치로가는 라인이나 음성 버블 포인터를 가질 수 있도록하겠습니다.

나는 사용자가 이것을하는 것이 어리석은 일이라고 생각했다. 특히 그가 5 분 동안 완벽하게 만들고 줌 레벨을 바꾸면 모든 것이 잘못 될 것이라고 생각했다.

나는 각 레이블에서 해당 위치까지의 총 스크린 거리가 최소화되도록 레이블을 배치하는 방법을 찾기 위해 함수를 작성하기로 결정했습니다. 나는 이것이 NP가 완성되었다고 당시 나 자신을 확신했다고 생각하지만, 적어도 많은 경우에도 여전히 가능할 정도로 충분히 적을 수 있다고 생각합니다. (나는 우리가 NP 완료성 증거에 수업 시간에 너무 많은 시간을 보냈다고 생각한 것을 기억합니다. 대체 솔루션에는 충분하지 않습니다. 상사가 무언가를 원한다면 "NP 열심히,하지 않을 것"이라고 말할 수 없습니다. 여전히 생각해 봐야합니다 무엇.)

그런 다음 Google지도가 와서 서로의 모든 레이블을 서로 뿌렸습니다.이 레이블은 완전히 짜증납니다 (그리고 매일 저주합니다). 그러나 나는 다른 기능과 경쟁 할 수 없어서 포기했습니다. :-(