ジュニア算数オリンピック グラフの問題
【随時更新】解答に必要な機能まとめ - ニート歴10年からの数学日記と【随時更新】計算量の減らし方まとめ - ニート歴10年からの数学日記を使って、ジュニア算数オリンピックのグラフの問題について考察していく。今回は最初の問題で実際のpython3も使った。
06年度トライアル問題 問題1
『図の各数字は2つの○の間を移動するとっきの所要時間(単位:分)を示しています。AからBまで移動するときにかかる最も短い時間を求めなさい。
○ | 4 | ○ | 5 | ○ | 8 | B |
6 | 9 | 3 | 7 | |||
○ | 5 | ○ | 4 | ○ | 6 | ○ |
4 | 6 | 5 | 5 | |||
○ | 4 | ○ | 9 | ○ | 6 | ○ |
5 | 8 | 7 | 9 | |||
A | 4 | ○ | 7 | ○ | 8 | ○ |
#[隣接する節点の番号, 移動のコスト] graph = [ [[1, 4], [4, 6]], [[0, 4], [2, 5], [5, 9]], [[1, 5], [3, 8], [6, 3]], [[2, 8], [7, 7]], [[0, 6], [5, 5], [8, 4]], [[1, 9], [4, 5], [6, 4], [9, 6]], [[2, 3], [5, 4], [7, 6], [10, 5]], [[3, 7], [6, 6], [11, 5]], [[4, 4], [9, 4], [12, 5]], [[5, 6], [8, 4], [10, 9], [13, 8]], [[6, 5], [9, 9], [11, 6], [14, 7]], [[7, 5], [10, 6], [15, 9]], [[8, 5], [13, 4]], [[9, 8], [12, 4], [14, 7]], [[10, 7], [13, 7], [15, 8]], [[11, 9], [14, 8]] ] #PQは本当はPriority Queue、つまり優先度キューだったが、今回は実装で怠けるためにリストにしたので、決して実際に使ってはいけない def singleSourceShortest(graph, start, goal): vertex_amount = len(graph) dist = [float("inf")] * vertex_amount #その節点に行くまでのコスト pred = [-1] * vertex_amount #どこから来たか PQ = [] #優先度リスト 探索する際にその時のdist[v]を節点の優先度として使う dist[start] = 0 for v_index in range(vertex_amount): PQ.append((v_index, dist[v_index])) PQ.sort(key=lambda x: x[1], reverse=True) #こう書くらしい(公式ドキュメントの「ソート HOW TO」曰く) while(PQ != []): u_tuple = PQ.pop() u_index = u_tuple[0] u = graph[u_index] for v in u: v_index = v[0] w = v[1] newLen = dist[u_index] + w if newLen < dist[v_index]: dist[v_index] = newLen pred[v_index] = u_index PQ = [i for i in PQ if i[0] != v_index] PQ.append((v_index, dist[v_index])) PQ.sort(key=lambda x: x[1], reverse=True) now_v = goal print("goal") while(pred[now_v] != -1): print("↑") now_v = pred[now_v] print(now_v) singleSourceShortest(graph, 12, 3)
$ python3 ダイクストラ.py goal ↑ 2 ↑ 6 ↑ 5 ↑ 4 ↑ 8 ↑ 12
12年度トライアル問題 問題8
『次の立体を頂点Aからスタートして返上を通ってAにもどってくるような方法は、全部で何通りありますか。ただし、同じ辺を2度通ってはいけません。
(図は省略 ABCDの三角錐)』
#pythonでは無い graph := [ "A" : ["B", "C", "D"], "B" : ["A", "C", "D"], "C" : ["A", "B", "D"], "D" : ["A", "B", "C"] ]; #辞書、()にするか[]にするか迷うな def visit_v(graph, current_v, start) { or(next_v in graph[current_v]) { #orにおいて、データを共有するかどうかという設定項目が必要か graph[current_v].remove(next_v); graph[next_v].remove(current_v); current_v := next_v; if(current_v != start) { # || graph[current_v] != [] を入れるべきか current_v := visit_v(graph, current_v, start); } } return current_v; } start := "A"; current_v := "A"; current_v := visit_v(graph, current_v, start); current_v == "A"; print(数);
こんな感じだろうか。
return文が必要だと気付いて付け足した。これで大丈夫かな。しかしやっぱりpythonは良かったなあ。