각 행이 서로 다른 작업을 수행 할 수있는 서로 다른 "역"을 나타내는 경로를 최적화하기위한 Excel 공식
이 질문의 틀을 잡는 방법을 잘 모르겠습니다.
다음은 실행 가능한 최소한의 예입니다.
- Jane은 A, B, D를 할 수 있습니다. Shes는 1km 떨어져 있습니다.
- Jack은 B, D, F를 할 수 있습니다. 그는 1.5km 떨어져 있습니다.
- 마샬은 E, F, A를 할 수 있습니다. 그는 20km 떨어져 있습니다.
- Polly는 E, D, C를 할 수 있습니다. 그녀는 10km 떨어져 있습니다.
- James는 C, F, B를 할 수 있습니다. 그는 15km 떨어져 있습니다.
시트에는 각 사람에 대한 행과 각 작업 (AF)에 대한 열이 있습니다.
최소한의 방문 인원으로 A, C, F를 완료하기 위해 어떤 조합으로 가야하는지 찾고 싶습니다. 두 가지 조합이 유효하다면 거리가 가장 작은 조합을 원합니다.
(따라서 위의 해결책은 Jane과 James입니다)
첫 번째 행에는 A, B, C, D, E, F의 각 항목에 대한 확인란이 있습니다. A, C, F를 선택했습니다.
방문해야하는 사람들을 강조 표시하거나 색상 코드를 지정하는 데 어떤 공식을 사용해야합니까? 이것이 엑셀에서 할 수 없다면 프로그래밍 언어를 사용하여 구현할 수 있도록이 문제를 해결하는 알고리즘을 무엇이라고 부를까요?
답변
끝났다!
개념
무차별 대입. 방문 할 모든 사람의 조합에 대한 경로 거리를 계산하십시오. 모든 필수 작업 (AF)을 제공하지 않는 조합은 무시하십시오. 경로 거리가 가장 낮은 경로를 선택하십시오.
이행
아이디어는 이진 표현을 사용하여 필요한 수학을 줄이는 것입니다. 각 사람이 정수로 1 비트를 할당 받았다고 가정 해 봅시다. 예를 들어 1001은 방문한 사람 1과 사람 4를 의미합니다. 따라서 8 명의 사람이 있다면 2 ^ 8-1 = 255 명의 사람 조합이 방문합니다. 1..255로 번호가 매겨진 행에서 조합을 만들 것입니다.
이제 모든 사람에게 할당 된 작업에 대해 동일한 작업을 수행합니다. 작업 A는 비트 1, B는 비트 2 ... 등등. 따라서 사람 010이 작업 마스크 (TM)가 0101 인 작업을 제공하면 사람 2는 A와 C를 제공하고 TM 1000을 사용하는 사람 001은 D 만 제공합니다.
011 명 (001 및 010)을 방문 할 계획이라면 제공되는 결합 된 작업은 다음과 같습니다.
=BITOR("TM for 001", "TM for 010") which will result in TM 1101 (tasks A, C, D)
모두에게 제공되는 결합 된 작업은 다음과 같습니다.
=BITOR("TM for 001", BITOR("TM for 010", BITOR("TM for 100",... "TM for 10000000"))))))))
따라서 임의의 사람 x 조합에 의해 어떤 작업이 제공되는지 알려면 관련 TM 만 함께 BITOR해야합니다.
=BITOR("TM for 001" * x0, BITOR("TM for 010" * x1, BITOR("TM for 100" * x2,... "TM for 10000000" * x7))))))))
여기서 xi는 x의 i 번째 비트입니다.
=BITAND(1,BITRSHIFT(x,i))
마찬가지로 사람 조합 / 경로 x의 총 거리를 결정합니다.
"Person 1 distance" * x0 + "Person 2 distance" * x1 +... "Person 8 distance" * x7
이제 TM y를 가진 사람 x에 대해 필요한 모든 작업 z를 수행 할 수 있는지 확인합니다 (즉, 유효한 경로).
=IF(BITAND(y,z) = z, "All tasks offered by x", "All tasks cannot be done")
And the distance for valid routes only
=IF(BITAND(y,z) = z, *distance calc above*,"") so invalid routes are blank ""
이제 가능한 모든 조합 (예 : (1..255))에 대해 이것을 계산하고 MIN (...)으로 유효한 최소 경로 거리 를 찾은 다음 MATCH (MIN (...), route distances column , 0) 해당 최소 경로 거리와 일치합니다. x를 비트 x0 .. x7로 나누고 조건부 서식을 사용하여 최상의 경로에있는 각 사람을 강조 표시합니다.