PHP에서 무한 루프를 감지하고 피하는 방법

Question

이 질문은 내 PHP 코드의 버그에 관한 것이 아니며, (아직 PHP 스크립트가없는 한, 지금도 알고리즘에 대해 생각하고 있습니다.) 문제는 다음과 같습니다.

현재 내부 부품을 기반으로 기계 부품을 제작할 수있는 기계 부품 관리자 (예 : 자전거 부품이 있고 해당 부품의 경우, 나는 2 개의 바퀴, 1 개의 handlebar를 필요로한다. 그리고 바퀴를 위해 나는 타이어 등을 필요로한다).

각 내부 부품도 내 데이터베이스의 기계적 조각이며 고유 한 ID로 연결되어 있습니다 (많은 PDF, 많은 3D 파일 등이 들어있는 폴더가 있음).

내 데이터베이스를 나타내는 GUI가 있고 각 조각에는 내부 조각을 만드는 데 필요한 모든 파일을 수집하는 "빌드"버튼이 있습니다. 예를 들어

:

내 자전거는 ID N ° 1을 갖는다는 휠이 ID를 갖는 N ° (2)와 핸들은 ID N ° (3)를 갖는다.

알고리즘은 매우 간단하지만 무한 루프에 취약합니다.

다음과 같은 경우를 피하려면 어떻게해야합니까? 내 자전거 (id 1)에 바퀴 (ID 2)가 필요하고 바퀴에 자전거가 필요하면 ... 자전거가 필요한 바퀴가 필요합니다. ...?

고맙습니다.

Answer 1

빌드 기능을 실행하는 동안 이미 해시로 결과를 생성 한 모든 구성 요소를 추적하고, 그 중 하나가 다시 발생하면 무시합니다.

// Sample "database": 
$components = array(
    1 => array (
     "id" => 1, 
     "name" => "bike", 
     "needs" => array (
      array ("id" => 2, "count" => 2), // 2 wheels 
      array ("id" => 3, "count" => 1), // 1 handlebar 
     ), 
     "folder" => "/my/folders/bike" 
    ), 
    2 => array(
     "id" => 2, 
     "name" => "weel", 
     "needs" => array(
      array("id" => 4, "count" => 1), // 1 tire 
      array("id" => 1, "count" => 1) // 1 wheel?? - erroneous information! 
     ), 
     "folder" => "/my/folders/wheel" 
    ), 
    3 => array(
     "id" => 3, 
     "name" => "handlebar", 
     "needs" => array(), 
     "folder" => "/my/folders/handlebar" 
    ), 
    4 => array(
     "id" => 4, 
     "name" => "tire", 
     "needs" => array(), 
     "folder" => "/my/folders/tire" 
    ) 
); 

// Build function: returns a list of folders related 
// to all the parts of the given component. 
function build($componentId, $components, $hash = array()) { 
    // Protection against infinite recursion: 
    if (isset($hash[$componentId])) return []; 
    $elem = $components[$componentId]; 
    // set hash, keyed by component ID. 
    $hash[$componentId] = 1; 
    // Add folder for this component 
    $folders[] = $elem['folder']; 
    // Collect folders of dependent components recursively 
    foreach($elem['needs'] as $child) { 
     // ... pass the hash as third argument 
     $folders = array_merge($folders, build($child["id"], $components, $hash)); 
    } 
    return $folders; 
} 

// Example call: build component with ID 1, returning a list of folders: 
print_r (build(1, $components)); 

위의 코드의 출력은 다음과 같습니다 : 여기

일부 상용구 당신이 영감을 사용할 수있는 코드입니다 그래서

Array 
(
    [0] => /my/folders/bike 
    [1] => /my/folders/wheel 
    [2] => /my/folders/tire 
    [3] => /my/folders/handlebar 
) 

자전거가 두 번 발생했습니다, 그것은이었다 그냥 무시.

Answer 2

자녀 - 부모 관계를 구분해야합니다.

자전거는 어린이 항목으로 휠을 포함 할 수 있으며 휠에는 자전거를 부모 항목으로 포함 할 수 있습니다. 또한 하나의 스크류와 타이어는 휠의 자식 아이템이 될 수 있습니다.

네비게이션은 상위 항목에서 하위 항목까지 또는 그 반대 방향 중 하나의 방향을 가져야합니다.