Rustで動的計画法の実装：Longest Path
はじめに
動的計画法を実装してみて、Rustの勉強をやってみる。問題としてはEducational DP Contestという動的計画法の練習を目的としたコンテストのものを使用。
AからZまで問題が設定されているが、今回はGのLongest Path、閉路を含まない有向グラフにおける最大パス長を求める問題。最短経路だとDijkstra法とか思い浮かべるが、最長のパスだとそんなに難しくはない。
利用したライブラリ
標準入力からデータを読み取る部分はproconioを利用。入力のノード番号が1オリジン(1-indexed)なので、0オリジン(0-indexed)に変更するためにmarker::Usize1も使う。これは、1減らした値を入れてくれるmarker。
完成したコード
閉路（ループ）がない有向グラフなので、各ノード毎に入ってくるリンクの数をカウントし、カウント数が0のノードから出るリンクを削除していく。そんなに難しくはないが、ソースだけ見ると何をしているのか直感的ではないので、説明する。
use proconio::input;
use proconio::marker::Usize1;
fn main(){
input!(
n: usize, m: usize,
links: [(Usize1, Usize1); m]
);
let mut count_incomming: Vec<usize> = vec![0; n];
for (_src, dst) in links.iter() {
count_incomming[*dst] += 1;
}
let mut src_nodes = Vec::with_capacity(n);
let mut remain_nodes = n;
for (i, count) in count_incomming.iter().enumerate() {
if *count == 0 {
src_nodes.push(i);
remain_nodes -= 1;
}
}
let mut path_length = 1;
loop {
let mut nodes = Vec::with_capacity(n);
for (src, dst) in links.iter() {
if src_nodes.iter().any(|e| *e == *src) {
count_incomming[*dst] -= 1;
if count_incomming[*dst] == 0 {
nodes.push(*dst);
remain_nodes -= 1;
}
}
}
if remain_nodes == 0 {
break;
}
path_length += 1;
src_nodes = nodes;
}
println!("{}", path_length);
}
入ってくるリンクの数をカウントする
リンクの宛先dstの数をノード毎にカウントして結果をcount_incommingに入れる。Rustでは、最近の賢いコンパイラと同様、使わない変数に関してwarningがでてくるが、アンダーバーで始めていればwarningはでてこない。
for (_src, dst) in links.iter() {
count_incomming[*dst] += 1;
}
初期化
incommingなリンクが1つもないノード。つまり始点となるノードをsrc_nodesに入れていく。このノードに到着する最大のパス長は0となるので、ここを起点とする。remain_nodesは。まだ「このノードを終点とした時の最大パス長が決まっていないノードの数」なので、src_nodesに入れる度に減算する。
let mut src_nodes = Vec::with_capacity(n);
let mut remain_nodes = n;
for (i, count) in count_incomming.iter().enumerate() {
if *count == 0 {
src_nodes.push(i);
remain_nodes -= 1;
}
}
パス長の導出
src_nodesを起点とするリンクを消していく。具体的にはdstに指定されているcount_incommingを1つ削除する。count_incommingが0になった場合は、それ以上入ってくるリンクが無いという事なので、「このノードを終点とした時の最大パス長」はpath_lengthで決定したということになる。最大パス長が決定したノードを新しいsrc_nodesとして、remain_nodesが無くなるまで繰り返す。
ソースコードではリンクlinksの起点がsrc_nodesに入っているかどうかでループをかけている。「src_nodesを起点とするリンク」は複数あるので、src_nodesのループから始めると二重ループとなるので見通しが悪くなると思う。iter().any()は線形探索だと思うので、結局は二重ループではあるのだけど。
上の説明では「リンクを消していく」とあるが、リンクの配列linksから要素の削除は行なっていない。今回の問題では閉路（ループ）が存在しないので、src_nodesに同じノードが複数入ることはなくこれで問題ない。閉路がある場合はリンクを削除しないとループが発生して止まらない。ただし、イテレータとして回しているループの中で要素を削除することは実は難しい。drain_filterを使えば素直に実装できそうな気はするが、nightly-only experimental API らしいので正式に採用されたら使ってみたい。
let mut path_length = 1;
loop {
let mut nodes = Vec::with_capacity(n);
for (src, dst) in links.iter() {
if src_nodes.iter().any(|e| *e == *src) {
count_incomming[*dst] -= 1;
if count_incomming[*dst] == 0 {
nodes.push(*dst);
remain_nodes -= 1;
}
}
}
if remain_nodes == 0 {
break;
}
path_length += 1;
start_nodes = nodes;
}
Dijkstraっぽく解いてみる
動的計画法を解くだけだとクラスっぽい仕組みを使わない気がするので、Dijkstra法っぽく実装してみた。Node間でメッセージを送って各ノードが自律的に動作するイメージで実装。多分効率は悪い。
閉路（ループ）については検知機能をつけて止まるようにはしておいた。
エラーの返し方
Rustの定型文みたいなもので、すぐにでてくるかな？と思っていたら、動的計画法の実装ではなかなかでてこなかったもの。関数のエラーをどのように返すか？という課題で、C++やJavaだと例外を返すし、Goだとtupleを返す事が多い。RustではOption型を返す。SwiftのOptionalやResultと同じ目的。ここらへんは流行がある気がするが、個人的には分かりやすいと思う。
loop {
if let Some(message) = message_queue.pop_front() {
if message.src == message.to {
Optionの中身はエラーを示すNoneと、正常結果のSome(T)の列挙型。Rustのletがパターンマッチングであることを利用して上のif文においてSome(T)が返って来たら、messageにTを代入してtrueとなる。Noneの場合はマッチしないので、falseとなる。
pub enum Option<T> {
None,
Some(T),
}
幅優先, 深さ優先
Messageの送受信のイメージでFILO (First-In Last-Out)のqueueをつかっている。pop_frontの場所をpop_backにすると深さ優先探索になり、短いパス長の広報が抑えられるので、効率が良くなると思う。最短経路を求める場合は、短いパス長を早く広報するため、幅優先探索の方がいい。
loop {
if let Some(message) = message_queue.pop_front() {
if message.src == message.to { println!{"Loop detection at {} length {}", message.src, message.length}; break;}
関連記事
Rustで動的計画法の実装:
🐸Frog | 🌴Vacation | 🎒Knapsack | 🐍LCS | 🚶♂️Longest Path | 🕸️Grid | 💰Coins | 🍣Sushi | 🪨Stones | 📐dequeue | 🍬Candies | 🫥Slimes | 💑Matching | 🌲Indipendent Set | 🌻Flowers | 👣Walk | 🖥️Digit Sum | 🎰Permutation | 🐰Grouping | 🌿Subtree | ⏱️Intervals | 🗼Tower | 🐸Frog3
Discussion