各行が異なることを実行できる異なる「駅」を表すルートを最適化するためのExcel式
この質問をどのように組み立てるかわからなかった。
実行可能な最小限の例を次に示します。
- ジェーンはA、B、Dを行うことができます。彼女は1km離れています。
- ジャックはB、D、Fを行うことができます。彼は1.5km離れています。
- マーシャルはE、F、Aを行うことができます。彼は20km離れています。
- ポリーはE、D、Cを行うことができます。彼女は10km離れています。
- ジェームズはC、F、Bを行うことができます。彼は15km離れています。
シートには、各人の行と各アクションの列、AFがあります。
最小の訪問者数でA、C、Fを完了するために必要な人の組み合わせを見つけたいと思います。2つの組み合わせが有効な場合は、距離が最も小さいものが必要です。
（したがって、上記の解決策はJaneとJamesです）
最初の行には、A、B、C、D、E、Fの各チェックボックスがあります。A、C、Fを選択しました。
訪問する必要のある人を強調表示または色分けするために、どの式を使用しますか？これがExcelで実行できない場合、プログラミング言語を使用して実装できるように、これを解決するためのアルゴリズムは何と呼ばれますか？
回答
終わった！
概念
強引な。訪問する人のすべての組み合わせのルート距離を計算します。必要なすべてのタスク（AF）を提供しない組み合わせは無視してください。ルート距離が最も短いルートを選択します。
実装
アイデアは、必要な計算を減らすためにバイナリ表現を使用することです。各人に整数の1ビットが割り当てられているとします。たとえば、1001は人1と人4を訪問することを意味します。したがって、8人の場合、訪問する人の組み合わせは2 ^ 8-1 = 255になります。1..255という番号の行で組み合わせを作成します。
今、私たちはすべての人に割り当てられたタスクに対して同じことをします。タスクAはビット1、Bはビット2 ...などです。したがって、人物010がタスクマスク（TM）0101のタスクを提供する場合、人物2はAとCを提供し、人物001はTM1000を提供します。
人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（...）、ルート距離列、を使用して最適なルートxを見つけます。 0）その最小ルート距離に一致します。xをビットx0 .. x7に分割し、条件付き書式を使用して、最適なルートにいる各人物を強調表示します。