# Efficient Strategies Algorithms for Resource Allocation Problems
## 4 Comparison of Strategies
### Evaluation of Strategies  
The definition of strategies of the previous section leads to three proposed strategies. First one that generates more strategies than the the two followings with a very fast generation algorithm and a complexity in \(\theta(\mathit{nb\_soldats})\) if the number of fields is equal to 2 or \(\theta(\mathit{nb\_soldats}\times\mathit{nbs})\) if the number of fields is 3. In both cases, the complexity is good and is either linear or quadratic. As for the second and third propositions, they have an algorithmic complexity of \(\theta(\mathit{nbw}\times\mathit{nb}\times\mathit{nbs}\times\mathit{nbs})\). This complexity is polynomial, and as soon as the number of resources or that of fields increases and reaches comes, the execution times of the algorithm increase (see Table 2). The only difference between the second and the third proposition is a conditional block whose complexity is constant.  
The simulation algorithms of the three propositions have the same complexity and are in \(\theta(\mathit{nbw}\times\mathit{nb}\times\mathit{nbs})\) (see proof in Appendices A and B).  
Tables 2 and 3 present the comparisons of different proposed strategies. The first table makes a comparison based on the algorithmic complexity of the algorithms for generating and simulating strategies; as for the second table, it will make a comparison between the results of several simulations with a some resources on some fields.  
In Table 3, we have: \(\mathit{nb\_soldats}\) is the number of resources, \(\mathit{nb}\) is the number of fields, \(\mathit{nbs}\) is the number of strategies generated, and \(\mathit{nbw}\) is the number of times the _\"do-while\"_ loop does.  
Evidence of these complexities is detailed in the Appendix A.  
In Table 2, we have: \(\mathit{NA}\): Not applied. Indeed, the first proposal could not generate with a number of fields greater than 3.  
The execution time is represented by a couple of values \(\mathit{(X/Y)}\) where \(\mathit{X}\) is the execution time of the generation of the strategies and \(\mathit{Y}\) is the execution time of the strategy simulation.  
Figure 5: Graphical representation of the simulation result with heterogeneous fields and resources.  
\begin{table}
\begin{tabular}{c c c c c c c c} \hline \hline \multirow{2}{*}{**Number of Fields**} & \multirow{2}{*}{**Number of Resources**} & \multicolumn{2}{c}{**1 st Proposition**} & \multicolumn{2}{c}{**2 nd Proposition**} & \multicolumn{2}{c}{**3 rd Proposition**} \\  & & **Generated Strategies** & **Execution Time** & **Generated Strategies** & **Execution Time** & **Generated Strategies** & **Execution Time** \\ \hline \multirow{8}{*}{2} & 10 & 11 & 0/0 & 5 & 0.001/0 & 6 & 0.002/0 \\  & 20 & 21 & 0/0 & 10 & 0.002/0.001 & 11 & 0.002/0.001 \\  & 50 & 51 & 0/0 & 25 & 0.002/0.001 & 26 & 0.002/0.001 \\  & 100 & 101 & 0/0.002 & 50 & 0.002/0.001 & 51 & 0.002/0.001 \\  & 500 & 501 & 0.001/0.01 & 250 & 0.004/0.007 & 251 & 0.004/0.007 \\  & 1000 & 1001 & 0.001/0.025 & 500 & 0.003/0.015 & 501 & 0.003/0.015 \\ \hline \multirow{8}{*}{3} & 10 & 66 & 0.002/0.003 & 8 & 0.002/0.02 & 14 & 0.002/0.0 \\  & 20 & 231 & 0.002/0.008 & 33 & 0.003/0.001 & 44 & 0.003/0.001 \\  & 50 & 1326 & 0.003/0.03 & 208 & 0.012/0.006 & 234 & 0.013/0.007 \\  & 100 & 5151 & 0.004/0.25 & 833 & 0.03/0.04 & 884 & 0.034/0.05 \\  & 500 & 125,751 & 0.018/145 & 20,833 & 13.7/27 & 21,084 & 14/28.5 \\  & 1000 & 501,501 & 0.033/3519 & 83,333 & 284/323.7 & 83,834 & 285/325 \\ \hline \multirow{8}{*}{4} & 10 & NA & NA & 9 & 0.002/0 & 23 & 0.003/0.0 \\  & 20 & NA & NA & 64 & 0.006/0.002 & 107 & 0.008/0.004 \\ \cline{1-1}  & 50 & NA & NA & 920 & 0.034/0.063 & 1154 & 0.05/0.08 \\ \cline{1-1}  & 100 & NA & NA & 7153 & 1.91/2.93 & 8036 & 22/3.1 \\ \cline{1-1}  & 300 & NA & NA & 189,375 & 1501/1745 & 197,017 & 1580/1810 \\ \hline \hline \end{tabular}
\end{table}
Table 2: Results of some executions of the algorithms of the proposed strategies.