こんにちは。@kenkoooo です。
教科書に載っているようなアルゴリズムって勉強しても仕事では全然使わない、と見せかけて意外と使うなぁと感じたので、仕事で見たことがあるアルゴリズムをいくつか紹介します。
広告を配信したい！
あなたはウェブサービスの会社で働いています。サービス利用者のユーザーに広告を配信することで、広告主からお金をもらっています。
あなたは今から広告主からもらった広告をユーザーに配信します。
- 広告主が
社います。
- 広告主
は広告を
人に配信したいです。
- 配信対象となるユーザーが
人います。
- ユーザー
の広告は受け取りを許可しています。
- ユーザー
件までしか広告を受け取りたくないです。
上記のような条件の中で、どのように広告を配信したら良いでしょうか？
条件を整理する
条件を整理してみましょう。
各ユーザーごとに、受け取りを許可している広告主がいます。許可されていない広告主は、そのユーザーに広告を配信することができません。
この許可・不許可の関係は、次の図のようなものになります。
また、広告主 は
人のユーザーに広告を配信したい一方で、ユーザー
は
件を超える広告は受け取りたくないという条件もあります。
考察
ここで、広告を水の流れのようなものと考えます。広告主 には
の広告が流れ込みます。この広告をユーザーの方へと流していきます。
また、ユーザー には
ずつ広告が流入し、最大で
まで広告を受け取り、受け流すことができます。
見方を変える
見方を変えると、広告主 → 河川、ユーザー → 河口と言い換えて、この問題の全体像は次のように言い換えられます。
「ダムから河川 へ、
の水が流入します。河川
から河口
へ川があり、
の水を流すことができます。河口
は
まで水を受けて海へと流すことができます。どのように水を流したら良いでしょうか？」
この問題は図示すると下の図のようになります。
このように、ネットワーク上でノードからノードへ容量が決まった辺があり、入口から出口へ容量の許す限り流す問題は最大流問題と呼ばれています。最大流問題は Ford–Fulkerson のアルゴリズムや、Dinic のアルゴリズムなどを使って解くことができます。
音声を認識したい！
あなたは AI スピーカーの会社で働いています。入力されてきた音声を日本語変換し、自然言語理解エンジンに渡すモジュールを開発しています。
例えば、「きょーのてんきわ？」と聞かれた時に「今日の天気は？」と変換したいです。
具体的には以下のような条件で考えることができます。
- 単語と読み方の対応をまとめた辞書ファイルがあります。
- 単語から単語への繋がりの自然さをあらかじめ計算したものがあります。不自然さをコストとしていて、大きいほどその単語の繋がりが不自然だと言えます。
これらを使って、入力をどのように変換したら良いでしょうか？
考察
例えば、辞書ファイルに登録されている単語が以下のようなものだったとします。
ここから、入力の候補を次の図のように作ることができます。
さらに、この図で単語から単語への繋がりが不自然なもの（コストが高いもの）を破線にすると、次のような図になります。
このように、変換の候補をネットワークとして考えることができました。ここから、始めから終わりまでの移動で最もコストが小さい候補を見つけたいですが、どのようにしたら良いでしょう？
見方を変える
先ほどの図について、単語を駅、単語から単語へのコストを距離と考えると、次の図のように考えることができます（無理やり当てはめたので地図としてはかなり不自然です…）。
先ほどの図で自然な変換候補を見つけることは、この図で東京から福岡への最短経路を見つけることと同じであると考えられます。
このように、ネットワーク上でノードからノードへコストを持った辺があり、あるノードから別のノードへ辺をたどって移動するコストが最小の経路を見つける問題は最短経路問題と呼ばれています。最短経路問題は Dijkstra のアルゴリズムなどで解くことができます。
（実際の変換はもう少し色んな条件を考慮する必要があり、別のアルゴリズムが用いられています）
自販機を補充したい！
あなたは飲料メーカーで働いています。今から全国の自動販売機に飲料を届けます。
- 配送所が
ケースあたり
円の配送コストがかかる。
- 自動販売機が
台あり、自動販売機
ケースまで納品することができる。
配送所 から自動販売機
に配送することができる。この配送には
ケースあたり
円の配送コストがかかる。
このとき、合計 ケースを全国の自動販売機に届けたいとき、配送コストの最小値はいくらになるでしょうか？
考察
この問題は、最初の最大流問題とほとんど同じように考えることができます。先ほどは広告を水のように流しましたが、今回は飲料ケースを流します。
最大流問題との大きな違いは、ケースを流すごとにコストがかかることです。このような問題は最小費用流問題と呼ばれていて、主双対法などで解くことができます。
まとめ
身近な生活の中で馴染みのあるアルゴリズムが使われていると嬉しいですね。
最後に
estie にはアルゴリズム的な面白さは全く期待しないで入社したのですが、不動産の情報はかなり複雑な形をしていて、それらを参照・更新する複雑なクエリに効率よく答えるにはどのようなデータ構造を使うか等、意外に考えることがあります。そういうのを考えたり実装したりする人を探しています（実装メインです）。ぜひ、話だけでも聞きに来てください。
