Pythonで最短経路を求める方法

Pocket

こんな問題があったのでPythonで解いてみました。

xとyという2つのリストが与えられている。
5つの点の座標はそれぞれxのn番目yのn番目になっている。
開始時の点をリストx,yの0番目の座標として、どの点を順番に通るのが最短なのかをリストに格納して出力せよ。

5点であれば全ての順列を計算しても大したことはないでしょう。

import itertools

def main():
  x = [50, 45, 75, 80, 20]
  y = [45, 15, 85, 75, 25]

  ps = itertools.permutations(range(len(x)))
  min_length = 1000000
  for p in ps:
    l = calc_length(x, y, p)
    if l < min_length:
      min_length = l
      min_p = p
  result = []
  for i in min_p:
    result.append([x[i], y[i]])
  print(result)

def calc_length(x, y, p):
  l = 0
  for n in range(0, len(p) - 1):
    i0 = p[n]
    i1 = p[n + 1]
    l += ((x[i0] - x[i1]) ** 2 + (y[i0] - y[i1]) ** 2) ** (1 / 2)
  return l

if __name__ == "__main__":
  main()

[ 2024年1月27日 | カテゴリー: Python | タグ: ]

« | »

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

送信してください。


タグ

カテゴリー

最近の投稿

最近のコメント

固定ページ

アーカイブ

stabucky

写真

メタ情報