找到一个复杂的阵列

的最大路径我有一个数组：找到一个复杂的阵列

$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和时间仅仅是一个整数。

这是一个给定的阵列的图示的例子：

Schema

上左下整数是“ID”和在中间的整数“时间”。

我的目标是找到这个数组最耗时的路径。在给定的例子中，路径将是2-> 5-> 4-> 6（id wise），总体上导致6个“时间”。它看起来很容易在纸上，但我真的不能编码algorythm来获取最耗时的路径的元素。我将不胜感激任何形式的帮助。

我认为algorythm应该是bruteforce-ish，并检查所有可用的选项。因此，与给定的阵列它会像这样：

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

在此先感谢。

来源

2013-01-20 Tom

代码你有什么已经尝试过？ – BenM

你从哪里得到这个数组？ –

我试过各种方法，但似乎无法让它工作。这个数组只是一个缩小的var_dump（） – Tom

请注意，这只会在数组中没有循环时起作用。

// 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-20 15:30:44

谢谢。它像一个魅力工作;-) – Tom

找到一个复杂的阵列

回答

相关问题