알고리즘 - NP- hard

Question

안녕하세요~ http://inverse90.tistory.com/m/entry/PNP-NP-Hard-NP-Complete NP , NP - hard 에 대한 글을 읽다가 궁금한 점이 있어 찾아왔습니다. 예로 제시된 TSP 에 대한 질문인데요. [TSP 문제는 '외판원 문제'로 &#34;여러 도시를 순환하는 가장 짧은 길&#34;을 찾는 문제입니다 :https://ko.wikipedia.org/wiki/%EC%99%B8%ED%8C%90%EC%9B%90_%EB%AC%B8%EC%A0%9C] 1) Decision problem - 거리 x 보다 짧은 route 을 찾을 수 있는가?(Yes/ No) 라는 문제는 NP-Complete 인 반면에2) Best Route - 최단 거리 x 를 구하라라는 문제는 NP-Hard 라고 알고 있습니다. 짧은 생각으로는, 1번의 경우도 - X보다 짧은 Route 을 찾는 문제 - 다항시간안에 해결이 불가능하여, NP-hard 가 되어야 하지 않나 하는 생각이 들었는데요. 왜냐면, 1) 주어진 x 보다 짧은 루트가 1개 뿐일때나, 2) 주어진 x 가 최적의 길로 더 짧은 루트가 없을때. 와 같은 경우가 있기 때문이라고 생각했습니다. 제가 np-hard 에 대한 개념을 잘못이해하고 있을지도 모르겠습니다. 부족한 질문 읽어주셔서 감사합니다. 답글 남겨주시면 감사하겠습니다!

알고리즘 - NP- hard

0개의 답변

#np 목록