最大確率のパス

1514年。最大確率のパス

難易度: 中

トピック: 配列、グラフ、ヒープ (優先キュー)、最短パス

n 個のノード (0 からインデックス付き) の無向重み付きグラフが与えられます。これはエッジ リストで表されます。ここで、edges[i] = [a, b] は、ノード a と b を成功の確率で接続する無向エッジです。そのエッジのトラバースの結果 succProb[i].

2 つのノードの開始点と終了点を指定すると、開始点から終了点までの成功確率が最大となるパスを見つけ、その成功確率を返します。

始点から終点までのパスがない場合は、0 を返します。あなたの答えは、正解と最大 1e-5 の差がある場合に受け入れられます。

例 1:

• 入力: n = 3、エッジ = [[0,1],[1,2],[0,2]]、succProb = [0.5,0.5,0.2]、開始 = 0、終了 = 2
• 出力: 0.25000
• 説明: 開始から終了まで 2 つのパスがあり、1 つは成功確率 = 0.2、もう 1 つは 0.5 * 0.5 = 0.25 です。

例 2:

• 入力: n = 3、エッジ = [[0,1],[1,2],[0,2]]、succProb = [0.5,0.5,0.3]、開始 = 0、終了 = 2
• 出力: 0.30000

例 3:

• 入力: n = 3、エッジ = [[0,1]]、succProb = [0.5]、開始 = 0、終了 = 2
• 出力: 0.00000
• 説明: 0 と 2 の間にパスはありません。

制約:

• 2
• 0 n
開始 != 終了
0 a != b
0 0 各 2 つのノード間には最大でも 1 つのエッジがあります

ヒント:

確率を乗算すると精度誤差が生じます。
対数確率を計算して、数値を乗算するのではなく合計します。
ダイクストラのアルゴリズムを使用して、すべてのコストを打ち消した後の 2 つのノード間の最小パスを見つけます。

解決策:

ダイクストラのアルゴリズムの修正バージョンを使用できます。最短経路を見つけるのではなく、成功の確率を最大化します。

このソリューションを PHP で実装してみましょう: 1514。最大確率のパス

<?php
/**
 * @param Integer $n
 * @param Integer[][] $edges
 * @param Float[] $succProb
 * @param Integer $start_node
 * @param Integer $end_node
 * @return Float
 */
function maxProbability($n, $edges, $succProb, $start_node, $end_node) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$n1 = 3;
$edges1 = [[0,1],[1,2],[0,2]];
$succProb1 = [0.5,0.5,0.2];
$start_node1 = 0;
$end_node1 = 2;

echo maxProbability($n1, $edges1, $succProb1, $start_node1, $end_node1);//Output: 0.25000


$n2 = 3;
$edges2 = [[0,1],[1,2],[0,2]];
$succProb2 = [0.5,0.5,0.3];
$start_node2 = 0;
$end_node2 = 2;

echo maxProbability($n2, $edges2, $succProb2, $start_node2, $end_node2);//Output: 0.30000


$n3 = 3;
$edges3 = [[0,1]];
$succProb3 = [0.5;
$start_node3 = 0;
$end_node3 = 2;

echo maxProbability($n3, $edges3, $succProb3, $start_node3, $end_node3); //Output: 0.00000
?>

説明：

1. グラフ表現

   : グラフは、各ノードが隣接ノードを指し、それらを接続するエッジの成功確率とともに隣接リストとして表現されます。

2. Max Probability Array

   : 配列 maxProb は、開始ノードから各ノードに到達する最大確率を格納するために使用されます。

3. Priority Queue

   : 最大ヒープ (SplPriorityQueue) は、最も確率の高いパスを最初に探索するために使用されます。これは、宛先ノードに到達したときに、最大の確率でパスが見つかるようにするために非常に重要です。

4. アルゴリズム

   :
   開始ノードの確率を 1 として初期化します (開始位置に留まる確率が 1 であるため)。
   優先キューを使用してノードを探索し、各近隣ノードに到達する最大確率を更新します。
   目的のノードに到達した場合は、確率を返します。
   パスが存在しない場合は、0 を返します。

出力：

以下の例:

$n = 3;
$edges = [[0,1],[1,2],[0,2]];
$succProb = [0.5,0.5,0.2];
$start_node = 0;
$end_node = 2;

出力は 0.25 になります。

このアプローチでは、確率計算の詳細を処理しながら、ダイクストラのアルゴリズムを使用した効率的なソリューションが保証されます。

連絡先リンク

このシリーズが役立つと思われた場合は、GitHub で リポジトリ

にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が最大確率のパスの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。