paizaのキャンペーン問題やってみた。(巡回セールスマン問題)

  • 6
    Like
  • 2
    Comment

肉かamazonギフト券が抽選でもらえるらしいので、今回はpython3でやってみました。
https://paiza.jp/poh/phantom_thief

問題概要

N個のお宝のx, y座標が与えられる。
各座標間は直線で移動。
0, 0の位置からスタートする。
可能な限り短いルートで各お宝をゲットするルートを出力する。
必ず最短距離である必要ない。

入力される値
N (N はお宝の総数)
x_1 y_1 (x_1 は 1 個目のお宝の場所の x 座標、 y_1 は 1 個目のお宝の場所の y 座標)
x_1 y_1 (x_2 は 2 個目のお宝の場所の x 座標、 y_2 は 2 個目のお宝の場所の y 座標)
・・・ 
x_N y_N (x_N は N 個目のお宝の場所の x 座標、 y_N は N 個目のお宝の場所の y 座標)

・全ての値は整数 
・1 ≦ N ≦ 100 
・1 ≦ x_i, y_i ≦ 1000000 (1 ≦ i ≦ N) 

期待する出力
お宝を全てゲットできるルートを出力して下さい。 
最後は改行し、余計な文字、空行を含んではいけません。 

例
入力例1
3
90 100
40 15
30 30

出力例1
90 100
40 15
30 30

入力例2
5
1 1
40 120
199 256
10 30
50 5

出力例2
1 1
40 120
199 256
10 30
50 5

自分が書いたコード。

import math

def cal_distance(current_point, point):
    """ 2点間の距離を求める """
    x1 = current_point[0]
    y1 = current_point[1]
    x2 = point[0]
    y2 = point[1]
    distance = math.sqrt((x2 - x1) ** 2 + (y2 - y1) ** 2)
    return distance

def make_distance_list(current_point, position_list):
    """ 2点間の距離のリスト作成 """
    distance_list = [(i, cal_distance(current_point, x)) for (i, x) in enumerate(position_list)]
    return distance_list

# 入力値取得
list_len = int(input())
position_list = []
for i in range(list_len):
    position_list.append(list(map(int,input().split())))

# 現在の位置から近い位置に移動していく
current_point = [0, 0]
while len(position_list) > 0:
    distance_list = make_distance_list(current_point, position_list)
    sorted_distance_list = [x[0] for x in sorted(distance_list, key=lambda d: d[1])]
    print('{0} {1}'.format(position_list[sorted_distance_list[0]][0],
                             position_list[sorted_distance_list[0]][1]))
    current_point = position_list.pop(sorted_distance_list[0])

実行結果(ちょっと入力と出力の境目がわかりずらい)

$ python PaizaRouteSearch.py
5
1 2
4 2
10 40
3 2
1 1
1 1
1 2
3 2
4 2
10 40

現在位置から一番近いお宝へ順に辿っていけばいいかなぁと安直な考えで書きました。
聞いた話によると「巡回セールスマン問題」というアルゴリズムで解くのが最短ルートらしいです。

時間があるときに調べて見直したいです。

 
追記:
paizaのブログで問題解説の記事が上がっていました。
http://paiza.hatenablog.com/entry/2017/09/26/【問題解説】怪盗813からの謎を解いて、お宝ゲットする方法

自分の解法は貪欲法というらしく、paizaのブログでも同じ解法を紹介していました。
その他にも「焼きなまし法」、「ビームサーチ」、「2-opt」、「遺伝的アルゴリズム」、
「クリストフィードのアルゴリズム」、「全域木」、「粘菌アルゴリズム」・・といろいろあるみたいです。
Wikipediaをみると数式が・・。学生以来数学から離れているので頭痛い。

プレゼントについては
もう当選者への発送が始まっているようで、自分には特に連絡がないので外れたみたいです。残念。

ちなみに、以下は間違いでした。問題があってその解法としてアルゴリズムがいくつかあるようで。
> 聞いた話によると「巡回セールスマン問題」というアルゴリズムで解くのが最短ルートらしいです。

追記2:
プレゼントについて
1か月半ほど経って忘れたころにAmazonギフト券(1000円分)が届きました!
期待してなかっただけにうれしい!
意外と当たるみたいなので、次回もまた参加したいと思います!