JPH0546590A - Graph minimum length-path searching method and device for obtaining plurality of optimum solution - Google Patents

Abstract

PURPOSE: To provide a graph search method for discovering plural pieces of solutions of which the optimum characteristic is warranted, at a high speed. CONSTITUTION: The shortest cost between the arbitrary vertexs of a directed graph attached with the costs of the real values on the side between the vertexes and an end point t is calculated. Route development is executed sequentially toward the end point t the like a, a+1, while the low order is pruned according to set analysis conditions in accordance with the sum f(Xi) of the cumulation g(Xi) of the costs from the beginning point s and the shortest cost h(Xi) of the remaining routes with the partial routes from the beginning point s of the directed graph G. The high-order N-pieces of the optimum routes held at the point of the time when the search ends, are outputted. The shortest cost of the remaining routes is previously calculated and the development is performed for the plural routes in accordance with the analysis conditions while the cumulation of the cost from the beginning point is added thereto and, therefore, the plural characteristic and optimum characteristic of the solution are assured. In addition, the development is sequentially executed while the routes of the low-order cost values are pruned and, therefore, the high-speed characteristic of the processing is assured as well.

Description

Detailed Description of the Invention

[0001]

[Industrial applications]

The present invention relates to a graph search method for finding the shortest path of a graph, and more particularly to a graph search method effective for finding a plurality of shortest paths.

[0003]

2. Description of the Related Art The problem of finding the shortest route in terms of distance, time, and price between two points is one of graph search methods. For example, if the user of the communication line can immediately find the cheapest communication path from the point A to the point B, the second cheapest communication path, the third cheapest communication path, ... The degree of freedom in selection when using the communication line is increased. In the navigation system,
If, for example, a plurality of high-order routes regarding the required time from the current position to the destination are immediately obtained, the driver can select one of those routes while taking other conditions into consideration. Alternatively, in the field of machine translation, Japanese morphological analysis can be formulated as a shortest path problem for graphs. In that case, when there are multiple formal interpretations of a given sentence, the most likely interpretation,
It is important to seek the second most likely interpretation, ...

The best known shortest path algorithm for such a graph is Dijkst.
ra) algorithm. This algorithm computes the shortest path of an effective graph with nonnegative cost in O (elogn) time. Here, e is the number of edges of the graph, and n is the number of vertices. This algorithm is fast, but it cannot simultaneously find multiple shortest paths, that is, second, third, ... Details of the Dijkstra algorithm are described in, for example, Aho, A .; V. Other work, "Data
Structures and Algorithm
s ", pp204-208, Addison-Wesl.
ey, 1983.

On the other hand, there is a beam search as a method for obtaining a plurality of solutions at high speed. In the beam search, pruning is performed based on the cost of a partial path, so that the obtained solution is not guaranteed to be optimal. I will end up. The details of this beam search are described in Winston, P. et al. H. Other work, "Arti
financial Intelligence-Secon
d Edition ", pp-96-97, Addis
on-Wesley, 1984.

[0006] A vertical search, a horizontal search, or a best-first search can be used to find a plurality of solutions with guaranteed optimality. Since it takes time of the order of exponential function, the field of practical use is narrow, which is not desirable. The details of the best priority search are described in Bar, A. et al. Others, "The Handbook of Artifi
cial Intelligence ", Willi
Am Kaufman, 1981.

An invention aiming at a similar effect is disclosed in Japanese Patent Laid-Open No.
-48127 and Japanese Patent Laid-Open No. 63-170776, both of which control the search order using a heuristic predicted value, and either the optimality of the solution or the computational complexity Be damaged. On the other hand, in the invention of Japanese Patent Laid-Open No. 62-32516, the distance to the end point is stored in advance at each vertex. However, the minimum value is not guaranteed, and there is no method for obtaining multiple solutions. There's a problem.

[Problems to be Solved by the Invention]

Thus, conventionally, the multiplicity of solutions, the optimality,
There is no graph search method that satisfies the processing speed at the same time. It is an object of the present invention to provide a graph search method for quickly finding a plurality of solutions with guaranteed optimality.

[Means for Solving the Problems]

