複数の点への最短距離について
概要
- マンハッタン距離などを最小化するにはL1距離(=中央値の距離)
- 何を最小化するかで使用する距離関数が異なる
具体例; 2Dのmatrixで目的地がいくつかあり、どこからスタートするのが最適な点になるのか
- 概要
- BFSでゴールから逆算すると、たくさんゴールがあるときは現実的ではない
マンハッタン距離を利用する場合は、X軸・Y軸の中央値が最適な場所
import statistics
def minTotalDistance(grid: List[List[int]]) -> int:
hs, ws = [], []
for h in range(len(grid)):
for w in range(len(grid[0])):
if grid[h][w] == 1:
hs.append(h)
ws.append(w)
hs.sort()
ws.sort()
hm, wm = statistics.median(hs), statistics.median(ws)
cost = 0
for h in hs:
cost += abs(h - hm)
for w in ws:
cost += abs(w - wm)
return int(cost)