N 명의 직원이있는 소규모 회사의 이사가 다른 직원에게 주간 보고서를 보내야하는 직원 간의 네트워크를 설정하기 위해 고용되었습니다. 또는 그들의 보고서는 각 직원에게 중요합니다. 그들의 일의 중요성 그들은 일주일에 몇 번의 보고서를 보내야합니다
두 명의 직원간에 메시지가 전달되는 데 걸리는 시간을 측정했습니다. 예산 삭감으로 인해 네트워크는 직원간에 N-1 연결 만 가질 수 있으며 하나의 메시지를 보낼 때 사용하는 기술의 단순성으로 인해 전체 네트워크가 전달 될 때까지 기다려야 함 (한 번에 하나의 메시지 만)
당신이 얻는 것은 N-직원 수, 당신은 근로자 i의 보고서가 매주 발송되는 횟수 인 Ki를 얻습니다 .Tij는 메시지가 직원 i에서 직원 j로 이동하는 시간을 나타냅니다 1 <= N <= 13
0 <= Ki <= 10 ^ 3
0 <= Tij <= 10 ^ 3
Tij = Tji, Tii = 0
처음에 나는 가장 최적의 네트워크가 별 (트리) 일 것이라고 가정했고, 필요한 것은 중앙에있는 노드를 결정하는 것 뿐이며, 우리는 최대 13 개의 N으로 제한 되었기 때문에 무차별 대입하고 시도하기로 결정했습니다. 그 시도는 실패했습니다. 이것이 가장 최적의 네트워크 구성이 아니었기 때문입니다 (또는 테스트 사례에서 나에게 표시됨). 그런 다음 최소 스패닝 트리 또는 직원이 만든 각 전체 그래프를 찾아서 해결할 수있을 것이라고 생각했지만 최소 스패닝 트리가 여러 개 있고 모두가 이미 종이에 실패한이 문제에 대해 똑같이 좋은 것은 아니기 때문입니다.
나는 현재 약간의 아이디어가 부족하므로 어떤 방향을 향 해야하는지에 대한 힌트가 좋을 것입니다.
13 개의 노드에 13 ^ 11 ~ 1.8e12 스패닝 트리가 있으므로 무차별 대입은 문제가되지 않습니다. 의도 된 솔루션은 동적 프로그래밍이라고 생각합니다. 비어 있지 않은 노드 하위 집합과 하위 집합 (루트)에 속하는 구별 노드로 구성된 각 쌍에 대해 루트가 하위 문제뿐만 아니라 하위 집합 외부의 모든 노드를 나타내는 하위 문제에 대한 최적의 솔루션을 계산합니다. 1 노드 세트는 명백한 기본 사례입니다. 더 큰 하위 문제의 경우 주어진 세트에서 루트를 제외한 모든 파티션에 대해 동적 하위 프로그램을 사용하여 최적화하십시오. 결합 된 하위 솔루션에 추가되는 비용은 해당 링크를 사용하는 통신 수에 의해 가중치가 부여 된 루트에서 하위까지의 링크 비용입니다.
이 기사는 인터넷에서 수집됩니다. 재 인쇄 할 때 출처를 알려주십시오.
침해가 발생한 경우 연락 주시기 바랍니다[email protected] 삭제
몇 마디 만하겠습니다