複数の点への最短距離

複数の点への最短距離について

タグ 距離 L1 L2 マンハッタン距離

概要

  • マンハッタン距離などを最小化するには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)

参考