1. ホーム
  2. recursion

[解決済み] 再帰性の実例【非公開

2022-09-25 16:26:44

質問

とは 現実世界 の問題で、深さ優先探索(DFS)以外に再帰的なアプローチが自然な解決策となるものは何でしょうか?

(私は ハノイの塔 , フィボナッチ数 とか、階乗の実戦問題とか。それらは私の中では少し作為的なものです)。

解き方は?

ここにはたくさんの数学的な例がありますが、あなたが欲しかったのは 実世界 ということで、少し考えて、これが私が提供できる最高の例です。

ある伝染病菌に感染した人がいます。これは致命的ではなく、すぐに治ります(A型)。

このため、B型がA型に感染すると、非常に迷惑な大混乱を引き起こす。

あなたの仕事は、すべてのB型を追跡し、病気のバックボーンを停止するためにそれらを免疫することです。 残念ながら、A型の人々はB型に効く治療薬に致命的なアレルギーを持っているので、あなたはすべての人に全国的な治療法を管理することはできません。

この方法は、社会的な発見であり、感染者(A型)がいる場合、過去1週間の接触者をすべて選び、それぞれの接触者に印を付けていきます。その人が感染していることをテストしたら、その人をフォローアップのキューに追加します。人がタイプ B であるとき、彼らを先頭に "フォローアップ" に追加します (これを速く止めたいからです)。

与えられた人を処理した後、キューの先頭からその人を選択し、必要であれば免疫を適用します。以前に訪問していないすべてのコンタクトを取得し、彼らが感染しているかどうかをテストします。

感染者のキューが0になるまで繰り返し、次のアウトブレイクを待ちます。

( OK、これは少し反復的ですが、再帰的な問題を解決する反復的な方法です。この場合、問題への可能性の高い経路を発見しようとする人口基盤の幅の最初のトラバーサルです。さらに、反復的な解決はしばしばより速く、効果的です。......くそっ! )