関連するソリューション
システム開発
エバンジェリスト・フェロー
玉越 元啓
しかし、これらの例題は日常生活ではあまり馴染みがないかもしれません。そこで、オリンピックで目にしたボルダリング(スポーツクライミング)をテーマにして、最短経路問題を解くコードを書いて解説していきます。
最短経路問題とは
最短経路問題の概要
最短経路問題は、グラフ理論における基本的な問題の一つです。グラフは、頂点(ノード)とそれらを結ぶ辺(エッジ)で構成されます。最短経路問題では、ある始点から終点までの経路の中で、総コスト(距離や時間など)が最も小さい経路を見つけることを目的とします。よくある最短経路の例
最短経路問題は、現実世界のさまざまな場面で応用されています。例えば、以下のような例があります。- サラリーマンの営業経路
複数の顧客を訪問する際に、移動距離や時間を最小限に抑えるための最適なルートを見つける。 - 交通ネットワーク
都市内の最短ルートを見つけるために、道路や鉄道のネットワークを解析する。 - インターネットルーティング
データパケットが最短時間で目的地に到達するための経路を決定する。
ボルダリングと最短経路問題
ボルダリングとは
ボルダリングは、スポーツクライミングの一種で、ロープを使わずに比較的低い壁を登る競技です。課題(プロブレム)と呼ばれる特定のルートを登り切ることが目標で、技術やバランス、パワーが求められます。初心者から上級者まで楽しめるスポーツでもあり、屋内施設も多く、天候に左右されずに楽しめるのが魅力です。また、体全体を使うため、フィットネス効果も高いそうです。(【パリ五輪】スポーツクライミングの競技ルールを解説: https://www.climbers-web.jp/whats_climbing/whats_climbing_10/)
パリオリンピックでは、ボルダリングとリードクライミングが複合種目として実施され、日本の安楽宙斗選手がボルダー&リード複合で銀メダルを獲得しました(パリ五輪、ボルダー&リード安楽宙斗銀メダル:https://www.climbing-net.com/news/paris2024_sportclimbing_20240810/)。
ボルダリングと最短経路問題
今回は、より身近で興味を引くテーマとして、ボルダリング(スポーツクライミング)を使って最短経路問題を解く方法を紹介します。ボルダリングでは、壁に設定された課題(ルート)をいかに効率よく登るかが重要です。この課題を最短経路問題として捉え、アルゴリズムを用いて解決することで、より直感的に理解できるでしょう。
実装
実行結果のイメージ
まずは、壁のイメージです。(壁のイメージの作成と最短経路を壁のイメージに合成するところは、紙面の都合で今回は含めておりません。)最短経路を壁にプロットしてみたところです。最短経路を求めている様子です。こちらが今回解説する範囲になります。
アルゴリズムについて
経路探索問題の手法の一つである、ダイクストラ法をベースにボルダリング用にアレンジしています。ダイクストラ法は、グラフ理論におけるアルゴリズムの一つで、特定の始点から他のすべての頂点への最短経路を求めるために使用されます。このアルゴリズムは、エドガー・ダイクストラによって1959年に考案されました。(参考:https://ja.wikipedia.org/wiki/%E3%83%80%E3%82%A4%E3%82%AF%E3%82%B9%E3%83%88%E3%83%A9%E6%B3%95)
ダイクストラ法は下の4つのステップで構成されています。「点/ホールド」の代わりに、グラフ理論の表現「ノード」と使っています。
1、初期化
始点から各ノードへの最短距離を無限大に設定し、始点の距離を0に設定する。
2、ヒープキューの使用
- 始点をキューに追加し、キューが空になるまで以下を繰り返す。
- キューから最短距離のノードを取り出す。
- 隣接する各ノードについて、現在の距離と新しい経路を通った場合の距離を比較し、短い方を選ぶ。
- 更新があった場合、その隣接ノードをキューに追加する。
キューが空になったとき、全てのノードへの最短経路が確定します。
ボルダリングにむけた工夫
壁にある持ち手(ホールドと呼ぶそうです。以下、点を表現しています)の情報からグラフを作成する必要があります。点から点への距離を求めて、グラフをつくることになります。実際には、全ての点(ホールドと呼ぶそうです)から全ての点に移動できるわけではありません。点から点の距離を測り、手が届く範囲の点を移動できる対象(隣接するノード)として抽出することとしました。
また、全ノードへの最短経路を求める必要はないため、ゴールへの最短経路が判明した時点で終了することとしました。この判定方法は、コードの解説にて後述しています。
コードのポイント解説
グラフの作成
ホールドの関係性をグラフにする処理です。ホールド間の距離を単純に出すのではなく、手が届かない距離にあるホールドへの距離を無限大とすることで経路として選ばれないようにしています。
def create_weighted_graph(points):
"""
各ホールドをノードとする重み付きグラフを作成する。
重みは二点間のユークリッド距離とする。
"""
graph = {}
for p1 in points:
graph[p1] = {}
for p2 in points:
if p1 != p2:
weight = distance(p1, p2)
if weight > MAX_DISTANCE:
graph[p1][p2] = float('inf')
else:
graph[p1][p2] = weight
return graph
経路探索処理
# 優先キューをセット(距離, 現在拠点)
queue = [(0, start)]
# キューが存在する間ループ
while queue:
dist, current_point = heapq.heappop(queue)
if current_point == goal:
# 取り出した最小距離の拠点がゴール=ゴールまでの経路を探索済
# Reconstruct the path
path = []
path = get_path(current_point,predecessors)
return path[::-1]
# 現在の拠点から次の拠点を探索
for neighbor in graph[current_point]:
# 次の拠点への移動距離を計算
new_dist = dist + graph[current_point][neighbor]
if new_dist < distances[neighbor]:
# 移動距離が短くなった場合
# その拠点までの距離、前拠点を更新
distances[neighbor] = new_dist
predecessors[neighbor] = current_point
# キューに追加
heapq.heappush(queue, (new_dist, neighbor))
showlog((new_dist, neighbor))
最初に、開始位置をヒープキューの初期値として登録します。この後は、キューに登録されている点が存在する間、次の処理を繰り返します。
- ヒープキューから点を取り出す(取り出した点の情報はキューから消えます)
- 取り出した点がゴールなら終了
- 取り出した点がゴール以外なら、現在いる点から移動可能な点までの総移動距離を計算します。
- 3.の距離が、既に求められていたその点までの総移動距離より短い場合(最短経路を更新した場合)、その点までの総移動距離と移動元の点の情報を更新して、その点をキューに追加します。
1.~4.の繰り返しにより、ゴールまでの移動距離が更新されつづけます。
最終的にヒープキューにはゴールに到達した他経路の情報や現在判明しているゴールまで経路よりも移動距離が長い点の情報だけが残り、②で取り出されるゴールの情報が最短経路となります。
ヒープキュー
キューには3種類あります。主な特徴をまとめました。データ構造 | 動作 | 主な用途 |
---|---|---|
スタック | 後入れ先出し (LIFO: Last In, First Out) 要素は後ろから追加・削除 |
関数呼び出しの管理、再帰処理 ブラウザの戻るボタン 条件付き経路探索、パズルの解法アルゴリズム、シミュレーションゲーム等の移動範囲探索など |
キュー | 先入れ先出し (FIFO: First In, First Out) 要素は後ろから追加、先頭から削除 |
タスクの順序管理、プロセスのスケジューリング プリンターの印刷ジョブ、幅優先探索 |
ヒープキュー (優先度キュー) |
優先度に基づく 要素は任意の順序で追加、優先度の高い要素が先に削除 |
タスクの優先順位付け、最短経路探索 ヒープソート、優先度付きタスク管理 |
今回は、ヒープキューを採用しています。
キューの要素として(開始点からの移動距離,点の座標(x,y))を追加しています。
queue = [(0, start)]
dist, current_point = heapq.heappop(queue)
キューから取り出す際は、要素のうち最も移動距離が近い点を取得でき、結果、キューから削除されます。
このとき取り出した点がゴールであったとき、その経路が最短移動距離となります。キューにはまだ要素が残っている場合もありますが、残っているキューは、より移動距離が遠い点の集合になるため、ゴールへの最短経路にはなりえません。全経路の探索ではなく、不要な経路の探索を行わないようにしてため、比較的高速に最短経路を求めることが出来ます。
今回のアルゴリズムを使えば、迷路を入口から出口までの最短経路を求めることもできます。色々と試してみてください。
今後の発展
今後の発展として、ホールドの検出とルート探索のバリエーションを増やすこと、が考えられます。実際のボルダリングの壁画像からホールドの検出には、物体検知やセグメンテーションのAIを活用すれば出来そうです。ホールド一つ一つを検出出来れば、持ちやすい/持ちにくいなどのホールド毎の特徴などを捉えることも可能になります。
ルート探索のバリエーションとしては、最短ルートのほかにも条件・制約を付加したルート探索が必要になりそうです。足場がある、体勢を維持しやすい、どの程度体力を消耗しそうか、など。難易度が低いルートの探索が出来れば、初心者向けにルートを推奨するアプリもつくれそうです。
実際のビジネスの技術的な課題について考えるときも、単純なモデル化した実験(今回のスタートからゴールまでの最短経路探索)をとおして、出来ることや発展させる方向性を具体的に検討することが出来るようになります。
まずは、課題の難易度を図る小さな実験から始めてみてはいかがでしょうか。
コードの全文
※ボルダリングの壁をランダムに生成している部分については、壁のサイズ、点の数、手が届く距離をパラメータとして与え、様々な条件で実験できるようにしています。python プログラムファイル名 -h
で、指定できパラメータが表示されます。
実行結果は、高さ480、幅480、点の数40、移動できる範囲80として生成したものです。
import random
import math
import heapq
import cv2
import numpy as np
import argparse
from datetime import datetime
DEBUG_MODE = False
def showlog(message):
if DEBUG_MODE:
print(message)
return
def distance(p1, p2):
"""
二点間のユークリッド距離を計算
"""
return math.sqrt((p1[0] - p2[0])**2 + (p1[1] - p2[1])**2)
def get_args():
parser = argparse.ArgumentParser(description='説明')
parser.add_argument('-m', '--MODE', type=str, default='False', help="Trueなら、デバッグログ表示をする(default='False')")
parser.add_argument('-p', '--point', type=int, default=50, help="ホールドの数。(default=50)")
parser.add_argument('-w', '--width', type=int, default=480, help="フィールドの横幅(default=480)")
parser.add_argument('-hi', --height', type=int, default=1600, help="フィールドの高さ(default=1600)")
parser.add_argument('-d', '--distance', type=int, default=200, help="移動できる拠点間の距離(default=100)")
args = parser.parse_args()
return args
def create_weighted_graph(points):
"""
各ホールドをノードとする重み付きグラフを作成する。
重みは二点間のユークリッド距離とする。
"""
graph = {}
for p1 in points:
graph[p1] = {}
for p2 in points:
if p1 != p2:
weight = distance(p1, p2)
if weight > MAX_DISTANCE:
graph[p1][p2] = float('inf')
else:
graph[p1][p2] = weight
return graph
def get_path(current_point, predecessors):
path = []
while current_point:
showlog(current_point)
path.append(current_point)
# ひとつ前に戻る
current_point = predecessors[current_point]
return path
def find_shortest_path(start, goal, points):
# 二点間の重み付きグラフの作成
# Create a weighted graph
graph = create_weighted_graph(points)
showlog(graph)
# 初期化
# ホールドの位置とスタートからホールドまでの最短移動距離、最短移動距離時の直前のホールドを記録する辞書を作成、初期化する
# ヒープキューを使うため、距離→
distances = {point: float('inf') for point in points}
distances[start] = 0
predecessors = {point: None for point in points}
# 優先キューをセット(距離, 現在拠点)
queue = [(0, start)]
# キューが存在する間ループ
while queue:
dist, current_point = heapq.heappop(queue)
if current_point == goal:
# 取り出した最小距離の拠点がゴール=ゴールまでの経路を探索済
# Reconstruct the path
path = []
path = get_path(current_point,predecessors)
return path[::-1]
# 現在の拠点から次の拠点を探索
for neighbor in graph[current_point]:
# 次の拠点への移動距離を計算
new_dist = dist + graph[current_point][neighbor]
if new_dist < distances[neighbor]:
# 移動距離が短くなった場合
# その拠点までの距離、前拠点を更新
distances[neighbor] = new_dist
predecessors[neighbor] = current_point
# キューに追加
heapq.heappush(queue, (new_dist, neighbor))
showlog((new_dist, neighbor))
if DEBUG_MODE:
currentpath = []
currentpath = get_path(current_point,predecessors)
show_path_image(points,currentpath,start,goal)
cv2.waitKey(100)
return None # No path found
def show_path_image(points, paths, start, goal, display_time=100):
canvas = np.full((HEIGHT, WIDTH , 3), 255, dtype=np.uint8)
for point in points:
cv2.circle(canvas, point, 4, (255, 0, 0), -1)
# 現時点での最短パスを描画
for i in range(len(paths) - 1):
cv2.line(canvas, paths[i], paths[i + 1], (0, 0, 255), 2)
cv2.circle(canvas, goal, 4, (255, 255, 0), -1)
cv2.circle(canvas, start, 4, (255, 255, 0), -1)
# Display the canvas
cv2.imshow("shorestest Path", canvas)
cv2.waitKey(display_time)
if DEBUG_MODE:
timestamp = datetime.now().strftime("%Y%m%d_%H%M%S%f")
filename = "path_" + timestamp + ".png"
cv2.imwrite(filename,canvas)
return
if __name__=="__main__":
# パラメータの処理
args = get_args()
WIDTH = args.width
HEIGHT = args.height
point_count = args.point
MAX_DISTANCE = args.distance
if args.MODE.upper()=='TRUE':
DEBUG_MODE = True
showlog(args)
# ランダムに点を配置
# 最上部から20p,最下部から20pの間には配置しない
padding_top = 20
padding_bottom = 40
padding_left = 10
padding_right = 10
padding = (padding_top,padding_bottom,padding_left,padding_right)
points = [(random.randint(padding_left, WIDTH - padding_right), \
random.randint(padding_bottom, HEIGHT - padding_top)) \
for _ in range(point_count)]
# スタート、ゴールを配置
w_center = int(WIDTH//2)
h_start = HEIGHT - padding_bottom
h_goal = padding_top
start = (w_center,h_start)
goal = (w_center,h_goal)
points.append(start)
points.append(goal)
print(f"start:{start}")
print(f"goal:{goal}")
print("■ 最短経路の探索")
shortest_path = find_shortest_path(start, goal, points)
# 結果を表示
print("スタート位置:", start)
print("ゴール位置:", goal)
print("最短経路:", shortest_path)
#time.sleep(1)
if shortest_path is None:
print("経路なし")
else:
print(len(shortest_path))
show_path_image(points, shortest_path, start, goal,0)
print("Fin.")
当サイトの内容、テキスト、画像等の転載・転記・使用する場合は問い合わせよりご連絡下さい。
エンジニアによるコラムやIDグループからのお知らせなどを
メルマガでお届けしています。