참조 그래프 :그래프의 가장자리를 병렬로 방문하는 알고리즘?
내가 그래프의 모든 모서리를 테스트하는 프로그램을 쓰고 있어요. 이 프로그램은 공통 노드를 공유하지 않는 경우에만 그래프의 가장자리를 병렬로 테스트 할 수 있습니다. 내 문제는 가능한 가장 효율적인 방법으로 가장자리를 테스트하지 않는 옵션이 있어야한다는 사실에서 비롯됩니다.
상기 그래프에 평행 에지들의 가장 효율적인 선택을 테스트하는 경우
는AB,
DE 모서리 및
CF 모두 제 중에
AD,
BC 및
EF 뒤에 병렬 번째 사이클에서 시험 할 수있다. 이 경우에만 세 번째주기에 남은 것은
BE입니다.
한 번에 두 개의 평행 한 모서리로 제한된다면 여러면에서 모서리를 방문 할 수 있었지만 다른 모서리보다 더 효율적이었습니다. 예를 들어, AB 및 CF을 먼저 방문한 다음 BC 및 AD을 방문 할 수 있습니다. 이 경우 BE, DE 및 EF은 총 5 회 동안 한 번에 하나씩 테스트해야합니다. 이것은 AB과 DE을 먼저 방문하는 것보다 덜 효율적입니다. BC과 EF 초, AD과 BE, 마지막으로을 총 4 회의 주기로 끝내십시오.
그런 방식으로 그래프를 방문하는 가장 효율적인 경로를 찾기 위해 적용 할 수있는 알고리즘이나 연습이 있습니까? 내 그래프는 다양한 크기와 연결성을 지니고있어서 원하는 경우에도 개인적으로 해결할 수 없습니다.
도움이나 방향에 대해 감사드립니다. 그래프 이론에 대한 교훈을 얻은 지 꽤 오랜 시간이 걸렸습니다. 그래서이 자연이 존재하는지 기억하지 못합니다. 나는 현재 이론적으로이 문제에 접근하고 있으며 아직이 측면에서 어떤 종류의 프로그래밍을 시도하고 구현하기 시작하지 않았다. 따라서 제 질문이 다른 곳으로 향하는 것이 더 낫다면 제 질문을 관련 스택 교환 사이트로 옮기는 것이 행복 할 것입니다.
그래야 그래프상의 일치하는 - https://en.wikipedia.org/wiki/Matching_(graph_theory)을 원하는 것처럼 들립니다. 그러나 그래프를 분석하여 처음에는이 일치 (또는 모서리의 다른 파티션)를 찾을 필요가 없습니까? 병렬 '테스트'단계 전에 직렬 사전 처리 단계를 수행하는 것이 좋습니까? – gilleain
나는 당신이 준 링크를 현재 읽고 있는데, 내가 말하는 것에 대해 논의하는 것으로 보인다. 그렇다. 질문의 두 번째 부분이 간다면, 나는 당신이 무엇을 의미하는지 명확하게 알지 못하고 더 명확하게 설명 할 수 있습니다. – JustinCoplin
당신이 병렬 처리를 위해 당신의 엣지를 분할 (분할)하는 방법은 어쨌든 엣지의 횡단을 포함 할 것이므로 어떤 병렬 이득을 얻을 지 확신 할 수 없다는 것을 의미합니다. – gilleain