1

我必须在图中搜索最重的路径：

        1

      2  1

    4  5  8

  2  2  3  4

（本例中为 1,1,8,4） 像这样的图形。所以它是一个元素，除了最底层之外还有两个孩子。谁有孩子，他们有一个共同的孩子，例如（在上图中）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节点的数量。可以很容易地证明，没有什么可以做得更快。

我认为你算法的慢部分是echo-ing - 这是一个非常繁重的操作，可能会因为你echo太多而使你的算法变慢。

PS：顺便问一下，你在多少个节点上执行你的算法？真的只有10吗？

于 2013-03-09T10:21:44.057 回答