그래프와 관련하여 질문이 있습니다. 각 모서리에 비용이 드는 노드와 모서리가있는 그래프를 생각해보십시오. 문제는 모든 노드를 방문하여 가로 지르는 비용의 합이 최소가되도록하는 것입니다 (여행 세일즈맨 문제 일 것 같습니다).브 루트 포스 방식과 동시 스레드 사이 선택
어떤 접근 방식을 권하고 싶습니까? 재귀에 의한 무차별 접근 방식을 사용하거나 스레드를 생성하여 여러 경로를 동시에 이동하고 비용을 계산함으로써 무차별 대입을 사용합니다.
또는이 문제에 대한 더 나은 접근 방법이 있습니까?
병렬로 작업을 수행하기 때문에 멀티 스레드 접근 방식을 사용합니다. 추가 최적화로서 일부 공유 변수에서 전체 경로의 최저 비용을 유지하고 각 스레드가 그 비용을 확인하게 할 것입니다. 순회간에 비용이 초과되면 즉시 처리가 종료됩니다.
그게 정확히 제가 가진 것입니다. 마음에 ....하지만 복잡해 질 것입니다. – hari
왜이 작업을 수행하는지 알 수 없거나 제한 조건이 무엇인지 알지 못하기 때문에 단일 스레드 재귀에 투표합니다. 쉽습니다.
큰 이유가 없습니다 ... 인터뷰를 준비하는 중 ... 회사가 이런 질문을합니다. – hari
재귀는 간단하며 무차별 적이기 때문에 멀티 스레딩을 사용하면 솔루션을 더 빨리 얻을 수 있다고 보장 할 수 없습니다. 당신은 바퀴를 재발견 전에, 콩코드 TSP 찾기를 체크 아웃 :
http://www.tsp.gatech.edu/concorde/index.html
그것은 무료로 다운로드의 소스가 포함되어 있습니다.
TSP는 NP 하드입니다. 위키 피 디아를 참조하십시오. 끔찍하게 비늘이납니다. 4 코어에서 멀티 스레딩을 사용하면 약간 큰 문제를 시도 할 때 에 비해 100, 1000 또는 1000000 번에 비해 아무런 변화가 없으므로 속도가 느려집니다. . 실제 크기의 데이터로 시도해보십시오. 완료하는 데 수년이 걸릴 수 있습니다.
하나의 솔루션은 메타 휴리스틱이며, Drools Planner (오픈 소스, 자바)와 같은 두 개의 라이브러리가 있습니다. TTP 예제를 살펴보십시오.
AOL의 친구와 채팅하지 않고 전문 웹 사이트이므로 올바른 맞춤법 및 문법을 사용해 보시기 바랍니다. –
아니면 그냥 그 사람에 대한 질문을 편집하거나이 사이트의 ** 새로운 ** 사용자이기 때문에 더 정중하게 말할 수 있습니다 .. – jgauffin
LOL ... 사람들이 대답을 얻으려면 여기에 오십시오 ... 똑똑한 것처럼 행동하지 마세요. u ... 질문에 대답하거나 여기서 나가십시오 ... 나는 사람들이 나를 위해 대답하기를 원하는 방식으로 질문을 게시합니다. 그래서, 건방진 행동을 멈추십시오. 삶의 아이를 찾으러 갈 겁니다. P – hari