Ovidiu Baniaș · 2018
In this paper we propose a quadratic dynamic programming algorithm applied in software testing domain, more specific in the test case selection decision making. We addressed a specific problem in software testing: running a subset of test cases from the whole set of available test cases in a limited time frame with the goal of maximizing the chances of finding potential defects. We employed both objective methods as the dynamic programming algorithm and subjective and empiric human decision as defining the selection and prioritization criteria. The proposed solution is suited for medium to large projects where in the worst-case scenarios the memory space complexity of the proposed algorithm does not exceed the order of GBytes. The proposed optimization algorithm is presented in pseudocode along with the dynamic programming recurrence formula and potential selection criteria as currently used in the industry.
Cited by 7
Yao Guo, Feng Lin, Hongyan Zhu · 2023
Aiming at the problem of tracking acoustic source with weak signal, dynamic programming (DP) is introduced to implement the Track Before Detect (TBD) task. In this method, a low threshold is used to obtain potential steered response power (SRP) measurements, and a recursive way is adopted to accumulate the source energy and to associate the source positions between adjacent frames. To reduce the miss detection, the predictive positions have also been treated as the measurements. Experiment results demonstrate that the proposed method can achieve more accurate position estimate than the existing TBD implemented by Particle Filter (PF) in moderate reverberation and noisy conditions.
Cited by 1
International Journal of Power Electronics and Drive System (IJPEDS) · Bulletin of Miscellaneous Information (Royal Gardens Kew) · 2021
This paper studies an approximate dynamic programming (ADP) strategy of a group of nonlinear switched systems, where the external disturbances are considered. The neural network (NN) technique is regarded to estimate the unknown part of actor as well as critic to deal with the corresponding nominal system. The training technique is simultaneously carried out based on the solution of minimizing the square error Hamilton function. The closed system’s tracking error is analyzed to converge to an attraction region of origin point with the uniformly ultimately bounded (UUB) description. The simulation results are implemented to determine the effectiveness of the ADP based controller.
Cited by 0
Qingwei Ping, Guifen Xia · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2009
To solve the laser weak echo detection under the clutter background, a dynamic programming (DP) technique has been developed for the detection of weak targets. The primary advantages of DP are its sensitivity to weak targets along with its robustness to laser echo glitter. DP technology turn searching track of the target into the subsection optimization of the target. First, DP algorithm finds all track subsection of target. Second, these track subsections are synthesized into the potential track of target. Third, the track of the same target is combined. Then the detection outcome is found. Theory analysis and the simulated results indicate a sensitivity improvement of detection performance over conventional detection algorithm.
Cited by 0
Alessandro Alla, Maurizio Falcone, Dante Kalise · SIAM Journal on Scientific Computing · 2015
We present an accelerated algorithm for the solution of static Hamilton--Jacobi--Bellman equations related to optimal control problems. Our scheme is based on a classic policy iteration procedure, which is known to have superlinear convergence in many relevant cases provided the initial guess is sufficiently close to the solution. This limitation often degenerates into a behavior similar to a value iteration method, with an increased computation time. The new scheme circumvents this problem by combining the advantages of both algorithms with an efficient coupling. The method starts with a coarse-mesh value iteration phase and then switches to a fine-mesh policy iteration procedure when a certain error threshold is reached. A delicate point is to determine this threshold in order to avoid cumbersome computations with the value iteration and at the same time to ensure the convergence of the policy iteration method to the optimal solution. We analyze the methods and efficient coupling in a number of examples in different dimensions, illustrating their properties.
Cited by 71Open access
Wei Jizhou, Yu Shuchun, Dong Wenfei et al. · 2016
Abstract. A stereo matching algorithm was proposed based on pyramid algorithm and dynamic programming. High and low resolution images was computed by pyramid algorithm, and then candidate control points were stroke on low-resolution image, and final control points were stroke on the high-resolution images. Finally, final control points were used in directing stereo matching based on dynamic programming. Since the striking of candidate control points on low-resolution image, the time is greatly reduced. Experiments show that the proposed method has a high matching precision. 1
Cited by 0
Gregory A. Godfrey, Warren B. Powell · 1999
We consider a stochastic version of a dynamic resource allocation problem. In this setting, reusable resources must be assigned to tasks that arise randomly over time. Both resources and tasks are heterogeneous, and servicing a task generally will change the attributes of a resource. These problems arise in #eet management, personnel training and assignment, and the remnantinventory problem. We formulate the problem as a multistage dynamic program, and suggest an approximation strategy that naturally yields integer solutions. We show experimentally that the approach provides near-optimal solutions for deterministic problems, and outperforms standard rolling-horizon methods on stochastic problems bya signi#cant margin. We consider the problem of assigning a set of reusable resources over time to tasks that arise randomly over time. Each resource is in a particular state, and each task requires a resource in a particular state. The assignment of a resource to a task generates revenue a...
Cited by 0
Gregory A. Godfrey, Warren B. Powell · Transportation Science · 2002
In a companion paper (Godfrey and Powell 2002) we introduced an adaptive dynamic programming algorithm for stochastic dynamic resource allocation problems, which arise in the context of logistics and distribution, fleet management, and other allocation problems. The method depends on estimating separable nonlinear approximations of value functions, using a dynamic programming framework. That paper considered only the case in which the time to complete an action was always a single time period. Experiments with this technique quickly showed that when the basic algorithm was applied to problems with multiperiod travel times, the results were very poor. In this paper, we illustrate why this behavior arose, and propose a modified algorithm that addresses the issue. Experimental work demonstrates that the modified algorithm works on problems with multiperiod travel times, with results that are almost as good as the original algorithm applied to single period travel times.
Cited by 86
Rare & Special e-Zone (The Hong Kong University of Science and Technology) · 1994
Cited by 0
Mohammad Ali Moradi, Sama Goliaei, Mohammad-Hadi Foroughmand-Araabi · PLoS ONE · 2019
Control problem in a biological system is the problem of finding an interventional policy for changing the state of the biological system from an undesirable state, e.g. disease, into a desirable healthy state. Boolean networks are utilized as a mathematical model for gene regulatory networks. This paper provides an algorithm to solve the control problem in Boolean networks. The proposed algorithm is implemented and applied on two biological systems: T-cell receptor network and Drosophila melanogaster network. Results show that the proposed algorithm works faster in solving the control problem over these networks, while having similar accuracy, in comparison to previous exact methods. Source code and a simple web service of the proposed algorithm is available at http://goliaei.ir/net-control/www/.
Cited by 15Open access
Ying Li · Procedia Computer Science · 2025
With the continuous development of information technology and the increasing complexity of network attacks, computer security management faces increasingly severe challenges, especially in how to optimize resource allocation and improve security protection efficiency. In order to cope with these problems, this paper introduces an optimization method based on dynamic programming algorithm to improve the effectiveness of computer security management. Firstly, a multi-level security management model is constructed. Then, the dynamic programming algorithm is applied to optimize the response sequence and resource allocation strategy of security incidents. Finally, the optimal strategies under different attack modes are designed, and the simulated annealing algorithm is used to further improve the quality of the solution. Experimental results show that this method significantly outperforms traditional strategies on multiple indicators. In terms of security incident response time, the optimization strategy shortens the response time by an average of 30%. In terms of resource utilization, the average resource utilization of the optimization strategy reaches 87.5%, which is significantly higher than the traditional strategy. In addition, in terms of security cost and risk control, the optimization strategy reduces costs by 4.7% and risks by 4.4%. The experiment verifies the effectiveness of the optimization strategy based on dynamic programming in improving response efficiency, optimizing resource allocation and reducing security risks, providing new ideas for computer security management.
Cited by 0Open access
Maher Charfi, Jalel Zrida · IEEE Transactions on Image Processing · 2011
This paper presents a novel approach to contour approximation carried out by means of the B-snake algorithm and the dynamic programming (DP) optimization technique. Using the proposed strategy for contour point search procedure, computing complexity is reduced to O(N×M(2)), whereas the standard DP method has an O(N×M(4)) complexity, with N being the number of contour sample points and M being the number of candidates in the search space. The storage requirement was also decreased from N×M(3) to N×M memory elements. Some experiments on noise corrupted synthetic image, magnetic resonance, and computer tomography medical images have shown that the proposed approach results are equivalent to those obtained by the standard DP algorithm.
Cited by 4
Noah D. Goodman · 2012
We describe a dynamic programming algo-rithm for computing the marginal distri-bution of discrete probabilistic programs. This algorithm takes a functional inter-preter for an arbitrary probabilistic program-ming language and turns it into an effi-cient marginalizer. Because direct caching of sub-distributions is impossible in the pres-ence of recursion, we build a graph of de-pendencies between sub-distributions. This factored sum-product network makes (poten-tially cyclic) dependencies between subprob-lems explicit, and corresponds to a system of equations for the marginal distribution. We solve these equations by fixed-point iteration in topological order. We illustrate this algo-rithm on examples used in teaching proba-bilistic models, computational cognitive sci-ence research, and game theory. 1
Cited by 0
Ching-Cheng Shen, Yen‐Liang Chen · European Journal of Operational Research · 2006
Cited by 10
Shan-Li Hu, Chunyi Shi · 2003
Auctions are important mechanisms for resource and task allocation in multi-agent systems. Combinatorial auctions where bidders can bid on bundles of items can lead to more economical revenue. This is a winner determination problem. But determining the winners is NP-complete. Rothkopf et al. (1998) presented a dynamic programming algorithm for this problem. It is an optimal algorithm found so far for the general case. In this paper we analyze its computational complexity exactly, prove that the computational complexity of the algorithm is /spl Theta/(3/sup n/) for n items. Compared with the result O(3/sup n/) of Rothkopf et al., it is more exact. This will help research on the approximate algorithm for the winner determination problem in combinatorial auctions, and for the optimal coalition structure generation in multi-agent systems.
Cited by 2
Kevin Y. K. Ng, N. G. F. Sancho · Automatica · 1980
Cited by 6
Geng Lin, Jinxi Han, Jianguang Jia et al. · 2025
This paper presents a task planning and resource scheduling algorithm based on a regret-driven greedy strategy and dynamic programming. The algorithm addresses key challenges such as resource conflicts between tasks, limited adaptability to dynamic task arrivals, and the trade-off between task benefits and costs. By incorporating real-time task evaluation, dynamic resource allocation and release mechanisms, and task interruption and insertion strategies, the algorithm achieves global optimization in complex and dynamic environments. The core regret mechanism allows lower-benefit tasks to release resources under constrained conditions, prioritizing higher-benefit tasks to maximize overall gains. Experimental results demonstrate that the proposed method excels in resource utilization, task completion rate, and total benefit optimization, providing a robust solution for task optimization under resource-limited scenarios.
Cited by 0
Pavlina Fragkou · ArXiv.org · 2003
In this paper we introduce a dynamic programming algorithm to perform linear text segmentation by global minimization of a segmentation cost function which consists of: (a) within-segment word similarity and (b) prior information about segment length. The evaluation of the segmentation accuracy of the algorithm on a text collection consisting of Greek texts showed that the algorithm achieves high segmentation accuracy and appears to be very innovating and promissing.
Cited by 0Open access
Xiang Song, Chengbin Chu, Yiyong Nie · ePrints Soton (University of Southampton) · 2004
In this paper, a heuristic dynamic-programming recursion is proposed for solving unconstrained 2D knapsack problem efficiently. The algorithm we propose is an incompletely enumerative method, in which some intricate cutting patterns may not be enumerated. Compared with the traditional dynamic-programming, the algorithm gives a high percentage of optimal solutions (93%) with a much lowered computational complexity. Some theoretical analyses for the algorithm are performed. Computational results are given for small and medium-sized problems.
Cited by 5
Fragkou Pavlina · 2003
In this paper we introduce a dynamic programming algorithm to perform linear text segmentation by global minimization of a segmentation cost function which consists of: (a) within-segment word similarity and (b) prior information about segment length. The evaluation of the segmentation accuracy of the algorithm on a text collection consisting of Greek texts showed that the algorithm achieves high segmentation accuracy and appears to be very innovating and promissing.
Cited by 0