1

次のようなグラフで最も重いパスを検索する必要があります。

        1

      2  1

    4  5  8

  2  2  3  4

(この例では 1,1,8,4) これまでのようなグラフ。したがって、最下位を除いて 2 つの子を持つ要素です。誰に子供がいて、共通の子供がいます。たとえば、(上のグラフで) 5 (3. 行) は 2 と 1 (2. 行) の共通の子供です。したがって、これらはエッジではなくノードであり、値があります。

私はphpでアルゴリズムを書きました：

class node{
    public $children = array();
    public $value;
    public $_heavier = null;
    public $_value = null;

    function __construct($value, $children) {
        $this->value = $value;
        $this->children = $children;
    }

    function heavier() {
        if (null !== $this->_value) {
            echo 'b' . $this->value . '<br>';
            return $this->_value;
        }

        $val = $this->value;

        if ($this->children[0]) {
            $c1 = $this->children[0]->heavier();
            $c2 = $this->children[1]->heavier();

            if ($c1 > $c2) {
                $this->_heavier = 0;
                $val += $c1;
            } else {
                $this->_heavier = 1;
                $val += $c2;
            }
        }

        echo 'a' . $this->value . '<br>';
        $this->_value = $val;

        return $val;
    }

    function getPath() {
        if (null !== $this->_heavier) {
            echo $this->children[$this->_heavier]->getPath();
        }
        return $this->value;
    }
}

$exists = array();
function a($row, $item) {
    global $input, $exists;

    $nextRow = $row + 1;
    $child1No = $item;
    $child2No = $item + 1;

    $child1 = null;
    if (isset($input[$nextRow][$child1No])) {
        $child1 = a($nextRow, $child1No);
    }

    $child2 = null;
    if (isset($input[$nextRow][$child2No])) {
        $child2 = a($nextRow, $child2No);
    }

    if (!isset($exists[$row][$item])) {
        $obj = new node($input[$row][$item], array($child1, $child2));
        $exists[$row][$item] = &$obj;
    } else {
        $obj = &$exists[$row][$item];
    }
    return $obj;
}

$nodes = a(0, 0);
$nodes->heavier();
echo $nodes->getPath();
echo '<br>';

動作しますが、時間がかかりすぎます。スピードアップするには？

どうも。

4

1 に答える 1

1

あなたのアルゴリズムは可能な限り最適です-ノードの数がO(n)どこにあるかに時間がかかります。nこれより速いものは何もないことは簡単に証明できます。

あなたのアルゴリズムの遅い部分は -ing だと思います。これは非常に重い操作であり、あまりにも多くechoの場合、アルゴリズムがかなり遅くなる可能性があります。echo

PS: ところで、アルゴリズムを実行するノードの数はいくつですか? 本当に10だけですか？

于 2013-03-09T10:21:44.057 に答える