As an efficient method of finding the shortest path of a graph, the present invention calculates the shortest cost between an arbitrary vertex and an end point t of a directed graph with a real-valued cost on the edge between vertices, and calculates the directed graph G The partial path from the starting point s of
Based on the sum of the accumulated cost from the above and the shortest cost of the remaining route, while pruning the lower order according to the set analysis condition, the route is expanded sequentially, and is retained at the time when the search is completed. It is characterized by outputting a plurality of optimum routes. According to the present invention, the shortest cost of the remaining route is calculated in advance, the cost is accumulated from the starting point, and the route is developed for a plurality of routes according to the analysis conditions, so that the multiplicity and optimality of the solution are secured at the same time. In addition, since the paths of lower cost values are pruned and sequentially expanded, high speed processing can be ensured.

【Example】

An embodiment of the present invention will be described below. First,
First, the terms related to the shortest path are defined as follows.
Let G be a directed graph with real-valued costs with nonnegative edges. Graph G has n vertices s,
It has t, u, v, ... and edges connecting these vertices. Vertex u
The cost of the edge <u, v> from the vertex to the vertex v is represented by c [u, v]. The cost cost (p) of the route p is the total cost of the edges on p. The shortest path from vertices s to t is the one with the lowest cost among the paths from s to t. Next, we define the concept of N-shortest in order to show the top N shortest routes. The path p0 is the path from vertex s to vertex t, and cost (p) <
At most N-1 other routes p from s to t that result in cost (p0)
It is assumed that there are only individual pieces (however, N> 0). At this time, p0
Is N-shortest.

For example, if there are four routes from s to t and their costs are 4, 5, 8 and 5, then the two routes with cost 5 are both 2-shortest. The shortest path in the usual sense is equal to 1-the shortest path.

The shortest route cannot include a patrol route. However, for N> 1 N, it is possible that the N-shortest path contains a tour.

Given the graph G having n vertices, the starting point s, the ending point t, and the number N of desired routes, the algorithm of the present invention has a time complexity of O (n ² N ² log N), Output N N-shortest paths.

Here, from a certain vertex u to a vertex t as an end point
Suppose we knew the cost h (u) of the shortest path to.
Then, f (Xi) = g (Xi) + h (xi), which is the sum of the cost g (Xi) of the path that has hitherto evaluated the partial path Xi of the beam search and the lowest cost h (xi) in the future. (Figure 2). Less than,
Such route development is sequentially advanced to the vertex t and the shortest route with the highest cost to the top N (FIG. 3). Here, the child characters 1 to n are vertices at the current position a and the next position a + 1 of the partial path X. The partial path X1 for which f (X1) is the minimum is a partial path of the shortest path of the whole. Because the path through the other partial path X is at least f
This is because it is guaranteed to have a cost of (X) (> = f (X1)).

In order to give the shortest cost to the goal vertex t to each vertex of the graph G, for example, the Dijkstra method may be applied in the reverse direction starting from the goal vertex t. That is, the overall processing of the present invention is roughly divided into two steps: assigning the shortest cost to the goal vertex t to each vertex and performing beam search using the evaluation function f from the starting point s to the goal vertex t. Become.

Next, a concrete embodiment of the present invention will be described with reference to FIGS.
This will be described with reference to FIG. 11 and Table 1. First, FIG. 4 shows the overall functional configuration of the graph shortest path search device of the present invention. 1 is input means for inputting a graph to be analyzed and analysis conditions, 2 is graph holding means for storing and holding the input graph, and 3 is the shortest distance between each vertex and end point in the path of the graph. Shortest cost calculating means for calculating the cost, 4 is a route expanding means for searching the shortest route of the input graph, 5 is an analyzing path holding means for holding the path expanding result, and 6 is an analyzing path for outputting the expanding result. It is an output means. The graph search device of the present invention is a dedicated micro-processor that processes each function such as the shortest cost calculation means and the route expansion means.
Although it may be configured by a processor, memory, etc., it is stored in a general-purpose computer and its storage device (save).
It may be configured by using the created program.

