この記事はSupershipグループ Advent Calendar 2022の11日目の記事です。
はじめに
約1年ぶりの投稿になります。@nao_omotoです。昨年のアドベントカレンダーでは、組合わせ最適化問題を「解く」というテーマで記事を書きましたので（とある会社の組織再編を数理モデリングで解決する話）、今年は組合わせ最適化問題を「可視化する」ということにチャレンジしてみました。温かい目で見ていただけたら幸いです。
構成は次の通りです。
1. 組合せ最適化問題について
2. Streamlitについて
3. 可視化①（レーベンシュタイン距離）
4. 可視化②（最短経路）
1. 組合せ最適化問題について
復習も兼ねて、簡単にまとめてみます。
組合せ最適化問題とは、数理最適化問題のうち解集合が組合せ的な構造（集合、順序、グラフなど）を持つ最適化問題のことです。原理的には、すべての組合せ最適化問題は整数計画問題に定式化することができ、以下の標準形と呼ばれる形で表すことができます。
maximize \ \ \ \sum_j c_j x_j \\
s.t. \ \ \ \sum_j a_{ij}x_j \leq b_i, \\
\ \ \ x_j \in \mathbb{Z}_{+}
一般的に、整数計画問題（組合せ最適化問題）はNP困難であるため、変数の数や領域が大きくなると厳密解を求めることが難しくなります。と、ここまでは去年の記事にも書きましたが、一方で、効率的に解ける問題とアルゴリズムもいくつかあることが知られています。
- 貪欲法
- 最短経路問題、最小全域木問題、...
- 動的計画法
- ナップサック問題、レーベンシュタイン距離（編集距離）、...
- ネットワークフロー
- 最大フロー・最小カット問題、最大マッチング問題、...
上記の問題は競プロの文脈でもよく取り上げられるので、数理最適化に馴染みがなくても知っている方は多いと思います。
さて、この記事では、これらの問題（アルゴリズム）の中から 「レーベンシュタイン距離」と「最短経路問題」を解く簡易アプリ を作成してみたので紹介します。
2. Streamlitについて
簡易アプリを作成するためのツールとして、今回はStreamlitを採用しました。StreamlitはPythonでWebアプリを作成するためのフレームワークです。手軽に開発できるのが特徴で、パラメータを動的に動かしてしてデータを可視化するなど、特にデータサイエンス領域で用いられることが多いです。個人的には、ここ1, 2年の間でよく見かけるようになった印象があります。
使い方は、インストールした後に、
pip install streamlit
作成したコード（例えば、app.py）を下記コマンドで実行するだけです。
streamlit run app.py
3. 可視化①（レーベンシュタイン距離）
レーベンシュタイン距離（編集距離）は、二つの文字列がどれだけ似ているかをを示す距離の一種です。具体的には、1文字の挿入・削除・置換をそれぞれ一つの操作とすると、二つの文字列を一致させるのに必要な操作の最小回数が距離と定義されます。
作成したアプリは、二つの文字列を入力するとレーベンシュタイン距離を返すというものです（図1, 図2）。
簡単に、コードの紹介をします。
[1/4] 最初にタイトルとキャプションを書きます。streamlitのライブラリをimportして、引数を与えているだけです。他にもいろいろなウィジェットがありますが、ここではシンプルに2つだけ採用しました。
import streamlit as st
# title
st.title("Levenshtein distance")
st.caption("2つの文字列の 編集距離を計算します")
[2/4] 次に、Web画面で入力した文字列を受け取ります。変数btnはbool値で、Web画面上の「Calc」ボタンを押すとTrueが入ります。
# input
S = st.text_input("String S")
T = st.text_input("String T")
btn = st.form_submit_button("Calc")
[3/4] そして、受け取った二つの文字列のレーベンシュタイン距離を計算します。 レーベンシュタイン距離は動的計画法によって効率的に求めることができます。下記の通り、dpテーブルを定義し、挿入・削除・置換に基づいてdpテーブルを更新していきます。計算量は$ \mathcal{O}(\mathrm{|S||T|})$です。
# calc Levenshtein distance
N, M = len(S), len(T)
INF = 10**10
dp = [[INF] * (M+1) for _ in range(N+1)]
for i in range(N+1): dp[i][0] = i
for j in range(M+1): dp[0][j] = j
for i in range(1, N+1):
for j in range(1, M+1):
if S[i-1] == T[j-1]:
dp[i][j] = min(dp[i][j-1]+1,
dp[i-1][j]+1,
dp[i-1][j-1])
else:
dp[i][j] = min(dp[i][j-1]+1,
dp[i-1][j]+1,
dp[i-1][j-1]+1)
[4/4] 最後に、上で計算したレーベンシュタイン距離を出力します。if btn:とすることで、Web画面で「Calc」ボタンを押すと結果が表示される仕組みになっています。
if btn: st.text(f"{S} と {T} の編集距離は {dp[N][M]} です")
この程度のアプリなら、アルゴリズム部分を除いて10行程度で実装できました。とても簡単です。
（ちなみに、コードの完全版では一部コードがwith句の中に入っています。これは文字列の入力画面でカーソルを離すたびにリロードされてしまうのを防ぐためです。）
コードの完全版（レーベンシュタイン距離）
import streamlit as st # type: ignore
# title
st.title("Levenshtein distance")
st.caption("2つの文字列の編集距離を計算します")
# form
with st.form(key="from"):
# input
S = st.text_input("String S")
T = st.text_input("String T")
btn = st.form_submit_button("Calc")
# calc Levenshtein distance
N, M = len(S), len(T)
INF = 10**10
dp = [[INF] * (M+1) for _ in range(N+1)]
for i in range(N+1): dp[i][0] = i
for j in range(M+1): dp[0][j] = j
for i in range(1, N+1):
for j in range(1, M+1):
if S[i-1] == T[j-1]:
dp[i][j] = min(dp[i][j-1]+1,
dp[i-1][j]+1,
dp[i-1][j-1])
else:
dp[i][j] = min(dp[i][j-1]+1,
dp[i-1][j]+1,
dp[i-1][j-1]+1)
# show results
if btn: st.text(f"{S} と {T} の編集距離は {dp[N][M]} です")
4. 可視化②（最短経路）
もうひとつ、グラフの最短経路を可視化するアプリを作成してみました。グラフはAからZの頂点と、重みつきの辺（全て非負）を描画しています。サイドバーのプルダウンからStartとEndの頂点を指定して「Run」ボタンを押すと、指定した頂点間の最短経路を探して、オレンジ色で可視化します。また、その最短経路の重みの総和もサイドバーに表示します（図3, 図4）。なお、最短経路はダイクストラ法を用いて計算しています。
図3: AからYの最短経路を可視化した結果。重みの総和（距離）は240。直感的にも正しそう。
図4: AからBの最短経路を可視化した結果。重みの総和（距離）は430。パッと目につくA$\rightarrow$W$\rightarrow$X$\rightarrow$Bの距離は450なので、実は最短経路ではない。
こちらのアプリはコードが長くなってしまったので、いくつかポイントをピックアップしてご紹介します。（詳細はコードの完全版をご覧ください。この章の一番下に貼ってます。）
[1/3] さきほどのアプリと大きく異なる点は、with st.sidebar:でサイドバーを表示したところです。また、st.selectboxでWeb画面にセレクトボックスを表示させ、選択した頂点を変数s, tに格納しています。
# sider bar
with st.form(key="node"):
with st.sidebar:
s = st.selectbox("Start", nodes)
t = st.selectbox("End", nodes)
btn = st.form_submit_button("Run")
[2/3] グラフは、networkxを用いて描画しています。Networkオブジェクト(nt)を生成し、頂点や辺の情報を追加していきます。（詳細はコード完全版を参照いただければと。）
import networkx as nx
# generate network
nt = Network("700px", "800px", heading='')
[3/3] ダイクストラ法については自前で実装しています。ポイントはprevで直前に訪れた頂点を管理し、復元した最短経路をrouteに格納しているところでしょうか。頂点をheapqで管理しているので、計算量は$\mathcal{O} \mathrm{((E + V)logV)}$です（ただし、$\mathrm{E}$は辺の数、$\mathrm{V}$は頂点数）。
# Dijkstra
from heapq import heappop, heappush
s_ = ord(s) - ord("A")
t_ = ord(t) - ord("A")
INF = 10**10
dist = [INF for _ in range(num)]
dist[s_] = 0
visited = [False] * num
prev = [-1] * num
que = []
heappush(que, (dist[s_], s_))
while que:
w, now = heappop(que)
if visited[now]: continue
visited[now] = True
for c, to in edges[now]:
if visited[to]: continue
if dist[to] > dist[now] + c:
dist[to] = dist[now] + c
prev[to] = now
heappush(que, (dist[to],to))
route = []
now = t_
while now != -1:
last = prev[now]
if last == -1: break
route.append((now, last))
now = last
だいぶコードの紹介を端折ってますので、完全版を下記に残しておきます。グラフを描画する部分が冗長になっていますが、こちらのアプリもアルゴリズムや、グラフの描画部分を除くと10行程度で作成できました。
コードの完全版（最短経路の可視化）
import streamlit as st # type: ignore
import networkx as nx # type: ignore
from pyvis.network import Network # type: ignore
import streamlit.components.v1 as components # type: ignore
### graph info
num = 26
g = [[(i+1)%num, (i+4)%num] if i%7!=0 else [] for i in range(num)]
weight = [[0] * num for _ in range(num)]
for now in range(num):
for to in g[now]:
weight[now][to] += 10 * abs(now - to)
weight[to][now] += 10 * abs(now - to)
edges = [[] for _ in range(num)]
for i in range(num):
for j in g[i]:
w = weight[i][j]
edges[i].append((w, j))
edges[j].append((w, i))
nodes = [chr(i + ord("A")) for i in range(num)]
pos = [[i+1, i+1] for i in range(num)]
### main body
# title
st.title("Dijkstra")
# sider bar
with st.form(key="node"):
with st.sidebar:
s = st.selectbox("Start", nodes)
t = st.selectbox("End", nodes)
btn = st.form_submit_button("Run")
# Dijkstra
from heapq import heappop, heappush
s_ = ord(s) - ord("A")
t_ = ord(t) - ord("A")
INF = 10**10
dist = [INF for _ in range(num)]
dist[s_] = 0
visited = [False] * num
prev = [-1] * num
que = []
heappush(que, (dist[s_], s_))
while que:
w, now = heappop(que)
if visited[now]: continue
visited[now] = True
for c, to in edges[now]:
if visited[to]: continue
if dist[to] > dist[now] + c:
dist[to] = dist[now] + c
prev[to] = now
heappush(que, (dist[to],to))
route = []
now = t_
while now != -1:
last = prev[now]
if last == -1: break
route.append((now, last))
now = last
# generate network
nt = Network("700px", "800px", heading='')
# add nodes
for i in range(num):
posx = pos[i][0]
posy = pos[i][1]
col = "orange" if s == nodes[i] or t == nodes[i] else None
nt.add_node(i, label=nodes[i], x=posx, y=posy, color=col)
# add edges
for now in range(num):
for to in g[now]:
if (now, to) in route or (to, now) in route: col, wid=("orange", 5)
else: col, wid=("green", 1)
nt.add_edge(now, to,
color=col, width=wid, label=str(weight[now][to]))
# show graph
nt.show("dijkstra.html")
html_file = open("dijkstra.html", "r", encoding="utf-8")
components.html(html_file.read(), height=700, width=802)
with st.sidebar:
st.text(f" {s} から {t} までの距離は {dist[t_]} です")
おわりに
ここまでお読みいただき、ありがとうございます！
今年を振り返ってみると、数理最適化というより競プロに力を入れていた年でした。来年は緑色$\rightarrow$水色（※Atcoderの話です）になれるように頑張ります！
参考文献
この記事は主に下記の書籍等を参考にして作成しました。
- 梅谷俊治『しっかり学ぶ数理最適化 -モデルからアルゴリズムまで-』講談社（2020）
- 米田優峻『競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~』マイナビ出版（2022）
- ときかねえさん 乗換案内をPythonで作ろう！最短経路探索アルゴリズムのUI実装
- VTuber サプー 【超簡単Webアプリ】streamlitでWebアプリを最速で作ってネット公開！〜 プログラミング初心者向け 〜
最後に宣伝
Supershipではプロダクト開発やサービス開発に関わる人を絶賛募集しております。
ご興味がある方はSupershipグループ 採用サイトをご確認ください。よろしくお願いします。