php - 特殊图中的最重路径(PHP)

Question

我必须在图中搜索最重的路径，例如:

        1

      2  1

    4  5  8

  2  2  3  4

(本例中为 1,1,8,4)像这样的图表。所以它是一个有两个 child 的元素，除了最底层。谁有 child ，他们有一个共同的 child ，例如(在上图中)5(在第 3 行中)是 2 和 1(在第 2 行中)的普通 child 。所以这些是节点而不是边，它们有一个值。

我用 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>';

这是有效的，但时间太多了。如何加速？

谢谢。

Answer 1

您的算法是最优化的 - 您花费了 O(n) 时间，其中 n 是节点数。可以很容易地证明，没有比这更快的了。

我认为您的算法中较慢的部分是 echo-ing - 这是一个非常繁重的操作，并且当您 echo 太多时可能会减慢您的算法.

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