在PHP中实现切削刀具算法 [英] Implementing Cutting Stock Algorithm in PHP

问题描述

我需要使用php脚本实现切割库存问题。
由于我的数学技能不是那么好，我只是想蛮力。

从这些参数开始

• $ inventory是可以切割的长度数组。


• $ requestedPieces是$请求的长度数组b $ b个客户。


• $ solution是一个空数组

我目前已经计算出此递归函数列出所有可能的解决方案：

 功能分支（$ inventory，$ requestedPieces，$ solution）{
 //循环遍历所请求的零件并找到可以满足它们的所有库存$ b 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）{
分支（$ inventory2，$ requestedPieces2，$ solution2）; 
}其他{
全球
解决方案
； 
 array_push（$ solutions，$ solution2）; 
} 
} 
} 
} 
} 
  

我发现的最大效率低下是，它将多次找到相同的解决方案，但是步骤的顺序不同。

例如：

• $ inventory = array（1.83，20.66）;


• $ requestedPieces = array（0.5，0.25 ）;

该函数将提供8个解决方案，而应提供4个解决方案。
什么是解决此问题的好方法。

解决方案

这不能回答您的问题，但我认为可以值得一提的是：

您还有其他几种解决问题的方法，而不是蛮力地解决。关于该主题的维基百科页面相当详尽，但我只简单介绍两个想法。我将使用Wikipedia术语来表示某些单词，即 master 用于库存件，而 cut 用于所请求的件。我将使用 set 来表示与给定母版有关的一组削减。

第一个基于贪婪算法，其中包括用最大可用切割填充一组，直到不再适合任何切割为止，然后重复每个母版都执行相同的过程，为每个母版产生一组。

第二个是更多动态：它使用递归（像您一样），并在递归的每一步中寻找最适合母版和裁片剩余长度的方法，目的是在没有更多裁片适合时，将浪费的长度最小化。

  function分支（$ master，$ cuts，$ set）{
 $ goods = array_filter（$ cuts，function （$ v）使用（$ master）{return $ v< = $ master;}）； 
 $ res = array（$ master，$ set，$ cuts）; 
 if（empty（$ goods））
 return $ res; 
 $ remaining = array_diff（$ cuts，$ goods）; 
 foreach（$商品为$ k => $ g）{
 $ t = $ set; 
 array_push（$ t，$ g）; 
 $ r =剩余$; 
 $ c = $商品； 
 for（$ i = 0; $ i< $ k; $ i ++）
 array_push（$ r，array_shift（$ c））; 
 array_shift（$ c）; 
 $ t =分支（$ master-$ g，$ c，$ t）; 
 array_walk（$ r，function（$ k，$ v）use（$ t）{array_push（$ t [2]，$ v）;}）; 
 if（$ t [0] == 0）返回$ t; 
 if（$ t [0]< $ res [0]）
 $ res = $ t; 
} 
返回$ res； 
} 
  

上面的函数应该为您提供给定母版的最佳设置。它返回一个由3个值组成的数组：

• 主版上浪费的长度


• 集合


• 剩余的削减量

参数为

• 主要长度，


• 要执行的切割（必须按降序排列），


• 已排定的割料组（一个已存在的割组，对于每个主控制器的第一次呼叫将为空）

注意事项：这取决于根据主人的命令，您当然可以编写一个函数，尝试所有相关的可能性以找到主人的最佳命令。

I need to implement the Cutting Stock Problem with a php script. As my math skills are not that great I am just trying to brute force it.

Starting with these parameters

• $inventory is an array of lengths that are available to be cut.
• $requestedPieces is an array of lengths that were requested by the customer.
• $solution is an empty array

I have currently worked out this recursive function to come up with all possible solutions:

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);
                }
            }
        }
    }
}

The biggest inefficiency I have discovered with this is that it will find the same solution multiple times but with the steps in a different order.

For example:

• $inventory = array(1.83, 20.66);
• $requestedPieces = array(0.5, 0.25);

The function will come up with 8 solutions where it should come up with 4 solutions. What is a good way to resolve this.

解决方案

This does not answer your question, but I thought it could be worth being mentioned:

You have several other ways to solve your problem, rather than brute forcing it. The wikipedia page on the topic is pretty thorough, but I'll just describe two others simpler ideas. I will use the wikipedia terminology for certain words, namely master for inventory piece, and cut for a requested piece. I will use set to denote a set of cuts pertaining to a given master.

The first one is based on the greedy algorithm, and consist in filling a set with the largest available cut, until no more cut may fit, and repeat that same process for each master, yielding a set for each one of them.

The second one is more dynamic: it uses recursion (like yours), and look for the best fit for the remaining length of master and cuts at each step of the recursion, the goal being to minimize the wasted length when no more cuts can fit.

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;
}

The function above should give you the optimal set for a given master. It returns an array of 3 values:

• the wasted length on master
• the set
• the remaining cuts

The parameters are

• the master length,
• the cuts to be performed (must be sorted in descending order),
• the set of cuts already scheduled (a preexisting set, which would be empty for the first call for each master)

Caveats: It depends on the masters' order, you could certainly write a function which tries all the relevant possibilities to find the best order of masters.

这篇关于在PHP中实现切削刀具算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！