マンハッタン距離が最小の座標を表示するアルゴリズム

Question

マンハッタン距離が最小の座標を表示する際、気を付けるポイントは、

座標は一つとは限らないこと、効率のいい探索方法を知りたいです。

前提

4行5列からなる配列arrがあり（下記参照）、スタート地点は[2,3]の座標とした時、
[[1, 0], [1, 2], [1, 3], [2, 2], [2, 3], [2, 4], [3, 2],[3, 3], [3,4]]のリストの中に含まれていない座標で、
最短の座標を複数表示したい。
下記の配列の場合なら、 [0, 3]、[1, 4]、 [2, 1]がともに距離が2のため、表示したいです。

arr = np.array([[[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]],
                [[1, 0], [1, 1], [1, 2], [1, 3], [1, 4]],
                [[2, 0], [2, 1], [2, 2], [2, 3], [2, 4]],
                [[3, 0], [3, 1], [3, 2], [3, 3], [3, 4]]])

# 対象となる座標を設定
target = [2, 3]

# マンハッタン距離で一番近い座標を求める
min_distance = float("inf")
closest_point = None
for i in range(4):
    for j in range(5):
        point = arr[i, j]#探索先のポイント　これでは全探索？
        distance = abs(target[0] - point[0]) + abs(target[1] - point[1])
        if  distance < min_distance:
            if list(point) not in [[1, 0], [1, 2], [1, 3], [2, 2], [2, 3], [2, 4], [3, 2],[3, 3], [3,4]]:
                min_distance = distance
                closest_point = point

# 結果を表示
print(closest_point)

試したこと

ただこれだと、複数個存在する場合に表示されないこと、そして左上から探索をかけるのが非効率だと思います。
そこでスタート地点[2,3]から上下左右に進み、隣マスも探索する方法があるのではと思ったのですが、
try exceptを使ったとしても、どのように書けばいいかわかりません。
chatGPTで調べてみたところ、ヒューステリック探索のうちの一つ、A*アルゴリズムですみたいなことが書いてあったのですが、これで検索をかけても、迷路の問題しか出てこず、もし便利な関数があったとしたらそちらも教えてほしいです。よろしくお願いいたします。

補足情報（FW/ツールのバージョンなど）

ここにより詳細な情報を記載してください。

Comments

[Zuishin]

そんな難しいことをしなくても、マンハッタン距離が指定された値となる座標を列挙し、その時に除外条件に当たるものを除けばいいのでは？

[can110]

ようするにWxHの枡でできたマップがあり、枡は空or壁である場合
スタート地点から一番近い空の枡の位置を知りたいということでしょうか。

Answer 1

元との比較はしていませんがscipy.spatial.distanceを使うと高速化できると思います。

import numpy as np
from scipy.spatial.distance import cdist

arr = np.array([[[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]],
                [[1, 0], [1, 1], [1, 2], [1, 3], [1, 4]],
                [[2, 0], [2, 1], [2, 2], [2, 3], [2, 4]],
                [[3, 0], [3, 1], [3, 2], [3, 3], [3, 4]]])
target = [2, 3]

# 除外する地点
ex = set(map(tuple, [[1, 0], [1, 2], [1, 3], [2, 2], [2, 3], [2, 4], [3, 2],[3, 3], [3,4]]))

# まず除外する
arr = set(map(tuple,arr.reshape(-1,2)))
arr = arr - ex
arr = list(arr)

A = np.array(arr)
B = np.array([target])
distances = cdist(A,B,'cityblock') # マンハッタン距離
min_indices = np.where(distances == distances.min())[0]

ret = A[min_indices].tolist()
print(ret) # [[2, 1], [0, 3], [1, 4]]

Answer 2

import numpy as np

arr = np.array([[[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]],
                [[1, 0], [1, 1], [1, 2], [1, 3], [1, 4]],
                [[2, 0], [2, 1], [2, 2], [2, 3], [2, 4]],
                [[3, 0], [3, 1], [3, 2], [3, 3], [3, 4]]])
arr = arr.reshape(-1, arr.shape[-1]).tolist()

# 対象となる座標を設定
target = np.array([2, 3])
exclude = [[1, 0], [1, 2], [1, 3], [2, 2], [2, 3], [2, 4], [3, 2],[3, 3], [3,4]]

# マンハッタン距離
distance = 0
closest_point = []
while not closest_point:
    distance += 1
    for x in range(distance+1):
        y = abs(distance - x)
        for t in map(list, [target + [x, y], target + [-x, y], target + [x, -y], target + [-x, -y]]):
            if t in arr and t not in exclude and t not in closest_point:
                closest_point.append(t)

# 結果を表示
print(f'{distance = }')
print(f'{closest_point = }')

# distance = 2
# closest_point = [[2, 1], [1, 4], [0, 3]]