質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.44%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Q&A

解決済

2回答

1598閲覧

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

ikevo

総合スコア5

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

0グッド

1クリップ

投稿2023/03/20 04:04

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

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

前提

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/ツールのバージョンなど)

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Zuishin

2023/03/20 04:20

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

2023/03/20 04:58

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

回答2

0

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

Python

1import numpy as np 2from scipy.spatial.distance import cdist 3 4arr = np.array([[[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]], 5 [[1, 0], [1, 1], [1, 2], [1, 3], [1, 4]], 6 [[2, 0], [2, 1], [2, 2], [2, 3], [2, 4]], 7 [[3, 0], [3, 1], [3, 2], [3, 3], [3, 4]]]) 8target = [2, 3] 9 10# 除外する地点 11ex = set(map(tuple, [[1, 0], [1, 2], [1, 3], [2, 2], [2, 3], [2, 4], [3, 2],[3, 3], [3,4]])) 12 13# まず除外する 14arr = set(map(tuple,arr.reshape(-1,2))) 15arr = arr - ex 16arr = list(arr) 17 18A = np.array(arr) 19B = np.array([target]) 20distances = cdist(A,B,'cityblock') # マンハッタン距離 21min_indices = np.where(distances == distances.min())[0] 22 23ret = A[min_indices].tolist() 24print(ret) # [[2, 1], [0, 3], [1, 4]]

投稿2023/03/20 09:04

can110

総合スコア38311

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

0

ベストアンサー

python

1import numpy as np 2 3arr = np.array([[[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]], 4 [[1, 0], [1, 1], [1, 2], [1, 3], [1, 4]], 5 [[2, 0], [2, 1], [2, 2], [2, 3], [2, 4]], 6 [[3, 0], [3, 1], [3, 2], [3, 3], [3, 4]]]) 7arr = arr.reshape(-1, arr.shape[-1]).tolist() 8 9# 対象となる座標を設定 10target = np.array([2, 3]) 11exclude = [[1, 0], [1, 2], [1, 3], [2, 2], [2, 3], [2, 4], [3, 2],[3, 3], [3,4]] 12 13# マンハッタン距離 14distance = 0 15closest_point = [] 16while not closest_point: 17 distance += 1 18 for x in range(distance+1): 19 y = abs(distance - x) 20 for t in map(list, [target + [x, y], target + [-x, y], target + [x, -y], target + [-x, -y]]): 21 if t in arr and t not in exclude and t not in closest_point: 22 closest_point.append(t) 23 24# 結果を表示 25print(f'{distance = }') 26print(f'{closest_point = }') 27 28# distance = 2 29# closest_point = [[2, 1], [1, 4], [0, 3]]

投稿2023/03/20 06:07

melian

総合スコア19992

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.44%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問