2

私は配列を持っています：

$data = array(
  1 => array(
    "time" => 1,
    "parent" => array(4)
  ),
  2 => array(
    "time" => 3,
    "parent" => array(4, 5)
  ),
  3 => array(
    "time" => 2,
    "parent" => array(6)
  ),
  4 => array(
    "time" => 1,
    "parent" => array(6)
  ),
  5 => array(
    "time" => 1,
    "parent" => array(4)
  ),
  6 => array(
    "time" => 1,
    "parent" => array()
  )
);

キーは要素のIDであり、親は要素の配列であり、要素IDを参照し、時間は単なる整数です。

これは、特定のアレイの図解例です。

スキーマ

左下の整数は「id」で、中央の整数は「time」です。

ここでの私の目標は、この配列の中で最も時間のかかるパスを見つけることです。与えられた例では、パスは2-> 5-> 4-> 6（idワイズ）であり、全体で6つの「時間」になります。紙の上ではかなり簡単に見えますが、最も時間のかかるパスの要素を取得するためにアルゴリズムをコーディングすることは実際にはできないようです。どんな助けでもいただければ幸いです。

アルゴリズムはブルートフォース攻撃のようなものであり、利用可能なすべてのオプションを確認する必要があると思います。したがって、指定された配列では、次のようになります。

1 -> 4 -> 6 = 3
2 -> 4 -> 6 = 5
2 -> 5 -> 4 -> 6 = 6 
3 -> 6 = 3
4 -> 6 = 2
5 -> 4 -> 6 = 3

前もって感謝します。

4

1 に答える 1

1

これは、配列にループがない場合にのみ機能することに注意してください。

// Note: built this in the SO editor, might have bugs
$cached = [];
$arrays = []; // Do this yourself

function get_path($num) {
    global $arrays, $cached;
    if (isset($cached[$num])) return $cached[$num];

    $array = $arrays[$num];
    $maxtime = $array['time'];
    $bestpath = array($num);
    foreach ($array['parent'] as $i) {
        $path = get_path($i);
        if ($path['time']+$array['time'] > $maxtime) {
            $maxtime = $path['time'] + $array['time'];
            $bestpath = array_merge(array($num),$path['path']);
        }
    }

    $cached[$num] = array('path' => $bestpath, 'time' => $maxtime);
    return $cached[$num];
}

var_dump(get_path(5));

実際にはブルートフォース攻撃ではなく、に十分に近い必要がありO(n)ます。基本的な考え方は、たどることができるパスをキャッシュするだけです。

注：ここでは少しCスタイルの構文を使用しましたが、理想的には、実際にはこのようなコードを記述しないでしょう。

于 2013-01-20T15:30:44.603 に答える