PHPの無限ループを検出して回避する方法

Question

この質問は私のPHPコードのバグではありません（私はまだPHPスクリプトはありませんが、アルゴリズムはまだ考えています）。ここに問題があります：

私は現在、内部部品に基づいて機械部品を作ることができる機械部品マネージャーに取り組んでいます（たとえば、私は自転車部品を手に入れました。私は2つの車輪、1つのハンドルバーを必要とし、車輪のためにはタイヤなどが必要です）。

各内部部品も私のデータベースの機械的な部分であり、一意のIDでリンクされています（多くのPDFや多くの3Dファイルなどを含むフォルダを持っています）。

私は自分のデータベースを表すGUIを持っており、各部分には内部の部品を構築するのに必要なすべてのファイルを収集するための「ビルド」ボタンがあります。例えば

：

マイ自転車はID N°1を有し、ホイールはID N°2を有し、ハンドルは、ID N°3を有しています。

アルゴリズムは非常に単純ですが、無限ループで脆弱です。

私の自転車（id1）が車輪（id2）を必要とし、私の車輪が自転車を必要とする場合...自転車が必要な車輪が必要な場合はどうすればいいですか？ ...？

ありがとう、

Answer 1

ビルド関数の実行中に、すでにハッシュで結果を生成しているすべてのコンポーネントを追跡し、それらのうちの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

子と親の関係を区別する必要があります。

自転車は車輪を子品目として含むことができ、車輪は自転車を親品目として含むことができる。また、1本のスクリューとタイヤは、車輪の子品にすることもできます。

ナビゲーションには、親アイテムから子アイテムまで、またはその反対のいずれかの方向があります。