4

PHPスクリプトを使用して板取り問題を実装する必要があります。私の数学のスキルはそれほど優れていないので、私はそれを総当たり攻撃しようとしています。

これらのパラメータから始めます

  • $ Inventoryは、カット可能な長さの配列です。
  • $ requestedPiecesは、顧客から要求された長さの配列です。
  • $solutionは空の配列です

私は現在、この再帰関数を実行して、考えられるすべての解決策を考え出しました。

function branch($inventory, $requestedPieces, $solution){
    // Loop through the requested pieces and find all inventory that can fulfill them
    foreach($requestedPieces as $requestKey => $requestedPiece){
        foreach($inventory as $inventoryKey => $piece){
            if($requestedPiece <= $piece){
                $solution2 = $solution;
                array_push($solution2, array($requestKey, $inventoryKey));
                $requestedPieces2 = $requestedPieces;
                unset($requestedPieces2[$requestKey]);
                $inventory2 = $inventory;
                $inventory2[$inventoryKey] = $piece - $requestedPiece;
                if(count($requestedPieces2) > 0){
                    branch($inventory2, $requestedPieces2, $solution2);
                }else{
                    global $solutions;
                    array_push($solutions, $solution2);
                }
            }
        }
    }
}

これで私が発見した最大の非効率性は、同じソリューションを複数回見つけるが、ステップの順序が異なることです。

例えば：

  • $ Inventory = array（1.83、20.66）;
  • $ requestedPieces = array（0.5、0.25）;

関数は8つのソリューションを考え出しますが、4つのソリューションを考え出す必要があります。これを解決するための良い方法は何ですか。

4

1 に答える 1

3

これはあなたの質問に答えませんが、私はそれが言及される価値があるかもしれないと思いました：

総当たり攻撃ではなく、問題を解決する方法は他にもいくつかあります。このトピックに関するウィキペディアのページはかなり徹底的ですが、他の2つの簡単なアイデアについて説明します。ウィキペディアの用語を特定の単語に使用します。つまり、在庫ピースのマスターと、要求されたピースのカットを使用します。セットを使用して、特定のマスターに関連するカットのセットを示します。

最初のものは欲張りアルゴリズムに基づいており、利用可能な最大のカットでセットを埋め、それ以上カットが収まらなくなるまで、各マスターに対して同じプロセスを繰り返し、それぞれのセットを生成します。

2つ目はより動的です：再帰を使用し（あなたのように）、再帰の各ステップでマスターとカットの残りの長さに最適なものを探します。目標は、これ以上カットが収まらないときに無駄な長さを最小限に抑えることです。 。

function branch($master, $cuts, $set){
     $goods = array_filter($cuts, function($v) use ($master) { return $v <= $master;});
     $res = array($master,$set,$cuts);
     if (empty($goods))
         return $res;
     $remaining = array_diff($cuts, $goods);
     foreach($goods as $k => $g){
         $t = $set;
         array_push($t, $g);
         $r = $remaining;
         $c = $goods;
         for ($i = 0; $i < $k; $i++)
             array_push($r,array_shift($c));
         array_shift($c);
         $t = branch($master - $g, $c, $t);
         array_walk($r, function($k,$v) use ($t) {array_push($t[2], $v);});
         if ($t[0] == 0) return $t;
         if ($t[0] < $res[0])
             $res = $t;
     }
     return $res;
}

上記の関数は、特定のマスターに最適なセットを提供するはずです。3つの値の配列を返します。

  • マスターの無駄な長さ
  • セット
  • 残りのカット

パラメータは次のとおりです

  • マスターの長さ、
  • 実行するカット（降順で並べ替える必要があります）、
  • すでにスケジュールされているカットのセット（既存のセット。各マスターの最初の呼び出しでは空になります）

警告：それはマスターの順序に依存します、あなたは確かにマスターの最良の順序を見つけるためにすべての関連する可能性を試みる関数を書くことができます。

于 2013-01-03T02:27:40.093 に答える