FIG. 5 shows an example in which the present invention is realized by using a general-purpose computer. In the figure, a computer 11
Is provided with a processor 12, a storage device 13 and an input / output channel 14, and instructions, commands or data are mutually transferred via a bus 15. The processor 12 has an arithmetic logic unit 16 and a control unit 17. Further, the storage device 13 has a data memory unit 18 and a program memory unit 19, and the data memory unit 18 includes:
There is a graph storage area 20 as the graph holding means 2 and a route recording area 21 as the analysis path holding means 5.
The programs stored in the program memory unit 19 include a shortest cost calculation unit 22 that constitutes the shortest cost calculation unit 3 together with the processor 12 and a route expansion unit 23 that constitutes the route expansion unit 4 together with the processor 12. Two
An input / output control device 4 connects the input device 25 as the input means 1, the display device 26 as the analysis path output means 6 and the external storage device 27 to the input / output channel 14. The algorithm of the program stored in the program memory unit 19 is as shown in Table 1.

Table 1 Path Search Algorithm Graph G, start point s, end point t, and number N of solutions to be obtained are input. (1) The shortest cost h [u] to the goal is given to each vertex u by the Dijkstra method. (2) F ← {<s, 0, h [s], null>} (3) while true (4) F '← φ (5) Regarding each element of F X = <u, g, f, p> (6) if u = ver (p) = t then F '← F'∪ {X} (7) About else v ∈ out [u] (8) g' ← g + c [u, v] (9) f '← g' + h [v] (10) p '← X (11) F' ← minN (F '∪ {<v, g', f ', p'>}) (12) if F = F 'then break (13) F ← F' (14) Trace each element of F in reverse and output the solution path (15)

Next, the algorithm of Table 1 will be described in detail with reference to the flow chart of FIG. First, in step 802, the graph G, the starting point s, the ending point t, and the number N of solutions to be obtained are input (one line of the algorithm). These input values are stored in the graph storage area 2 of the data memory unit 18.
It is held at 0. Figure 6 shows how this data structure looks like.
The graph storage area has a relative address of 30 for each vertex.
At the same time, the contents 32 of the graph, that is, out [u] ... The vertex set c [u, v] of the destination of the edge coming out of the vertex u ... The cost of the edge from the vertex u to the vertex v is stored. In addition, an area for storing the shortest cost from h [u] ... vertex u to end point t is given to each vertex. Furthermore, a pointer to the list of corresponding edges is shown.

At the next step 804, from each vertex u to the end point t.
The shortest cost h [u] up to is stored in the path memory area 21 of the data memory unit 18 (row (2) of the algorithm in Table 1). The structure of the path recording area is as shown in FIG. 7, and the relative address 30 of each vertex and the content 34 of the set F of partial paths are recorded. The details will be described later.

