## 3 Proposed Method
### The Generation of MTV by Improved AO* Model  
After the parameters \(\beta\) are determined, this paper will use the data of the circuit under test to judge whether the relative error of estimated value of \(\mathrm{P}_{MTV}\) calculated by the heuristic function meets the condition of the testers. If the result does not meet the condition, this paper will regenerate parameters by setting the initial values to these time results. Otherwise, this paper will use AO* model to search MTV heuristically. In order to improve the generation searching, this paper makes several improvements to the AO* model. * Set the \(P_{MTV}\) of the MTVs needed to be optimized as \(P_{min}\), which is the upper bound of the search. For the search process, the search path with \(\hat{P}_{MTV_{i}}\) bigger than \(P_{min}\) will not continue to search. * In order to avoid the influence of the multi-optimal solution problem, this paper uses adaptive method to consider both search efficiency and low \(P_{MTV}\) of the solution. This paper sets the meet-threshold \(\theta\) according to the upper bound of the search and use the depth-first strategy to search. When the ratio of \(P_{MTV}\) of a solution to \(P_{min}\) is less than or equal to \(\theta\), the algorithm ends. At the same time, this paper sets the threshold number of searches to \(c_{s}\). When cumulative number of searches reach \(c_{s}\), this paper adjusts \(\theta\) according to Equation (22). \[\theta=\frac{c_{s}+1}{c_{s}}.\theta\] (22) Based on the above improvement, the whole algorithm flow is as follows:Step 1: According to the P_MTV of the MTVs needed to be optimized, set the \(P_{min},\ \theta\) and \(c_{s}\). Step 2: Create the root node of the search tree; the root node contains all possible types of the sub-matrix \(MTV_{1}\), each of which corresponds to a search direction. Step 3: Calculate the \(f(MTV_{1})\) of each type of \(MTV_{1}\), then calculate the \(\hat{P}_{MTV_{1}}\) of each type of \(MTV_{1}\). Ban the direction of those \(MTV_{1}\) whose \(\hat{P}_{MTV_{1}}\) is bigger than \(P_{min}\). Find the \(MTV_{1}\) with least \(\hat{P}_{MTV_{1}}\) and set it as the direction to expand. Create the next node for \(MTV_{2}\), as the same model, and so on, until the node for \(MTV_{n}\) is reached. Step 4: When the number of layers of MTV corresponding to a node is \(n\), it means one search is finished and we obtain a solution. Calculate the \(P_{\text{MTV}}\) of these \(MTV_{n}\)s, find the least \(P_{\text{MTV}}\), and calculate the ratio of \(P_{\text{MTV}}\) to \(P_{min}\). If the ratio is equal to or less than \(\theta\), the algorithm ends, and the \(MTV_{n}\) with least \(P_{\text{MTV}}\) is the final solution. Otherwise, if the cumulative number of searches reaches the \(c_{s}\), this algorithm adjusts the \(\theta\) by Equation (22). Step 5: If the algorithm is not finished, trace up the parent node and change the each \(\hat{P}_{MTV_{i}}\) of \(MTV_{i}\) type to their next node's \(\hat{P}_{MTV_{i+1}}\). Find the MTV with the least \(P_{\text{MTV}}\), and set its direction as the direction needed to expand. If the direction is not changed, continue to trace up. Otherwise, this algorithm will expand in a new direction. If the search tree traces up to the root node, the algorithm ends and, according to the direction of root node, the \(MTV_{n}\) with least \(P_{\text{MTV}}\) is the final solution. The above steps can be represented by a flow diagram (Figure 6). Figure 6: The flow diagram of heuristic search using the improved AO*. The running process of traditional AO* algorithm is a backtracking search process. In the worst case, its time complexity is close to the enumerated type. For the searching of an \(n\times m\)-scale MTV, the worst time complexity is O (\(n!\)). The method of this paper introduces adaptive method and depth-first strategy, through observing the result of every \(c_{s}\) searching, the termination condition of the algorithm is adjusted adaptively. The worst time complexity of each searching is \(n\cdot(2^{m}-2)\).