Optimization of the Item Selection Problem Using Multi-Division Dynamic Programming

利用多區間動態規劃技術於選題策略之研究

對於解組合最佳化問題上，動態規劃（Dynamic Programming， DP）是一種功能強大的尋求最佳解之有效技術。但是，在多變數（維度）的二次方程式中，DP無法找到0～1 整數規劃的最佳解。在本文中，研究者提出一新的技術「多區間動態規劃」（Multi-Division Dynamic Programming， MDDP）做為選題策略。在建構測驗時，MDDP 除了可以改善DP 的效率和正確性外，亦可有效解決誤差函數為二次函數時，所導致誤差值遞減後再遞增的問題。實驗結果顯示，研究者所提出的方法能產生誤差非常小的平行測驗，優於其他新近所提的方法，而且MDDP 的執行時間與誤差的改善率比傳統DP好，改進比例分別達到88.3%和94.9%，肯定了本研究所提之多區間動態規劃技術，對於測驗之選題策略，具有高效益與高精確度，對測驗之研究也提供一有用的技術。

Dynamic Programming (DP) is a powerful method for solving combinatorial optimization problems. However， it is incapable of finding the optimal solutions of 0-1 integer programming in the multi-dimensional quadratic equation. In this study， we proposed a new approach called “Multi-Division Dynamic Programming (MDDP)” that improves the efficiencyand the accuracy of dynamic programming in constructing parallel tests for minimizing the deviations of quadratic equations. Experimental results show that our proposed approach can construct the parallel tests with the lowest error than the other methods (e.g.，Genetic Algorithm， Greedy Approach， Neural Network， Swanson & Stocking， andWang &Ackerman). The execution-times and the deviation improvement ratios of MDDP are morethan 88.3% and 94.9% better than DP. The proposed MDDP would be useful for its effectiveness and accuracy to the item selection problem.