The shortest cost h [u] is calculated by the Dijkstra method as shown in FIG. 9, for example. S is already h [u]
Is a set of confirmed vertices. For the end point t, always h
Since [u] = 0, t is the initial value of S (step 90).
2). The shortest cost h [u] is calculated by first calculating h [i] of each vertex i.
Is initialized with the cost c [i, t] of the edge from each vertex i to the end point t (step 904). Next, for each vertex i, the vertex V
Let w be the element with the smallest h [i] in S (step 9
08), add it to the set S of vertices for which h [i] has been determined (step 910), and for each element v of the vertex VS, min
(H [i], h [w] + c [v, w] is set as the shortest cost h [v] (step 912). Note that the step of inputting the number N of solutions to be obtained (step 802 of FIG. 8) is It can be after step 804 of calculating the shortest cost.

Returning to FIG. 8, steps 806 to 828.
The route expansion is being executed at. This corresponds to lines (3) to (14) of the algorithm in Table 1. First, the contents of F are initialized (step 806). F is an ordered set that stores N subpaths during the search. The elements of F are a quartet of <u, g, f, p>, where u ... current vertex g ... cost of the route so far f ... g + h (u) (this The cost of the shortest route that passes through a partial route) p ... is a set of four that represents the immediately preceding route. This quadruplet is stored in the route recording area 21 of the data memory unit 18. Therefore,
The initial value of F is such that u is the starting point s, g is zero, f is h (s), and p is nothing, that is, <s, 0, h (s), null>. Next step 8
The newly obtained F in 08 is defined as F ′, and each element of F is X =
With respect to <u, g, f, p>, the processing of step 812 and thereafter is expanded.

Ver (p) in step 812 is the previous vertex in the path. For convenience, for the end point t, c
Suppose there is an edge such that [t, t] = 0. The following processing is executed for v ∈ out [u] until the end point t is reached. Update the cost of the route so far. g ′ ← g + c [u, v] (step 816) The cost of the shortest path passing through this path is calculated. f '← g' + h [v] (step 818) A pointer to the previous path is set in preparation for outputting the analysis path later. p ′ ← X (step 820) Pruning is performed based on f. F '← min_N (F' ∪ {<v, g ', f', p '>}) (step 822) where min_N (F) is the element of F with the lowest cost N
This is a function that returns a number. In step 828, F is updated, and u = t, that is, the same processing is repeated until the end point t is reached. In step 812, when the end point t is reached, a route that passes through this side once (that is, u = ver (p) =
The route t) will not be expanded anymore. At the end of the algorithm, F contains N-the shortest maximum N solutions. F is an empty set if there is no route from the start point s to the end point t, and the number of elements may be less than N if the number of routes is less than N. However, if the number of paths from s to t is greater than N, then the number of elements in F is always N.

In step 822, min_N
Is replaced with min_E, that is, a function that returns a cost within E times the minimum cost, a plurality of cost shortest paths within E times the minimum cost path can be obtained.

Step 830 (of the algorithm of Table 1
In line (15), the immediately preceding paths are sequentially reversed from each element <t, g, f, p> of F to output the completed solution path.

Let us assume that the number N of solutions to be obtained is N = 3 and follow the execution of the algorithm with reference to FIG. It is assumed that vertex 1 is the starting point and vertex 5 is the ending point. In the first half of the algorithm of Table 1, starting from vertex 5, the Dijkstra method is applied and each vertex u is assigned a value of h [u]. An example of this result is shown in FIG. 6 as the contents of the graph storage area 20. Also, due to space limitations, the value of the fourth component p of the F element is substituted by ver (p).

In this state, the latter half of the algorithm of Table 1,
That is, the beam search is executed. This search starts at vertex 1. Therefore, the initial value of the set F of partial routes is {<1,0,60,
null>}. In the next loop, all edges from vertex 1 are expanded. Here, the destination vertex set out [1] from the vertex 1 is {2,4,5], and the edge cost c [1,2] from the vertex 1 to the vertex 2 is 10 and the vertex 1 is The cost c [1,4] of the edge from the vertex 1 to the vertex 4 is 30, and the cost c [1,5] of the edge from the vertex 1 to the vertex 5 is 100. Also, vertex 2,
The shortest cost f from the vertex 1 to the end point 5 is 70, 60, and 100, respectively, through the routes 4 and 5. Therefore, the result of the expansion is {<4,30,60,1>, <2,10,70,1>, <5,100,100,1>} (Iter2) in ascending order of the shortest cost f. Further expanding these, we obtain {<3,50,60,4>, <3,60,70,2>, <5,90,90,4>, <5,100,100,5>} (Iter3). The states of Iter 1-3 are recorded in the graph storage area 20 as shown in FIG. This Ite
Since the state of r3 exceeds the number of solutions to be sought N = 3, the lower <5,100,100,5> is discarded, and the higher 3
One is left. In the next loop, we get {<5,60,60,3>, <5,70,70,3>, <5,90,90,5>} (Iter3), but they all reach the end point Since it is the route that was done, the algorithm ends. The actual solution is obtained by tracing the previous vertex p in reverse from here, and they are 1st place 1 → 4 → 3 → 5 (cost = 60) 2nd place 1 → 2 → 3 → 5 (cost = 70) 3rd place 1 → 4 → 5 (cost = 90).

As described above, according to the present invention, the shortest N paths can be obtained by the combination of the Dijkstra method and the beam search. If only Dijkstra's method is used, as mentioned earlier, the first route can be obtained,
It is not possible to obtain multiple optimal routes. On the other hand, the beam search alone cannot obtain the optimum solution. This will be described with reference to FIG. The figure shows a state in which the beam search has advanced k steps. The partial route Xi is sorted by the sum g (Xi) of the costs of the sides traced from the initial state, and the top N of them are retained. However, it is not guaranteed that the best partial path X1 here is the shortest as a whole. This is because the cost from X1 to the end point t may deteriorate rapidly and other routes may emerge as better solutions.

Table 2 shows a summary of the comparison between the present invention described above and the conventional example.

Next, an example in which the present invention is applied to Japanese morphological analysis will be described. It is known that so-called morphological analysis, which cuts out clauses and word boundaries from a solid Japanese sentence, can be described very well in the range of regular grammar (type 3 grammar). Here, it is assumed that the eligibility of analysis is given by the sum of cost functions according to the frequency of occurrence of words. An analysis result with a small cost is a more qualified analysis result. With this assumption, the problem of finding the optimum solution for morphological analysis can be reduced to the shortest path problem of the graph. For example, if you analyze the compound noun "North Atlantic", "North""Great""West""West""Hokkaido""Onishi""West""Atlantic" are all correct nouns or proper nouns or affixes. (For example, "Hokkaido" means Hokkaido University, "Onishi" means a person's name, etc.), North / Large / West / West North / Large / West North / Large West / West Hokkaido University / West / West Hokkaido Univ./West North / Atlantic, Six interpretations are possible grammatically. When the result of applying the regular grammar to the input string is expanded into a trellis, and this is represented by a graph as shown in FIG. 13, and each side is given a cost based on the word frequency information as shown in the figure, the higher rank is obtained. The technique of the present invention can be used to obtain an N-position interpretation.

In the case of Japanese morphological analysis, since the graph is an acyclic graph that does not include a closed cycle, if the topological order of the vertices of the graph is used, the shortest cost calculation with the end point and the route expansion can be executed at higher speed. it can. The topological order of an acyclic graph means that if there is an edge u → v, u <
v is the ordering, and s <in FIG.
v1 <v2 <v3 <t is the topological order of this graph. Therefore, the shortest cost calculation (step 804 in FIG. 8)
For, the algorithm as shown in FIG. 14 can be used. That is, the graph G is arranged in a topological order (1402), and the cost c [i, of the edge from each vertex i to the end point t is
Let t] be the initial value of the shortest cost h [i] from the vertex i to the end point t (step 1404), and take each vertex u in the reverse topological order, and for v ∈ out [u], min (h [v], h [u] ＋ c
Let [v, u] be the shortest cost h [u] (step 1408).
In this example, the top three are North / Atlantic (cost 0.5) North Atlantic / West (cost 0.6) North / Atlantic (cost 0.7).

Note that the pruning condition is not the top N but
Find all the solutions whose cost difference from the best solution is within a certain condition by appropriately setting the analysis conditions such that the error from the shortest route is within a certain value or within a certain scale factor from the shortest route. You can also

The present invention can also be applied to the same graph in which the starting point s and the ending point t of the graph or the number N of solutions to be obtained are changed and repeatedly analyzed and output. In such a case, create a database for the graph G and its cost in advance, and repeat the same graph G data by inputting the start point s, the end point t, or the changed value of the analysis condition N in a later step. You can also use it.

From this point of view, the present invention searches and displays the shortest route from the current position of the automobile to the destination position.
Regarding an example applied to an in-vehicle navigation system,
This will be described with reference to FIGS. In FIG. 15, first, road network information as a graph is input (1502).
~ 1504). As shown in FIG. 16, the road network information includes city names A1 to A1 in a specific area, for example, all over Japan.
Costs such as An and the distance between cities or required time c [v,
u] is added. The cost is strictly
Since there is no symmetry, for example, one-way traffic, slopes, etc., the required time between cities may differ depending on the direction.
When the difference due to the direction is small, that is, when there is substantially symmetry, the cost, c [v, u] = c [u, v] can be set to simplify the subsequent calculation. Next, a certain city Ai is the s vertex,
The other cities are set as goal vertices t, and the Dijkstra method is applied in the reverse direction starting from the goal vertices t to calculate the shortest cost hi [u] between the city Ai and each of the other cities. Note that the Dijkstra method is applied in the backward direction from s vertex (city Ai) to vertex t
For the cost c [v, u] in the direction toward (other cities),
It goes without saying that the cost is calculated in the opposite direction. Hereinafter, similar processing is performed with all cities as s vertices (1506 to 1508).

For the calculation of the shortest cost, instead of the above-mentioned Tykstra method, Floyd-Marshall is used.
Method and All-pair Sho such as Jhonson method
The rtest Algorithm may be used. The shortest cost is calculated in advance to find the shortest cost hi [u] between all input cities, and the graph storage area 20
, And the above steps (1502 to 1508) may be omitted, whereby the processing time for route search can be greatly reduced. FIG. 17 shows an example of the shortest cost table between cities, and the shortest cost hi [u] among all the cities A1 to An is tabulated. If this shortest cost is symmetric, then only the triangular matrix in the upper half of the table need be stored. In addition, a plurality of types of tables having different costs such as time and distance may be prepared to give the user a degree of freedom in selection. These shortest cost tables are stored in the data memory 18 (FIG. 5) of the storage device 13 together with the road network information.

Next, the user inputs the two arbitrary cities, the start point and the finish point (step 1).
510-1512). Also, the search condition, for example, the shortest route to the top N is received (step 1514).
~ 1516). In either case, if there is no change in the input, proceed directly to the next step. After that, a beam search is performed (step 1518) and the solution path is output (step 1520). FIG. 18 shows an output example of the analysis result.

In addition to the above, the present invention can be widely applied to fields in which it is necessary to obtain a plurality of optimum solutions, such as character recognition, search for communication paths and robot movement paths.

[0038]

As described above, according to the present invention, with respect to an arbitrary directed graph having a non-negative cost, it is possible to quickly obtain a plurality of solutions of which optimality is guaranteed among the paths from the start point to the end point. Since the shortest path problem is one of the most basic network problems, it has a wide range of applications and its industrial advantages are great.

[Brief description of drawings]

FIG. 1 is a diagram illustrating definitions of terms related to a shortest path of a graph according to the present invention.

FIG. 2 shows the principle of the present invention and shows the state of route expansion of a graph at the current position a.

FIG. 3 shows the state of route expansion of the graph at the next step of FIG. 2, the current position a + 1.

FIG. 4 shows an overall functional configuration of the graph shortest path search device of the present invention.

FIG. 5 shows an example in which the graph shortest path search device of the present invention is configured using a general-purpose computer.

6 shows an example of the data structure of the graph storage area of FIG.

7 shows an example of a data structure of a route recording area 21 of FIG.

FIG. 8 is a flow chart showing details of a route search algorithm.

FIG. 9 is a flow chart when the shortest cost h [u] in FIG. 8 is calculated by the Dijkstra method.

FIG. 10 is a diagram illustrating an example of executing the algorithm of FIG.

11 is a diagram showing a situation of route expansion of FIG.

FIG. 12 is a diagram illustrating a problem of a beam search of a conventional example.

FIG. 13 is a diagram illustrating an example in which the present invention is applied to Japanese morphological analysis.

FIG. 14 is a diagram showing an example of steps of calculating the shortest cost in FIG.

FIG. 15 is a flow chart of an example in which the present invention is applied to a vehicle-mounted navigation system.

16 is a diagram showing an example of road network information as a graph in FIG.

17 is a diagram showing an example of a table of the shortest costs hi [u] among all the cities 1 to n in FIG.

FIG. 18 is a diagram showing an output example of the unraveling path according to the example of FIG. 15;

[Explanation of symbols]

 1 ... Input means 2 ... Graph holding means 3 ... Shortest cost calculation means 4 ... Route expansion means 5 ... Analysis path holding means 6 ... Analysis path output means out [u] .. . The set of destination vertices of the edge that comes from vertex u c [u, v] ... the cost of the edge from vertex u to vertex v h [u] ... the shortest cost from vertex u to endpoint t

Claims (17)

[Claims] 1. A graph search method for searching and outputting a path for a given graph by a graph search device comprising an input means, an arithmetic processing means, a storage means and an output means, wherein the input means is used to connect between vertices. A directed graph G with real-valued costs on the edges, a graph input step that gives two specific vertices as the start point s and end point t, and a condition setting step that inputs conditions for analyzing multiple routes, A graph holding step of storing the digraph G in the storage means, a shortest cost calculation step of calculating the shortest cost of any node and the end point t of the digraph G by the arithmetic processing means, and the arithmetic processing means, The partial path from the starting point s of the directed graph G, based on the sum of the accumulated cost from the starting point s and the shortest cost of the remaining paths, A route expansion step of sequentially expanding the lower routes according to the setting conditions, a partial route holding step of holding the plurality of expanded partial routes in the storage means, and a search ending A graph search method comprising: a solution path output step of outputting the plurality of partial paths held in the storage means at the time point to the output means. 2. The graph search method according to claim 1, wherein in the shortest cost calculating step, the Dijkstra method is applied in a reverse direction to calculate the shortest cost to the end point t of each vertex. .. 3. The shortest cost calculating step, wherein the directed graph G is arranged in a topological order, and the shortest cost to each goal vertex of each vertex is obtained by an acyclic graph analysis method. 1. The graph search method described in 1. 4. The setting condition is to obtain a route having a cost within N rank of the shortest cost, and in the route expanding step, a partial route from the starting point s of the digraph G is a cost from the starting point s. The graph search method according to claim 1, further comprising: pruning the routes lower than the Nth position based on the sum of the accumulation of the above and the shortest cost of the remaining routes, and sequentially expanding. 5. The setting condition is to obtain a route having a cost up to E times the shortest cost from the start point s to the end point t. In the route expanding step, the route from the start point s of the directed graph G is calculated. Sequentially pruning a plurality of partial routes while pruning the sum of the accumulated cost from the starting point s and the shortest cost of the remaining routes being larger than E times the shortest cost from the starting point s to the end point t. The graph search method according to claim 1, wherein the graph search method according to claim 1. 6. The graph search method according to claim 1, wherein, in the graph input step, a starting point s and an ending point t in the directed graph G are variable values. 7. The directed graph G is a trellis of a sentence whose morphemes are to be analyzed, and in the graph input step, the trellis and two specific vertices therein are given as a start point s and an end point t, and the shortest cost In the calculating step, the shortest cost between any node of the trellis and the end point t is calculated, and in the route expanding step, the accumulated cost from the starting point s and the sum of the shortest cost of the remaining routes are used. The graph search method according to claim 1, wherein a beam search is performed on the trellis from the head to find a plurality of optimum morpheme solutions for the given sentence. 8. A graph search method for searching and outputting a path for a given graph by a graph search device comprising an input means, an arithmetic processing means, a storage means and an output means, wherein the input means is used to connect between vertices. A graph input step of inputting a directed graph G with a real-valued cost on an edge, a graph holding step of storing the directed graph G in the storage means, and a shortest distance between all vertices of the directed graph G by the arithmetic processing means. A shortest cost calculating step of calculating a cost, a shortest cost holding step of storing the shortest cost in the storage means, and giving two specific vertices among the vertices as a start point s and an end point t, and analyzing a plurality of routes A condition setting step of inputting a condition for, and the start point s of the digraph G by the arithmetic processing means.
Based on the sum of the accumulated cost from the starting point s and the shortest cost of the remaining route, while sequentially pruning the lower route according to the setting conditions, the route expansion step And a partial path holding step for holding the plurality of expanded partial paths in the storage means, and outputting the plurality of partial paths held in the storage means to the output means when the search is completed. A graph search method, comprising: 9. A graph search method for searching and outputting a path for a given graph by a graph search device comprising an input means, an arithmetic processing means, a storage means and an output means, wherein a real-valued value is present on edges between vertices. A graph holding step of storing the directed graph G with costs and the shortest cost between all vertices of the directed graph G in the storage means, and giving two specific vertices among the vertices as a start point s and an end point t, and A condition setting step of inputting a condition for analyzing a route, the arithmetic processing means, the starting point s of the directed graph G.
Based on the sum of the accumulated cost from the starting point s and the shortest cost of the remaining route, while sequentially pruning the lower route according to the setting conditions, the route expansion step And a partial path holding step for holding the plurality of expanded partial paths in the storage means, and outputting the plurality of partial paths held in the storage means to the output means when the search is completed. A graph search method, comprising: 10. The graph search device is a navigation system, the directed graph G is road network information, and in the route expanding step, the accumulated cost from the start point s and the shortest cost of the remaining routes are set. The graph search method according to claim 9, wherein a beam search is performed from the head of the road network information using a sum of and to obtain a plurality of shortest routes. 11. A directed graph G having real-valued costs on edges between vertices, input means for giving a path expansion condition, graph holding means for storing the directed graph G, and arbitrary nodes and end points of the directed graph G. Shortest cost calculating means for calculating the shortest cost with t, the partial path from the starting point s of the directed graph G based on the condition input via the input means, the accumulation of costs from the starting point s, and the calculated Based on the sum of the shortest cost of the remaining routes and pruning the lower routes according to the above-mentioned setting conditions, route expanding means for sequentially expanding, and a part for holding a plurality of expanded partial routes A graph search device comprising: route holding means; and solution route output means for outputting the partial route held in the partial route holding means when the search is completed. .. 12. The directed graph G is provided by the path expanding means.
Based on the sum of the accumulated cost from the starting point s and the shortest cost of the remaining routes, the maximum N number of partial routes from the starting point s are sequentially pruned while pruning the routes lower than the Nth position. The graph search device according to claim 11, wherein the graph search device is developed. 13. The graph search device is a computer including a processor and a memory, and the shortest cost calculation means and the route expansion means are held in the memory in a save program format and executed by the processor. The graph search device according to claim 11, wherein the graph holding unit and the partial path holding unit are formed in a specific area of the memory. 14. A directed graph G having a real-valued cost on an edge between vertices, an input means for giving a path expansion condition, a graph holding means for storing the directed graph G, and an arbitrary vertex of the directed graph G. Shortest cost calculating means for calculating the shortest cost with the terminal vertex t, the partial path from the starting vertex s of the directed graph G based on the condition input via the input means, the accumulation of costs from the starting point s, Based on the calculated sum of the shortest costs of the remaining routes, a route expanding unit that sequentially expands while pruning lower routes according to the setting condition, and a plurality of parts expanded by the route expanding unit A partial path holding means for holding the path, and a solution path output means for outputting the plurality of partial paths held by the partial path holding means. Graph search device. 15. The directed graph G is a trellis of a sentence whose morphemes are to be analyzed, and the input means gives the trellis and two specific vertices thereof as a starting point s and an ending point t, and the shortest cost calculating means. By calculating the shortest cost of any vertex of the trellis and the end point t, the route expansion means, by using the sum of the accumulated cost from the start point s, and the shortest cost of the remaining route, the trellis 15. The graph search device according to claim 14, wherein a beam search is performed from the head to find a plurality of optimum morpheme solutions for the given sentence. 16. A graph search device having input means, arithmetic processing means, storage means, and output means for searching a path for a given graph and outputting the same, wherein a real-valued value is present on an edge between vertices. A graph holding means for storing the directed graph G with costs and the shortest cost between all the vertices of the directed graph G in the storage means, and giving two specific vertices among the vertices as a start point s and an end point t, and By the condition setting means for giving a condition for analyzing the path, the start point s of the directed graph G by the arithmetic processing means.
A route expansion means for sequentially expanding the partial routes from the start route s while pruning lower routes according to the setting condition based on the sum of the accumulated cost from the starting point s and the shortest cost of the remaining routes. A partial path holding means for holding the plurality of expanded partial paths in the storage means, and a solution path output means for outputting the plurality of partial paths held in the storage means to the output means A graph search device comprising: 17. The graph search device is a navigation system, the directed graph G is road network information, and the route expansion means accumulates costs from the start point s and the shortest cost of the remaining routes. 17. The beam search is performed from the head of the road network information by using the sum of and to obtain a plurality of shortest routes for the given sentence, and the route is output by a solution route output means. Graph search device.