Abstract: A simple algorithm for solving the knapsack problem is shown to lead to examining, on the average, around ${e^{2\sqrt n }}$ vectors out of ${2^n}$.
Abstract: A simple algorithm for solving the knapsack problem is shown to lead to examining, on the average, around ${e^{2\sqrt n }}$ vectors out of ${2^n}$.
By studying the algorithms of single pattern matching, five factors that have effect on time complexity of the algorithm are analyzed. The five factors are： sorting the characters of pattern string in an increasing o...
详细信息
By studying the algorithms of single pattern matching, five factors that have effect on time complexity of the algorithm are analyzed. The five factors are： sorting the characters of pattern string in an increasing order of using frequency, utilizing already-matched pattern suffix information, utilizing already-matched pattern prefix information, utilizing the position factor which is absorbed from quick search algorithm, and utilizing the continue-skip idea which is originally proposed by this paper. Combining all the five factors, a new single pattern matching algorithm is implemented. It＇s proven by the experiment that the efficiency of new algorithm is the best of all algorithms.
The Track-Before-Detect (TBD) algorithms allow the estimation of the state of an object, even if the signal is hidden in the background noise. The application of local cross-correlation for the modified Information Up...
详细信息
ISBN:
(纸本)9783030227340;9783030227333
The Track-Before-Detect (TBD) algorithms allow the estimation of the state of an object, even if the signal is hidden in the background noise. The application of local cross-correlation for the modified Information Update formula improves this estimation for extended objects (tens of cells in the measurement space) compared to the direct application of the Spatio-Temporal TBD (ST-TBD) algorithm. The Monte Carlo test was applied to evaluate algorithms by using a variable standard deviation of the additive Gaussian noise. The proposed solution does not require prior knowledge of the size or measured values of the object. Mean Absolute Error for the proposed algorithm is much lower, close to zero to about 0.8 standard deviation, which is not achieved for the ST-TBD.
It is shown that the proof of the main result in Reyner’s paper, similarly titled, is incorrect. Interestingly, by combining a simple modification of the algorithm with tighter analysis, one can obtain the original r...
详细信息
It is shown that the proof of the main result in Reyner’s paper, similarly titled, is incorrect. Interestingly, by combining a simple modification of the algorithm with tighter analysis, one can obtain the original result with a minor improvement.
Criteria for selection of a “best” algorithm change with technology. algorithms to generate samples from the normal probability distribution were analyzed in a technology-independent empirical Knuth type A algorithm...
详细信息
Gas pipeline will cause leakage accidents due to corrosion, aging, third-party damage and other reasons. Gas pipeline leakage will directly cause energy waste, environmental pollution and economic losses. So in the pr...
详细信息
Aiming at the problems of low efficiency, heavy quality, and high cost of traditional components, it is necessary to study a design and analysis method of non-standard components. Taking the non-standard parts-turret ...
详细信息
Aiming at the problems of low efficiency, heavy quality, and high cost of traditional components, it is necessary to study a design and analysis method of non-standard components. Taking the non-standard parts-turret loading and -unloading device as the carrier, the key parts of the non-standard parts are extracted for structural design and the multi-objective mathematical model and modal theory model are established. The optimization analysis of the key parts is carried out by genetic algorithm. Finally, the optimization results are compared and simulated by ANSYS Workbench. The results show that: in this case, the genetic algorithm optimized data with other data, the overall quality difference is 4.1%. The first six order modal values in the optimized results are in the range of 68 Hz to 130 Hz, which provides a basis for similar research in the future.
Average case algorithm analysis is usually viewed as a tough subject by students in the first courses in computer science. Traditionally, these topics are fully developed in advanced courses with a clear mathematical ...
详细信息
Average case algorithm analysis is usually viewed as a tough subject by students in the first courses in computer science. Traditionally, these topics are fully developed in advanced courses with a clear mathematical orientation. The work presented here is not an alternative to this, rather, it presents the analysis of algorithms (and average-case in particular) adapted to the mathematical background of students in an elementary course on algorithms or Programming by using two selected case-studies.
Color quantization is a process of choosing a set of K representative colors to approximate the N colors of an image, K much less than N, such that the resulting K-color image looks as much like the original N-color i...
详细信息
Color quantization is a process of choosing a set of K representative colors to approximate the N colors of an image, K much less than N, such that the resulting K-color image looks as much like the original N-color image as possible. This is an optimization problem known to be NP-complete in K. However, this paper shows that by ordering the N colors along their principal axis and partitioning the color space with respect to this ordering, the resulting constrained optimization problem can be solved in O(N + KM2) time by dynamic programming (where M is the intensity resolution of the device). Traditional color quantization algorithms recursively bipartition the color space. By using the above dynamic-programming algorithm, we can construct a globally optimal K-partition, K > 2, of a color space in the principal direction of the input data. This new partitioning strategy leads to smaller quantization error and hence better image quality. Other algorithmic issues in color quantization such as efficient statistical computations and nearest-neighbor searching are also studied. The interplay between luminance and chromaticity in color quantization with and without color dithering is investigated. Our color quantization method allows the user to choose a balance between the image smoothness and hue accuracy for a given K.
暂无评论