こんな問題があったので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()
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()
コメント