China
Africa
Explore chapters and articles related to this topic
Andrew Viterbi and the Viterbi algorithm
Published in Jun Wu, Rachel Wu, Yuxi Candice Wang, The Beauty of Mathematics in Computer Science, 2018
Returning to our main topic, let us take a look at the famous algorithm named after Viterbi. The Viterbi algorithm is a special but widely applied dynamic planning algorithm (see previous chapters). Dynamic planning algorithms can be used to solve the shortest path problem in any graph. The Viterbi algorithm was proposed for a specific type of directed graph, the lattice graph. It is so important because any problem that can be described using a hidden Markov model can use the Viterbi algorithm to decode. Hence, it is applied in fields including digital communications, speech recognition, machine translation, and pinyin-to-hanzi (Chinese characters) conversion. Now, we will use a familiar example, pinyin-to-hanzi conversion in Chinese input methods, to show the Viterbi algorithm.
Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems
Published in Optimization Methods and Software, 2022
Heejune Sheen, Makoto Yamashita
We first describe how to generate a QCQP for the lattice problem with the size where is a positive integer. Consider Here is the decision variable. For the coefficient matrices , a lattice graph is considered with the vertex set and the edge set Figure 1 illustrates the lattice graph with . Test instances with the lattice graph were also used in [37].
Cellular Genetic Algorithms: Understanding the Behavior of Using Neighborhoods
Published in Applied Artificial Intelligence, 2019
If we think the population of an EA in terms of graphs (Alba and Dorronsoro 2008b), being the individuals the vertices of the graph and their potential relationships the edges, a panmictic EA is a completely connected graph (see Figure 2a). On the other hand, a cEA is a lattice graph, as one individual can only interact with its nearest neighbors, for example, in Figure 2b) each individual has eight neighbors.
The robust shortest path problem for multimodal transportation considering timetable with interval data
Published in Systems Science & Control Engineering, 2018
Song Liu, Yong Peng, Qiankun Song, Yiying Zhong
This study generated a directed lattice graph with nominal travel time and cost of each arc independent. The generated graph is a lattice graph, as shown in Figure 9. Vertex 1 (upper left corner) is the departure point, and Vertex 25 (lower right corner) is the destination point. There are three transport modes, highway, railway and waterway available between two nodes. H, R and W, respectively, represent highway, railway and waterway. Because the RSPP for the multimodal transportation considering timetable with the interval data is a relatively new issue, there is no standard case library for testing. Thus, the study needs to construct test data by its own. The most generally used two methods for constructing data: one is random generation, and the other is modification based on existing instances. Due to the lack of authoritativeness and representativeness of the data that is generated randomly, the examples used in this research are modified based on the Solomon standard examples (Solomon, 1987). In Solomon's case, the data are divided into three types: C-type, R-type and RC-type. This research selects the first 25 nodes in Solomon's R101 to map the nodes in Figure 9. The Euclidean distance/90 (km/h) between nodes in Solomon's nodes indicate the average transport time by highway, Euclidean distance/60 (km/h) represents the average transport time by railway and Euclidean distance/40 (km/h) demonstrates the average transport time by waterway. The disturbance time is equal to the average transport time. Supplementary data: the transport speed, transport cost and timetables for transport mode are shown in Table 2. The transshipment time and cost between different modes of transport are shown in Table 3. Supposing that we now need to transport a batch of goods from starting node 1 to the destination 25 at 8:00, and the goods is required to carry to the destination 25 in 2000 to 4000 min. So how can we arrange the transport so that the transport cost will be the lowest.