CN116319518B

CN116319518B - Information acquisition method and device based on shortest path of knowledge graph

Info

Publication number: CN116319518B
Application number: CN202211058393.2A
Authority: CN
Inventors: 王举范
Original assignee: Individual
Current assignee: Individual
Priority date: 2022-08-31
Filing date: 2022-08-31
Publication date: 2024-02-20
Anticipated expiration: 2042-08-31
Also published as: WO2024046013A1; CN116319518A

Abstract

The invention provides an information acquisition method and device based on a shortest path of a knowledge graph, wherein the method comprises the following steps: according to the shortest path searching strategy and the nodes in the user request, initially setting an iteration starting point and determining the shortest path; forming a first node set by taking the nodes with the determined shortest paths and adjacent nodes with undetermined shortest paths as first nodes, selecting the adjacent nodes closest to the iteration starting point from the adjacent nodes with undetermined shortest paths of the first nodes in the first node set to determine the shortest paths, and updating the first node set; repeating the steps until all expected shortest paths are found, wherein the expected shortest paths are related to a shortest path searching strategy; and acquiring information from the knowledge graph according to the shortest path of each node and responding to the user request according to the acquired information. The shortest path of one or more nodes can be calculated in each iteration, and the shortest path of other nodes can be approximated stably.

Description

Information acquisition method and device based on shortest path of knowledge graph

Technical Field

The present disclosure relates to the field of computers, and in particular, to a method and an apparatus for obtaining information based on a shortest path of a knowledge graph.

Background

The knowledge graph uses a graph model to describe knowledge, models association relations among things, and uses organization principles to enable a user or a computer system to conduct knowledge reasoning according to the underlying data.

The nodes in the knowledge graph correspond to the entities, and the directed edges correspond to the relationships among the entities. The entities are connected with each other through the relationship, and understanding the relationship between the entities is the basis of knowledge graph analysis. After the entity relationship is quantitatively measured, the closeness degree of the relationship between the entities can be calculated by using a shortest path algorithm to obtain a shortest path tree or a shortest path, so that the relationship between the entities can be understood more intuitively and deeply, and high-quality data can be provided for insight and discovery of hidden facts and rules.

The shortest path algorithm commonly used for knowledge graph mining information in the prior art is mainly based on a Dijkstra algorithm based on relaxation operation.

In Dijkstra algorithm, let S be the node set where the shortest path has been found, and Q be the node set where the shortest path has not been found. The Dijkstra algorithm aims at minimizing the weight value of a path for a node u recently added into S, and examines each node v which is connected with u and is not in S, namely, when dist [ u ] +length (u, v) < dist [ v ], the weight value dist [ v ] of v is replaced by dist [ u ] +length (u, v), and the path precursor pre [ v ] of v points to u. Based on this, the Dijkstra algorithm has the following drawbacks:

(1) The Dijkstra algorithm uses a relaxation operation to continuously select paths with smaller weight values among a plurality of paths for nodes in Q, and repeatedly updates path information of some nodes in Q, which is specifically expressed in the following steps: the path information of the nodes in Q may be updated between iterations; the degree of perturbation to dist in each iteration is positively correlated with the degree of departure of u. The above two points result in a significant increase in maintenance costs for the newly generated u in Q.

(2) The adjacent edge of the node u needs a lot of condition judgment, and the arithmetic logic unit of the CPU is seriously depended on, so that the efficiency of running the shortest path algorithm of the computer system can not be improved by using parallel computing.

Disclosure of Invention

The method and the device are used for solving the problem that the calculation efficiency is low in the shortest path determining process based on the knowledge graph in the prior art.

In order to solve the above technical problem, an aspect of the present disclosure provides an information obtaining method based on a shortest path of a knowledge graph, where the knowledge graph includes a plurality of nodes and adjacent edges between nodes, and weights of the adjacent edges between nodes represent distances between nodes, the method includes:

s11, according to the shortest path searching strategy and the nodes in the user request, initially setting an iteration starting point and determining the shortest path;

S12, forming a first node set by taking the nodes with the determined shortest paths and adjacent nodes with undetermined shortest paths as first nodes, selecting the adjacent nodes closest to the iteration starting point from the adjacent nodes with undetermined shortest paths of the first nodes in the first node set to determine the shortest paths, and updating the first node set and the determined path lengths of the newly added first nodes;

s13, repeating the step S12 until all expected shortest paths are found, wherein the expected shortest paths are related to a shortest path searching strategy;

s14, acquiring information from the knowledge graph according to the shortest path of each node and responding to the user request according to the acquired information.

In another aspect, a shortest path determining apparatus for a knowledge graph is provided, where the knowledge graph includes a plurality of nodes and adjacent edges between nodes, and weights of adjacent edges between nodes represent distances between nodes, the apparatus includes:

the initialization unit is used for searching nodes in the strategy and the user request according to the shortest path, initially setting an iteration starting point and determining the shortest path;

a shortest path determining unit, configured to form a first node set by using, as a first node, a node having a determined shortest path and having adjacent nodes not having determined shortest paths, select, from among adjacent nodes having not determined shortest paths of the first node in the first node set, an adjacent node closest to an iteration start point to determine a shortest path, and update the first node set;

The circulation control unit is used for repeatedly starting the shortest path determining unit until all expected shortest paths are found, wherein the expected shortest paths are related to a shortest path searching strategy;

and the information acquisition unit is used for acquiring information from the knowledge graph according to the shortest path of each node and responding to the user request according to the acquired information.

The above two embodiments can enable the shortest path of one or more nodes to be calculated in each iteration and stably approach the shortest path of other nodes by avoiding the use of a relaxation operation and determining the shortest path by selecting the adjacent node nearest to the iteration start (denoted as a small-step algorithm). The number of adjacent edges of the nodes does not directly influence the time complexity, and the determination efficiency of the shortest path can be improved.

In another aspect, a method for determining a shortest path of a knowledge graph is provided, the knowledge graph includes a plurality of nodes and adjacent edges between the nodes, and weights of the adjacent edges between the nodes represent distances between the nodes, the method includes:

s21, according to a shortest path searching strategy and a source node and a target node in a user request, an iteration starting point and an edge node are initially set, wherein the edge node comprises a first node centralized node of adjacent nodes with the determined shortest paths and undetermined shortest paths, a node to be selected of undetermined shortest paths which can be added into the first node centralized node, and a node in a relaxation operation centralized node which obtains paths through relaxation operation but does not determine the shortest paths; initially setting a first node set to comprise an iteration starting point and determining the shortest path of the first node set, wherein a node set to be selected and a relaxation operation set are empty; initially setting the determined path length of the iteration start point to be zero, and the determined path lengths of the rest nodes to be infinity;

S22, calculating the heuristic path length of the edge node, wherein the heuristic path length of the edge node is the path length from the iteration starting point to the iteration ending point through the edge node;

s23, according to the heuristic path length and the determined path length of the edge nodes, screening out a node pB with the minimum determined path length from the nodes with the maximum heuristic path length from a first node set and a node set to be selected, and screening out a node pA with the maximum determined path length from the nodes with the minimum heuristic path length from a relaxation operation set;

s24, if the relaxation operation set is empty or the heuristic path length of the node pB is smaller than the heuristic path length of the node pA, or the heuristic path length of the node pB is equal to the heuristic path length of the node pA and the determined path length of the node pB is larger than or equal to the determined path length of the node pA, executing the following small-step algorithm: selecting an adjacent node closest to the iteration starting point from adjacent nodes of the first node in the first node set, which are not determined to be the shortest path, determining the shortest path, and updating the determined path lengths of the first node set and the newly added first node;

otherwise, calculating paths of all neighboring nodes of node pA in the set of relaxation operations based on the relaxation operations and updating the determined path lengths of the set of relaxation operations and the newly added relaxation node;

S25, screening excellent nodes from the relaxation operation set, and moving the excellent nodes to a node set to be selected, wherein the excellent nodes are nodes pA2 with the maximum determined path length in the nodes with the minimum heuristic path length in the relaxation operation set;

when the number of nodes in the first node set and the node set to be selected is larger than a second preset value, nodes which are screened out from the first node set and the node set to be selected and exceed the second preset value are moved to a relaxation operation set;

s26, repeating the processes from the step S22 to the step S25 until the shortest path from the source node to the target node is found and the heuristic path lengths of the edge nodes are all larger than the lengths of the shortest paths from the source node to the target node;

s27, acquiring information from the knowledge graph according to the shortest path of each node and responding to the user request according to the acquired information.

In another aspect, a shortest path determining apparatus for a knowledge graph is provided, where the knowledge graph includes a plurality of nodes and adjacent edges between nodes, and weights of adjacent edges between nodes represent distances between nodes, and the apparatus includes:

an initialization unit, configured to initially set an iteration start point and an edge node according to a shortest path searching policy and a source node and a target node in a user request, where the edge node includes a first node set node having a determined shortest path and having an adjacent node of an undetermined shortest path, a node in the node set to be selected of the undetermined shortest path that can join the first node set, and a node in the relaxation operation set that obtains a path through a relaxation operation but does not determine the shortest path; initially setting a first node set to comprise an iteration starting point and determining the shortest path of the first node set, wherein a node set to be selected and a relaxation operation set are empty; initially setting the determined path length of the iteration start point to be zero, and the determined path lengths of the rest nodes to be infinity;

The computing unit is used for computing the heuristic path length of the edge node, wherein the heuristic path length of the edge node is the path length from the iteration starting point to the iteration end point through the edge node;

the screening unit is used for screening the node pB with the minimum determined path length from the nodes with the maximum heuristic path length from the first node set and the node set to be selected according to the determined path length of the heuristic path length and the edge nodes, and screening the node pA with the maximum determined path length from the nodes with the minimum heuristic path length from the relaxation operation set;

an algorithm selection unit, configured to execute the following small-step algorithm if the relaxation operation set is null or the heuristic path length of the node pB is smaller than the heuristic path length of the node pA, or the heuristic path length of the node pB is equal to the heuristic path length of the node pA and the determined path length of the node pB is greater than or equal to the determined path length of the node pA: selecting an adjacent node closest to the iteration starting point from adjacent nodes of the first node in the first node set, which are not determined to be the shortest path, determining the shortest path, and updating the determined path lengths of the first node set and the newly added first node;

otherwise, calculating paths of all adjacent nodes of the node pA in the set of relaxed operations based on relaxed operations and updating the set of relaxed operations;

The node moving unit is used for screening out excellent nodes from the relaxation operation set and moving the excellent nodes to the node set to be selected, wherein the excellent nodes are nodes pA2 with the maximum determined path length in the nodes with the minimum heuristic path length in the relaxation operation set;

the circulation control unit is used for repeatedly starting the calculation unit, the screening unit, the algorithm selection unit and the node moving unit until the shortest path from the source node to the target node is found and the heuristic path length of the edge node is larger than the shortest path length from the source node to the target node;

According to the two embodiments, the heuristic information is used as the target guide information to combine the small-step algorithm with the relaxation operation algorithm, so that searching blindness caused by no knowledge of the iteration end point in the searching process of the small-step algorithm can be reduced, excellent nodes are screened out through the relaxation operation and used as candidate nodes of the first node in the small-step algorithm, the searching range of the small-step algorithm can be reduced, and the shortest path from the iteration start point to the iteration end point can be obtained more rapidly.

In another aspect, a computer device is provided herein, including a memory, a processor, and a computer program stored on the memory and executable on the processor, the processor implementing the method of the previous embodiments when the computer program is executed by the processor.

Yet another aspect herein provides a computer storage medium having stored thereon a computer program which, when executed by a processor of a computer device, performs instructions of a method according to the previous embodiments.

The foregoing and other objects, features and advantages will be apparent from the following more particular description of preferred embodiments, as illustrated in the accompanying drawings.

Drawings

In order to more clearly illustrate the embodiments herein or the technical solutions in the prior art, the drawings that are required in the embodiments or the description of the prior art will be briefly described below, it being obvious that the drawings in the following description are only some embodiments herein and that other drawings may be obtained according to these drawings without inventive effort to a person skilled in the art.

FIG. 1 illustrates a first flow chart of a knowledge-graph shortest path-based information acquisition method of embodiments herein;

FIG. 2 illustrates a first flow chart of a process for selecting a nearest neighbor node to an iteration start to determine a shortest path and updating a first set of nodes in accordance with embodiments herein;

FIG. 3 is a schematic diagram of a knowledge-graph extraction graph according to an embodiment herein;

FIG. 4 shows a second flowchart of a knowledge-graph shortest path-based information acquisition method of embodiments herein;

FIG. 5 illustrates a second flowchart of a process for determining a shortest path and updating a first set of nodes by selecting a neighboring node closest to an iteration start in accordance with an embodiment herein;

FIG. 6 illustrates a schematic diagram of another knowledge-graph extraction graph in accordance with an embodiment herein;

fig. 7 is a diagram showing a structure of an information acquisition apparatus based on a shortest path of a knowledge graph according to an embodiment herein;

fig. 8 is a diagram showing another configuration of an information acquisition apparatus based on a shortest path of a knowledge-graph according to an embodiment herein;

fig. 9 shows a block diagram of a computer device of embodiments herein.

Description of the drawings:

701. an initializing unit;

702. a shortest path determining unit;

703. a circulation control unit;

704. an information acquisition unit;

801. an initializing unit;

802. a calculation unit;

803. a screening unit;

804. an algorithm selection unit;

805. a node moving unit;

806. A circulation control unit;

807. an information acquisition unit;

902. a computer device;

904. a processor;

906. a memory;

908. a driving mechanism;

910. an input/output module;

912. an input device;

914. an output device;

916. a presentation device;

918. a graphical user interface;

920. a network interface;

922. a communication link;

924. a communication bus.

Detailed Description

The following description of the embodiments of the present disclosure will be made clearly and fully with reference to the accompanying drawings, in which it is evident that the embodiments described are only some, but not all embodiments of the disclosure. All other embodiments, based on the embodiments herein, which a person of ordinary skill in the art would obtain without undue burden, are within the scope of protection herein.

It should be noted that the terms "first," "second," and the like in the description and claims herein and in the foregoing figures are used for distinguishing between similar objects and not necessarily for describing a particular sequential or chronological order. It is to be understood that the data so used may be interchanged where appropriate such that the embodiments described herein may be capable of operation in sequences other than those illustrated or described herein. Furthermore, the terms "comprises," "comprising," and "having," and any variations thereof, are intended to cover a non-exclusive inclusion, such that a process, method, apparatus, article, or device that comprises a list of steps or elements is not necessarily limited to those steps or elements expressly listed or inherent to such process, method, article, or device.

The present specification provides method operational steps as described in the examples or flowcharts, but may include more or fewer operational steps based on conventional or non-inventive labor. The order of steps recited in the embodiments is merely one way of performing the order of steps and does not represent a unique order of execution. When a system or apparatus product in practice is executed, it may be executed sequentially or in parallel according to the method shown in the embodiments or the drawings.

The knowledge graph can efficiently organize, manage and utilize mass information, and has wide application in various fields such as social networks, human resources and recruitment, finance, insurance, retail, advertising, communication, IT, manufacturing industry, media, medical treatment, electronic commerce, logistics and the like. Specifically, for example, the knowledge graph can realize the conversion of Web from webpage links to concept links (supporting retrieval by topic), and truly realize semantic retrieval. For another example, a knowledge graph based search engine can graphically feed back structured knowledge to a user, who can accurately locate and deeply obtain knowledge without having to browse a large number of web pages.

The information acquisition method and device based on the shortest path of the knowledge graph can be applied to various fields for information acquisition based on the shortest path of the knowledge graph, such as information retrieval and path planning (including robot navigation, vehicle navigation and the like), and the specific application fields of the information acquisition method and device based on the shortest path of the knowledge graph are not limited.

The knowledge graph comprises a plurality of nodes and adjacent edges among the nodes, and the weight of the adjacent edges among the nodes represents the length distance among the nodes. The specific content included in the knowledge graph depends on the application field. The length distance between nodes is an abstract concept, and represents the cost, time and the like of transferring or acquiring information between nodes.

In an embodiment herein, an information obtaining method based on a shortest path of a knowledge graph is provided, which is used for solving a problem of low calculation efficiency in a shortest path determining process based on the knowledge graph in the prior art, specifically, as shown in fig. 1, the information obtaining method based on the shortest path of the knowledge graph includes:

step S11, according to the shortest path searching strategy and the nodes in the user request, an iteration starting point is initially set and the shortest path is determined.

And S12, forming a first node set by taking the nodes with the determined shortest paths and adjacent nodes with undetermined shortest paths as first nodes, selecting the adjacent nodes closest to the iteration starting point from the adjacent nodes with undetermined shortest paths of the first nodes in the first node set to determine the shortest paths, and updating the first node set.

Step S13, repeating the step S12 until all expected shortest paths are found, wherein the expected shortest paths are related to a shortest path searching strategy.

And step S14, acquiring information from the knowledge graph according to the shortest path of each node and responding to the user request according to the acquired information.

The embodiment can be applied to a client or a server, knowledge graph information (nodes and connection relations among the nodes, nodes reflect entities, and connection relations among the nodes reflect association relations among the nodes) is stored in the client or the server, and information obtained from the knowledge graph is displayed on the client. The clients described herein include, but are not limited to, computer devices, mobile terminals, etc., and may also be software installed on computer devices, mobile terminals, etc.

The present embodiment can enable the shortest path of one or more nodes to be calculated in each iteration and stably approach the shortest path of other nodes by avoiding the use of a relaxation operation and determining the shortest path by selecting the adjacent node closest to the iteration start point each time (denoted as a small-step algorithm). The number of adjacent edges of the nodes does not directly influence the time complexity, and the determination efficiency of the shortest path can be improved.

Before implementing this embodiment, the user needs to operate the client to receive a user request, where the user request includes at least the start node, so that the information related to the start node is mined through steps S11 to S14.

In step S11, the shortest path searching strategy at least includes single source searching, single source single target forward searching, single source single target reverse searching, single source single target bidirectional searching, and the process of initially setting the iteration starting point includes:

(1) If the shortest path searching strategy is single-source searching, setting a source node in the user request as an iteration starting point, and executing step S12 and step S13 from the source node, wherein the determining condition of all expected shortest paths is that all nodes with determined shortest paths have adjacent nodes without determined shortest paths.

(2) If the shortest path searching strategy is single-source single-target forward searching, setting a source node in the user request as an iteration starting point, and executing step S12 and step S13 according to the forward searching direction from the source node to the target node.

(3) If the shortest path searching strategy is single-source single-target reverse searching, setting a target node in the user request as an iteration starting point, and executing the step S12 and the step S13 according to the reverse searching direction from the source node to the target node.

(4) If the shortest path searching strategy is single-source single-target bidirectional searching, setting a source node and a target node in the user request as iteration starting points, and executing step S12 and step S13 respectively according to the forward searching direction from the source node to the target node and the reverse searching direction from the target node to the source node.

For single-source single-target forward searching, single-source single-target reverse searching and single-source single-target bidirectional searching, associating iteration starting points of each searching direction with nodes of the determined shortest paths of each searching direction, associating the nodes with the target nodes, and associating the source nodes and the target nodes with all the determination conditions of the expected shortest paths with the nodes. For example, the source node is node a, the target node is node G, the search direction is from node a to node G, the intermediate node includes node B, node a is recorded in association information of the source node for associating the source node with the target node, node G is recorded in association information of the target node, and node a is recorded in association information of node B.

And for forward searching of the single source and single target and reverse searching of the single source and single target, the determined path is the shortest path.

For single-source single-target bidirectional searching, two paths are obtained, namely, a path from the iteration starting point s to the iteration midpoint p, and a path from the iteration midpoint p to the iteration starting point t are combined into a complete path from the starting point s to the end point t. In the path searching process, the following adjacent edge expression mode can be set:

(1) Directed abutment edge<from,to> _f For forward search, a directed edge pointing from to, where from corresponds to a first node, to is a neighbor of from, and to corresponds to a second node.

(2) Directed abutment edge<from,to> _b For reverse search, a directed edge pointing from to, which corresponds to a first node, to is a point of adjacency to, and from corresponds to a second node.

(3) Reverse search adjacent edge<from,to> _b Is adjacent to the forward search<from,to> _f In the opposite direction, i.e. with the second node from pointing to the first node to, and the forward search is with the first node from pointing to the second node to, all with the adjacent edge<from,to>Is uniform in direction.

(4) In the reverse search, the to node in the adjacent edge linear table of the first node to is the same node, and the to node corresponds to a plurality of second nodes from.

(5) In the forward search, from nodes in the adjacent edge linear table of the first node from are the same node, and the from nodes correspond to a plurality of second nodes to.

There are various implementations of single source single target bi-directional lookup, such as whether a unified second node is used to predict shortest path length, whether multi-threading is used. The method comprises the following steps of adopting independent second nodes to predict the shortest path length for forward searching and reverse searching, and independently calculating the second nodes to predict the shortest path length in each iteration direction in the same thread.

The shortest paths of the nodes described herein include: the predecessor nodes of the node and the node have determined path lengths. The determined path length of a node is equal to the sum of the determined path length of a precursor node of the node plus the weight of the adjacent edges between the node and the precursor node of the node, and the node comprises at least one precursor node, for example 0, 1 or more precursor nodes. The determined path length of the node represents the sum of weights moving from the iteration starting point to the node passing through the adjacent edges, the determined path length of the iteration starting point is zero in an initial state, the determined path lengths of the rest nodes are infinity, and the path searching process is updated. Taking an iteration start point as an example, a precursor node of the iteration start point is null, and the determined path length of the iteration start point is zero. For another example, if the node C is a node B, the node B is a source node a, the weight of the adjacent side < a, B > is 3, the weight of the adjacent side < B, C > is 2, the path length is determined to be 5 by the node C. In specific implementation, the shortest path of the node may further include the adjacent edge weight of the node, the record number of the precursor node, the current node, and the record number of the current node. And recording path information with the number of the second node pointing to the first node through the precursor node and the precursor node, and recording adjacent side information through the path length, the precursor node and the current node.

For the adjacent edges < from, to >, the forward search direction points from node from to, the precursor node of node to is the from node, the reverse search direction points from node to node from, and the precursor node of node from is the to node. For example, the shortest path p1- > p2- > p3 consists of two directed edges < p1, p2> and < p2, p3 >: the forward search paths point to p1< -p2 and p2< -p3, opposite to the path direction; the paths of the reverse search point to p2- > p3 and p1- > p2, consistent with the path direction.

As shown in fig. 2, selecting, in step S12, from among the adjacent nodes of the first node in the first node set, the adjacent node closest to the iteration start point to determine the shortest path and update the first node set includes:

step S121, determining relevant information for a first node in the first node set for which relevant information is not determined and removing the first node without relevant information from the first node set.

Wherein the related information of the first node includes: the second node, the adjacent edge to be processed and the second node predict the shortest path length. The adjacent edges to be processed are adjacent edges meeting the following conditions in all adjacent edges between the first node and adjacent nodes of undetermined shortest paths: the contiguous edge weight is the minimum of all contiguous edges and the sum of the contiguous edge weight and the determined path length of the first node is greater than the contiguous edge of the accumulated movement step associated with the first node set. The second node is a non-first node of the adjacent edge to be processed. The second node of the first node expects a shortest path length equal to the weight of the adjacent edge to be processed plus the determined path length of the first node.

In detail, the cumulative moving step length associated with the first node set is equal to the shortest path length of the node which is the most distant from the iteration start point of the determined shortest path, reflects the path weight length which has moved from the iteration start point, and is zero in the initial state. In the same iteration, the method sequentially determines all shortest paths of the second nodes of the adjacent edges with the same weight value of the first node.

In this step, the adjacent edge to be processed may be determined according to an adjacent edge linear table arranged in ascending order of the first node, where the adjacent edge linear table points to the adjacent edge of the first unacknowledged shortest path by means of a pointer, and the determining process includes:

and judging whether the sum of the determined path length of the first node and the adjacent edge weight of the current first unacknowledged shortest path is larger than the accumulated moving step length associated with the first node set, if not, pointing the pointer to the next adjacent edge in the adjacent edge linear table, if so, using the adjacent edge as the next adjacent edge to be processed, wherein the non-first node corresponding to the adjacent edge to be processed is a second node.

Step S122, the first node with the smallest predicted shortest path length of the second node is screened from the first node set.

In step S123, the second node related to the first node is the adjacent node closest to the iteration start point.

When the step is implemented, the screened first node is used as a precursor node of the relevant second node, and the predicted shortest path length of the second node associated with the first node is the determined path length of the second node.

Step S124, updating the accumulated moving step length associated with the first node set as the estimated shortest path length of the second node associated with the screened first node.

Step S125, for the second node, the to-be-processed neighboring edge and the predicted shortest path length of the second node related to each first node, the following determination is performed:

step S1251, when the predicted shortest path length of the second node is equal to the determined path length of the second node, using the second node as a subsequent node, determining related information of the first node according to the first node and the subsequent node which are newly added with a shortest path for the subsequent node, and if no related information exists, removing the first node from the first node set;

the second node predicts the shortest path length, i.e. the sum of the determined path length of the first node and the weight of the adjacent edge to be processed, equal to the determined path length of the second node indicates that the second node has joined the first node set, and only the relevant information of the first node needs to be determined. The first node has no contiguous nodes of the undetermined shortest path when the first node has no relevant information.

Step S1252, when the estimated shortest path length of the second node is smaller than the determined path length of the second node, the second node is used as a subsequent node, the related information of the first node is determined according to the first node and the subsequent node which are newly added with a shortest path for the subsequent node, if no related information exists, the first node is removed from the first node set, the second node is newly added as the first node to the first node set, the related information of the newly added first node is determined, and if no related information exists, the newly added first node is removed from the first node set.

The second node of the first node predicts a shortest path length, i.e., the sum of the determined path length of the first node and the pending adjacency weight, less than the path length of the second node indicates that the second node is not added to the first set of nodes.

In this embodiment, as shown in fig. 3, assuming that the current first node is node 3 and node 2, the second node is node 5 and node 4, and the adjacent edges to be processed are <2,5> and <3,4>, and the weights of paths 0- >2- >5, 0- >3- >5, and 0- >3- >4 are all 10, assuming that after a certain iteration, node 2 can reach node 5, and then node 5 is changed to the first node, according to the foregoing logic, node 3 will not screen out the next adjacent edge to be processed <3,5>, but in fact, the weights of paths 0- >3- >5 and 0- >2- >5 are the same, that is, the paths 0- >3- >5 are also an optimal path, so in the special scenario shown in fig. 3, the foregoing method cannot find all optimal paths, and in order to solve the technical problem, the knowledge-based shortest path information acquisition method further includes:

Determining a third node according to the ordered adjacent edge linear table of each first node, wherein the third node is a node which correctly confirms the shortest path or confirms the shortest path;

if the sum of the determined path length of the first node and the weight of the adjacent edge between the first node and the third node is equal to the determined path length of the third node, the third node is used as a subsequent node, and a shortest path is newly added for the subsequent node according to the first node and the subsequent node thereof; otherwise the first set of parameters is selected,

and if the sum of the determined path length of the first node and the weight of the adjacent edge between the first node and the third node is equal to the accumulated moving step length associated with the first node set, taking the third node as a subsequent node, adding the third node newly added as the first node into the first node set according to the first node and the subsequent node which are newly added as a shortest path for the subsequent node, determining the related information of the newly added first node, and if the related information is not available, removing the newly added first node from the first node set.

Taking fig. 3 as an example, the first node is node 5, node 3, node 4, the precursor node of node 5 is node 2, and assuming that the determined path length of node 5 is 10, the determined path length of node 3 is 2, the determined path length of node 4 is 10, the weight of adjacent sides <3,5> is 8, node 4 and node 5 have no third node, the third node of node 3 is node 5, and the shortest path for updating the third node may update the precursor node of the third node including node 2 and node 3.

In an embodiment herein, to avoid invalid iteration, which affects the searching speed of the minimum path, determining the relevant information of the first node further includes:

judging whether the same second node exists in the related information of at least two first nodes;

if yes, comparing the second nodes of the first nodes with the same second nodes to predict the shortest path length;

if the second node of the first node predicts that the shortest path length is different, only the related information of the first node with the shortest path length predicted by the minimum second node is reserved, and the related information is redetermined for other first nodes.

The method and the device can ensure that unnecessary interference lines are removed in the shortest path searching process, and invalid iterations are avoided.

In an embodiment of the present disclosure, a method for determining a shortest path of a knowledge graph is further provided, which is used to solve the problem of low calculation efficiency in a shortest path determining process based on the knowledge graph in the prior art, where the knowledge graph includes a plurality of nodes and adjacent sides between nodes, and weights of adjacent sides between nodes represent distances between nodes, as shown in fig. 4, the method includes:

step S21, according to a shortest path searching strategy and a source node and a target node in a user request, an iteration starting point and an edge node are initially set, wherein the edge node comprises a first node set node, a node to be selected set node and a relaxation operation set node, the first node set is initially set to comprise the iteration starting point and the shortest path is determined, and the node to be selected and the relaxation operation set are empty; the determined path length of the iteration start point is initially set to zero and the determined path lengths of the remaining nodes are infinity.

The nodes in the first node set are adjacent nodes with determined shortest paths and undetermined shortest paths, the nodes in the node set to be selected are nodes with undetermined shortest paths which can be added into the first node set, and the nodes in the relaxation operation set are nodes with paths obtained through relaxation operation but with undetermined shortest paths.

The shortest path lookup strategy includes: single source single target forward search, single source single target reverse search, single source single target bidirectional search.

In some embodiments, the most path of the node includes a precursor node of the node and a determined path length of the node, the precursor node of the corresponding iteration start point is null, and the determined path length of the iteration start point is zero. In other embodiments, the shortest path of the node further includes node information in the shortest path between the start of the iteration and the node.

When this step is performed, a set of relaxation operations may also be set including the start of the iteration.

Step S22, calculating the heuristic path length of the edge node, wherein the heuristic path length of the edge node is the path length from the iteration starting point to the iteration ending point passing through the edge node.

In this step, the heuristic path length of the edge node can be calculated by using the following formula:

f(n)＝g(n)+h(n)；

Wherein f (n) is a heuristic path length from the iteration start point to the iteration end point through the edge node n, i.e. a predicted cost from the iteration start point to the iteration end point through the edge node n; n is an edge node; h (n) is the predicted path length of the edge node n to reach the iteration end point, namely, how much cost is needed to reach the iteration end point from the edge node; g (n) is the determined path length of the edge node n from the iteration start, i.e. represents the determined cost from the iteration start to the edge node n; h is an estimation function, and h can be Euclidean distance function, manhattan distance, chebyshev distance function and the like, the specific type of h is not limited, and the predicted path length from any node to the iteration end point is smaller than or equal to the shortest path length from the any node to the iteration end point.

Step S23, according to the heuristic path length and the determined path length of the edge nodes, a node pB with the minimum determined path length in the nodes with the maximum heuristic path length is screened out from the first node set and the node set to be selected, and a node pA with the maximum determined path length in the nodes with the minimum heuristic path length is screened out from the relaxation operation set.

In this step, the node pB with the minimum determined path length among the nodes with the maximum heuristic path length screened from the first node set and the node set to be selected is the worst node in the first node set and the node set to be selected, and the node pA with the maximum determined path length among the nodes with the minimum heuristic path length screened from the relaxation operation set is the best node, which is specifically because:

Inspiring the node with the maximum path length f: the actual length of the path reaching the iteration end point through the node is larger than the actual length of the paths reaching the iteration end point of other nodes.

Among the nodes having the maximum heuristic path length f, the node pB having the minimum determined path length g is selected: the predicted path length h that reaches the iteration endpoint through the node is indicated to be the largest, a larger h value has larger uncertainty in the process of converting to g, and the g value from n to the iteration endpoint is larger than other nodes, namely a path with larger quality difference can be generated, so that the node pB is the worst node.

Inspiring the node with the minimum path length f: meaning that the shortest path from the start of the iteration to the node will occur with a high probability on the shortest path from the start of the iteration to the end of the iteration.

Among the nodes of the minimum heuristic path length f, the node pA of which the determined path length g is the largest is selected: the predicted path length h, which represents the arrival at the end of the iteration through the node, is minimal. On the one hand, selecting a smaller h value has less uncertainty in the conversion to g, i.e. will result in a good quality path. On the other hand, selecting the node with the largest g value can ensure that the condition of not less than the accumulated moving step length is met, and on the other hand, the moving frequency of the node between the set processed by the small step mechanism and the relaxation operation set is reduced. Thus, node pA is the best node.

Step S24, selecting a small step algorithm or a relaxation operation algorithm according to the nodes pB and pA, and specifically comprising:

if the set of relaxation operations is null or the heuristic path length of node pB is less than the heuristic path length of node pA, or the heuristic path length of node pB is equal to the heuristic path length of node pA and the determined path length of node pB is greater than or equal to the determined path length of node pA, then the following small-step algorithm is performed: and selecting the adjacent node nearest to the iteration starting point from adjacent nodes of the first node in the first node set, which are not determined to be the shortest paths, determining the shortest paths and updating the first node set.

Otherwise, the paths of all the neighboring nodes of the node pA in the relaxed operation set are calculated based on the relaxed operation and the relaxed operation set is updated.

In this step, calculating paths of all neighboring nodes of the node pA in the set of relaxation operations based on the relaxation operations and updating the set of relaxation operations includes:

determining that the node pA has found the shortest path, removing the node pA from the relaxed operation set, and for any adjacent point pNeighbor of the node pA, calculating a path length cost from the iteration start s to the adjacent node pNeighbor through the node pA as a determined shortest path length g (pA) of the node pA plus a weight of an adjacent edge between the node pA and the node pNeighbor, and performing the following steps:

If cost is less than the original determined path length g (pNeighbor) and pNeighbor is not in the set of relaxation operations: adding the node pNeighbor to the relaxation operation set;

if the cost is less than the original determined path length g (pdeighbor): deleting path information recorded for the pNeighbor, recording path information of an adjacent point pNeighbor according to the node pA and the cost, wherein the path length of the node pNeighbor is the cost, and the precursor node is pA;

if the cost is equal to the original determined path length g (pNeighbor): recording path information of the adjacent point pNeighbor according to the node pA and the cost, namely adding an equal-length path for the pNeighbor;

if the cost is greater than the original determined path length g (pdeighbor): no operation is performed.

Step S25, the loose operation set, the node set to be selected and the nodes in the first node set are moved. The method specifically comprises the following steps:

screening excellent nodes from the relaxation operation set, and moving the excellent nodes to the node set to be selected, wherein the excellent nodes are nodes pA2 with the maximum determined path length in the nodes with the minimum path length inspired by the relaxation operation set;

and when the number of nodes in the first node set and the node set to be selected is larger than a second preset value, screening out nodes exceeding the second preset value from the first node set and the node set to be selected, and moving the nodes to a relaxation operation set.

Step S26, repeating the above processes from step S22 to step S25 until the shortest path from the source node to the target node is found and the heuristic path lengths of the edge nodes are all greater than the lengths of the shortest paths from the source node to the target node.

And step S27, acquiring information from the knowledge graph according to the shortest path of each node and responding to the user request according to the acquired information.

When the step is implemented, information can be obtained according to the meaning represented by the adjacent edges between the nodes in the knowledge graph.

According to the embodiment, the heuristic information is used as the target guide information to combine the small-step algorithm with the relaxation operation algorithm, so that searching blindness of the small-step algorithm caused by no knowledge of iteration end points in the searching process can be reduced, excellent nodes are screened out through the relaxation operation and serve as candidate nodes of a first node in the small-step algorithm, when the number of nodes in the first node set and the candidate node set is larger than a preset value, part of nodes in the first node set and the candidate node set are moved into the relaxation operation set, the searching range of the small-step algorithm can be reduced, and the shortest path from the iteration start point to the iteration end point can be obtained more rapidly.

In an embodiment of the present invention, in step S21, if the shortest path searching policy is a single-source single-target forward searching, the iteration start point is the source node. Further, steps S22 to S25 are performed according to the forward lookup direction from the source node to the target node. The heuristic path length from the iteration start point through the edge node in step S22 is the heuristic path length from the source node through the edge node to the target node.

If the shortest path searching strategy is single-source single-target reverse searching, the iteration starting point is the target node, and the steps S22 to S25 are executed according to the reverse searching direction from the source node to the target node. The heuristic path length from the iteration start point through the edge node in step S22 is the heuristic path length from the target node through the edge node to the source node.

If the shortest path searching strategy is single-source single-target bidirectional searching, the iteration starting point is a source node and a target node, and the steps S22 to S25 are respectively executed according to the forward searching direction from the source node to the target node and the reverse searching direction from the target node to the source node. In the forward direction of search, the heuristic path length from the iteration start point through the edge node in step S22 is the heuristic path length from the source node through the edge node to the target node, and in the reverse direction of search, the heuristic path length from the iteration start point through the edge node in step S22 is the heuristic path length from the target node through the edge node to the source node.

The iteration starting point of each searching direction is associated with the node of the shortest path which is determined for each searching direction, the iteration starting point is associated with the source node and the target node, and the determination condition of the shortest path from the source node to the target node is that the node exists and the source node and the target node are simultaneously associated.

In specific implementation, the single-source single-target bidirectional search uses the iteration starting point s as a search starting point to perform forward search, uses the iteration ending point t as a search starting point to perform reverse search, and finds a shortest path from s to t when the same node is reached. Wherein: (1) Directed abutment edge<from,to> _f For forward search, representing a directed edge pointing from to, where from corresponds to a first node, to is a contiguous point of from, and to corresponds to a second node; (2) Directed abutment edge<from,to> _b For reverse search, representing directed edges pointing from to, where to corresponds to a first node, from is a point of adjacency to, and from corresponds to a second node; (3) Reverse search adjacent edge<from,to> _b Is adjacent to the forward search<from,to> _f In the opposite direction, i.e. in the direction in which the second node from points to the first node to, the forward search is in which the first node from points to the second node to, and the adjacent edge<from,to>Is consistent in direction; (4) In the reverse search, a to node in the adjacent edge linear table of the first node to is the same node, and the to node corresponds to a plurality of second nodes from; (5) In the forward search, a from node in a contiguous edge linear table of a first node from is the same node, and the from node corresponds to a plurality of second nodes to; (6)<from,to>Can refer to an adjacent edge in any search direction, which represents an adjacent edge in a forward search <from,to> _f In the reverse search, the search walks over its representative adjacent edge<from,to> _b 。

In one embodiment, the step S25 of screening out the nodes exceeding the second predetermined value from the first node set and the node set to be selected to move to the relaxation operation set includes:

determining excellent nodes in the first node set and the node set to be selected according to the following mode: screening out nodes of the determined shortest path with the second preset value at most according to the sequence of the heuristic path length from small to large and the determined path length from large to small; and moving the non-excellent nodes in the first node set and the node set to be selected into a relaxation operation set.

The second preset value is a debugging parameter, the second preset value is too small to cause the node to continuously move between the first node set and the node set to be selected and the relaxation operation set, the second preset value is too large to cause the number of the nodes in the first node set and the node set to be selected to be large, and further the calculated amount is increased, so that heuristic information is not applied, the number of times of movement of the node between the first node set and the node set to be selected and the relaxation operation set can be reduced by reasonably selecting the second preset value, and the determination efficiency of the shortest path is improved. In one embodiment, the second predetermined value may be determined by one of three methods:

(1) And setting a fixed second preset value according to the partial or total knowledge graph data.

(2) A fixed second predetermined value is set according to the difference between the iteration start point and the iteration end point.

(3) According to the knowledge graph data and the upper limit and the lower limit of a second preset value designed by the application scene, the second preset value can be set as a value between the lower limit and the upper limit during initialization, and the second preset value is dynamically adjusted according to the following strategies: at each successive K ₀ In the iteration, if the number of nodes of the relaxation operation set moving to the node set to be selected is smaller than K ₁ The second predetermined value decreases M if the number of nodes moved by the set of relaxation operations to the set of nodes to be selected is greater than K ₂ A second predetermined value is increased by M, wherein K ₀ 、K ₁ M is a positive integer, and can be set according to practical conditions. The application scene is, for example, information retrieval, path planning and the like, and depends on the specific application field of the knowledge graph. K as described herein ₀ The number of iterations refers to the number of times the above steps S22 to S24 are performed.

In an embodiment of the present disclosure, in order to avoid a waste of computational power caused by repetition of nodes in the first node set, the node set to be selected, and the relaxation operation set, the method for obtaining information based on a shortest path of a knowledge graph further includes:

And when the first node set is changed, moving out a first intersection node from the relaxation operation set and the node set to be selected, wherein the first intersection node is the intersection node of the first node set, the relaxation operation set and the node set to be selected.

In this step, when a new node is added to the first node set, that is, a node that does not move from the node set to be selected to the first node set, if the new node is in the node set to be selected or the relaxation operation set, the new node is deleted from the node set to be selected and the relaxation operation set.

And when the relaxation operation set is changed, a second intersection node is moved out of the first node set and the node set to be selected, wherein the second intersection node is the intersection node of the relaxation operation set, the first node set and the node set to be selected.

In this step, when a new node is added to the relaxation operation set, that is, a node that does not move from the first node set to the relaxation operation set, if the new node is in the node set to be selected or the first node set, the new node is deleted from the node set to be selected and the first node set.

In one embodiment herein, when the first node set is initially set to include the iteration start point in step S21, the accumulated movement step associated with the first node set is also set to zero.

When the first node set is updated in step S24, the accumulated movement step associated with the first node set is also updated.

The screening out the execution condition of the excellent node moving to the node set to be selected from the relaxation operation set in step S25 includes:

the first node set and the node set to be selected are empty; or the heuristic path length of the excellent node is smaller than the maximum heuristic path length of the nodes in the first node set and the node set to be selected, and the determined path length of the excellent node is larger than or equal to the accumulated moving step length associated with the first node set.

In one embodiment, as shown in fig. 5, in the step S24, from the adjacent nodes of the first node in the first node set, which are not determined to be the shortest paths, selecting the adjacent node closest to the iteration start point to determine the shortest path and updating the first node set includes:

step S241, when the first node set is empty, the node with the minimum determined path length in the node set to be selected is moved to the first node set and the accumulated moving step length associated with the first node set is set as the determined path length of the mobile node.

Step S242, determining relevant information for the first node without determining relevant information in the first node set and removing the first node without relevant information from the first node set.

Wherein the related information of the first node includes: the second node, the adjacent edge to be processed and the second node predict the shortest path length; the adjacent edges to be processed are adjacent edges meeting the following conditions in all adjacent edges between the first node and adjacent nodes of undetermined shortest paths: the adjacent edge weight is the minimum value of all adjacent edges, and the sum of the adjacent edge weight and the determined path length of the first node is larger than the adjacent edge of the accumulated moving step length associated with the first node set; the second node is a non-first node of the adjacent edge to be processed; the second node of the first node predicts a shortest path length equal to the weight of the adjacent edge to be processed plus the determined path length of the first node.

Step S243, the first node with the shortest path length estimated by the second node is screened from the first node set, and the selected node from the node set to be selected is moved to the first node set according to the screened first node.

In this step, when a node moves from the node set to be selected to the first node set, step S242 is re-executed to determine relevant information for the mobile node, and re-determine the first node with the smallest predicted shortest path length for the second node in the first node set.

When the step is implemented, according to the first node which is screened, selecting the node from the node set to be selected to move to the first node set comprises the following steps:

(1) when the second node estimated shortest path length of the first node estimated shortest path length of the screened second node is greater than or equal to the minimum determined path length of the nodes in the node set to be selected, moving the nodes in the node set to be selected to the first node set according to the following steps (2) and (3):

(2) Judging whether the second node associated with the screened first node contains the node pX or not for each node pX corresponding to the minimum determined path length in the node set to be selected,

if not, the node pX is moved from the node set to be selected to the first node set, the relevant information is determined for the node pX, wherein the second node of the node pX predicts the shortest path length=the determined path length of the node px+the weight of the neighboring edge to be processed of the node pX,

if yes, removing the node pX from the node set to be selected;

(3) Judging whether the nodes in the node set to be selected are moved to the first node set in the step (2), if yes, executing the step S243 again to screen the first node with the smallest predicted shortest path length of the second node from the first node set, otherwise, executing the step (1) again until the minimum determined path length of the nodes in the node set to be selected is larger than the second predicted shortest path length of the first node with the smallest predicted shortest path length of the second node, and executing the step S244.

In this step, the first node closest to the iteration start point in the set of nodes to be selected is moved to the first node, so that it is ensured that the second node corresponding to the second node predicted shortest path length of the first node to be selected is the node closest to the iteration start point, which is not determined to be the shortest path, and then the node movement from the loose set to the first node set is completed, and the node closest to the iteration start point in the set of nodes to be selected is preferentially moved to the first node set or removed from the set of nodes to be selected.

In step S244, the second node related to the first node is the adjacent node closest to the iteration start point.

Step S245, updating the accumulated moving step length associated with the first node set as the estimated shortest path length of the second node associated with the screened first node.

Step S246, for the second node, the neighboring edge to be processed and the predicted shortest path length of the second node related to each first node, the following processing is performed:

step S2461, when the estimated shortest path length of the second node of the first node is equal to the determined path length of the second node, using the second node as a subsequent node, determining relevant information of the first node according to a new shortest path of the first node and the subsequent node for the subsequent node, and if no relevant information exists, removing the first node from the first node set.

Step S2462, when the second node of the first node predicts that the shortest path length is smaller than the determined path length of the second node, using the second node as a subsequent node, determining relevant information of the first node according to a shortest path newly added by the first node and the subsequent node for the subsequent node, if there is no relevant information, removing the first node from the first node set, adding the second node newly added as the first node into the first node set, determining relevant information of the newly added first node, and if there is no relevant information, removing the newly added first node from the first node set.

In order to more clearly illustrate the technical solutions of the embodiments shown in fig. 4 to 5, a specific example is used to describe the detailed description below, where the knowledge graph of this embodiment includes 9 nodes, the numbers of the nodes and the weight relationships between the nodes are as shown in fig. 6, the source node is node 0, the end node is node 8, and the heuristic path length f (n), the determined path length g (n) and the predicted path length h (n) of each node are respectively:

g(0)＝0，h(0)＝5，f(0)＝5；

g(1)＝1，h(1)＝4，f(1)＝5；

g(2)＝2，h(2)＝2，f(2)＝4；

g(3)＝2，h(3)＝2，f(1)＝4；

g(4)＝3，h(4)＝5，f(4)＝8；

g(6)＝4，h(6)＝1，f(6)＝5；

g(7)＝5，h(7)＝9，f(7)＝14；

g(8)＝6，h(8)＝0，f(8)＝6。

the information acquisition method based on the shortest path of the knowledge graph comprises the following steps:

initializing: the shortest path length of the iteration starting point 0 is 0, the iteration starting point is initialized to a first node set, the relaxation operation set and the node set to be selected are empty and marked as the relaxation operation set { }, the node set to be selected { }, the first node set {0} and the edge node is only the node 0.

First cycle: the heuristic path length of the edge node is calculated.

The edge node has only node 0, and the heuristic path length f (0) =g (0) +h (0) = 0+5 =5.

The node pb=0 is selected from the first node set and the node set to be selected, and the node pA cannot be screened from the relaxation operation set.

Because the relaxation operation set is empty, a small-step algorithm is executed, node 1 is screened out to be the adjacent node which is closest to the iteration starting point and is not determined to be the shortest path, the shortest path of the node 1 is determined, the determined path length is g (1) =1, and the accumulated moving step length is 1. The first set of nodes is updated to {1,0}.

In this cycle, a small-step algorithm is executed, so that the selected node does not need to be moved from the relaxation operation set to the node set to be selected. The number of nodes in the first node set and the node set to be selected is 2, which is equal to n=2, and the mobile node is not required to enter the relaxation operation set.

Second cycle: the heuristic path length of the edge node is calculated.

The edge node includes node 0 and node 1, and the heuristic path length of node 0 is f (0) =g (0) +h (0) = 0+5 =5, and the heuristic path length of node 1 is f (1) =g (1) +h (1) =1+4=5.

The node pb=0 is selected from the first node set and the node set to be selected, and the node pA cannot be screened from the relaxation operation set. Nodes 2 and 3 are selected as adjacent nodes which are nearest to the iteration start point and have no shortest path, the shortest paths of the nodes 2 and 3 are determined, the determined path lengths of the nodes 2 and 3 are g (2) =g (3) =2, and the cumulative moving step length is 2. The first set of nodes is updated to {2,3,1}.

The number of nodes in the first node set is greater than n=2, at this time, the node with the maximum heuristic path length and the minimum determined path length in the first node set needs to be moved into the relaxation operation set, because f (1) =g (1) +h (1) =1+4=5, f (2) =g (2) +h (2) =2+2=4, f (3) =g (3) +h (3) =2+2=4, and therefore, the node 1 in the first node set is selected to be moved into the relaxation operation set, at this time, the node 1 is moved into the relaxation operation set, the node set to be selected is empty, and the first node set includes the nodes 2 and 3.

Third cycle: the heuristic path length of the edge node is calculated.

The edge nodes include node 1, node 2 and node 3, where the heuristic path length of node 1 is f (1) =g (1) +h (1) =1+4=5, f (2) =g (2) +h (2) =2+2=4, and f (3) =g (3) +h (3) =2+2=4.

The node pb=3 is selected from the first node set and the node set to be selected, and the node pa=1 cannot be screened from the relaxation operation set.

f (pB) < f (pA), selecting a small-step algorithm, wherein node 4 is the adjacent node closest to the iteration start point and the shortest path is not determined, determining the shortest path of node 4, wherein the determined path length is g (4) =3, the cumulative moving step is 3, and updating the first node set to {2,4}.

The number of nodes in the first node set and the node set to be selected is 2 and less than n=3, and the mobile node is not required to enter the relaxation operation set.

Fourth cycle: the heuristic path length of the edge node is calculated.

The edge nodes include node 1, node 2 and node 4, where the heuristic path length of node 1 is f (1) =g (1) +h (1) =1+4=5, f (2) =g (2) +h (2) =2+2=4, and f (4) =g (4) +h (4) =3+5=8.

The node pb=4 is selected from the first node set and the node set to be selected, and the node pa=1 cannot be screened from the relaxation operation set.

f (pB) > f (pA), selecting a relaxation operation algorithm, determining paths of nodes 6 and 7, determining path lengths of node 6 and node 7 to be g (6) =4, g (7) =5, and updating the relaxation operation set to {6,7}, respectively.

The heuristic path length of the nodes in the relaxation operation set is: f (6) =g (6) +h (6) =4+1=5, f (7) =g (7) +h (7) = 5+9 =14, and the excellent node in the relaxation operation set is node 6,f (6) < f (pB) and g (6) =4 is equal to or greater than the accumulated movement step size 3, so node 6 is added to the node set to be selected, at this time, the node set to be selected is {6}, and the first node set is {2,4}. The first node set+the node set to be selected is greater than N, so that the node 4 with the maximum heuristic path length in the first node set+the node set to be selected needs to be moved to the relaxation operation set, at this time, the relaxation operation set is {7,4}, the node set to be selected is {6}, and the first node set is {2}.

Fifth cycle: the heuristic path length of the edge node is calculated.

The edge nodes include node 2, node 6, node 4 and node 7, where the heuristic path length of node 2 is f (2) =g (2) +h (2) =2+2=4, the heuristic path length of node 6 is f (6) =g (6) +h (6) =4+1=5, the heuristic path length of node 4 is f (4) =g (4) +h (4) =3+5=8, and the heuristic path length of node 7 is f (7) =g (7) +h (7) = 5+9 =14.

The node pb=6 is selected from the first node set and the node set to be selected, and the node pa=4 cannot be screened from the relaxation operation set. f (pB) < f (pA), selecting a small-step algorithm, wherein node 8 is the nearest neighbor node to the iteration start point and the shortest path is not determined, determining the shortest path of node 8, which has determined that the path length is g (8) =6, and updating the first node set to {2}.

Moving to the iteration end point of 8, and finding a shortest path reaching the iteration end point. Since f (2) =4 < =g (8), it is also necessary to continue the next cycle.

Sixth cycle: the heuristic path length of the edge node is calculated.

The edge nodes include node 2, node 7 and node 4, where the heuristic path length of node 2 is f (2) =g (2) +h (2) =2+2=4, the heuristic path length of node 4 is f (4) =g (4) +h (4) =3+5=8, and the heuristic path length of node 7 is f (7) =g (7) +h (7) = 5+9 =14.

And continuing iteration according to the loop process until f values of all nodes in the node set to be selected, the relaxation operation set and the first node set are larger than g (8).

In an embodiment herein, in order to avoid invalid iteration and thus affect the searching speed of the minimum path, the determining the related information of the first node in step S242 further includes:

In one embodiment herein, to avoid the occurrence of missing the shortest path, the small-step algorithm further includes:

In an embodiment herein, in order to improve the determination efficiency of the shortest path, a task parallel distributed system is further provided, where the distributed system may process multiple single-target node shortest path determination tasks and single-source node shortest path determination tasks simultaneously by multiple cluster devices, and different computing processes in each task are implemented by using a cluster or parallel computing manner.

Based on the same inventive concept, an information acquisition device based on a shortest path of a knowledge graph is also provided herein, as in the following embodiments. Because the principle of solving the problem of the information acquisition device based on the shortest path of the knowledge graph is similar to that of the information acquisition method based on the shortest path of the knowledge graph, the implementation of the information acquisition device based on the shortest path of the knowledge graph can be referred to the information acquisition method based on the shortest path of the knowledge graph, and repeated parts are omitted.

Specifically, as shown in fig. 7, an information acquisition device based on a shortest path of a knowledge graph includes:

an initialization unit 701, configured to initially set an iteration start point and determine a shortest path according to a shortest path searching policy and a node in a user request;

a shortest path determining unit 702, configured to form a first node set with nodes that have determined shortest paths and have neighboring nodes that have not determined shortest paths as first nodes, select a neighboring node closest to an iteration start point from neighboring nodes that have not determined shortest paths of the first nodes in the first node set, determine the shortest path, and update the first node set;

a loop control unit 703, configured to repeatedly start the shortest path determining unit 702 until all desired shortest paths are found, where the desired shortest paths are related to a shortest path searching policy;

and an information obtaining unit 704, configured to obtain information from the knowledge graph according to the shortest path of each node and respond to the user request according to the obtained information.

As shown in fig. 8, the information acquisition apparatus based on the shortest path of the knowledge graph includes:

an initialization unit 801, configured to initially set an iteration start point and an edge node according to a shortest path searching policy and a source node and a target node in a user request, where the edge node includes a first node set node having a determined shortest path and having an adjacent node of an undetermined shortest path, a node in a node set to be selected of an undetermined shortest path that can join the first node set, and a node in a relaxation operation set node that obtains a path through a relaxation operation but does not determine the shortest path; initially setting a first node set to comprise an iteration starting point and determining the shortest path of the first node set, wherein a node set to be selected and a relaxation operation set are empty; initially setting the determined path length of the iteration start point to be zero, and the determined path lengths of the rest nodes to be infinity;

A calculating unit 802, configured to calculate a heuristic path length of the edge node, where the heuristic path length of the edge node is a path length from an iteration start point to an iteration end point through the edge node;

a screening unit 803, configured to screen, according to the heuristic path length and the determined path length of the edge nodes, a node pB with the minimum determined path length from the nodes with the maximum heuristic path length from the first node set and the node set to be selected, and screen, from the relaxation operation set, a node pA with the maximum determined path length from the nodes with the minimum heuristic path length;

an algorithm selection unit 804, configured to execute the following small-step algorithm if the relaxation operation set is null or the heuristic path length of the node pB is smaller than the heuristic path length of the node pA, or the heuristic path length of the node pB is equal to the heuristic path length of the node pA and the determined path length of the node pB is greater than or equal to the determined path length of the node pA: selecting an adjacent node closest to the iteration starting point from adjacent nodes of the first node in the first node set, which are not determined to be the shortest path, determining the shortest path, and updating the determined path lengths of the first node set and the newly added first node;

A node moving unit 805 configured to screen out an excellent node from the relaxation operation set, and move the excellent node to the node set to be selected, where the excellent node is a node pA2 with the maximum determined path length from nodes with the minimum heuristic path length in the relaxation operation set;

a loop control unit 806, configured to repeatedly start the computing unit, the screening unit, the algorithm selecting unit, and the node moving unit until a shortest path from the source node to the target node is found and the heuristic path lengths of the edge nodes are all greater than the lengths of the shortest paths from the source node to the target node;

an information acquisition unit 807 for acquiring information from the knowledge graph according to the shortest path of each node and responding to a user request according to the acquired information.

In an embodiment herein, there is also provided a computer device, as shown in fig. 9, where the computer device 902 includes a memory 906, a processor 904, and a computer program stored on the memory 906 and executable on the processor 904, and where the processor 904 implements the method described in any of the foregoing embodiments when executing the computer program. The processor 904, such as one or more Central Processing Units (CPUs), may each implement one or more hardware threads. The memory 906 is used to store any kind of information such as code, settings, data, and the like. For example, and without limitation, the memory 906 may include any one or more of the following combinations: any type of RAM, any type of ROM, flash memory devices, hard disks, optical disks, etc. More generally, any memory may store information using any technique. Further, any memory may provide volatile or non-volatile retention of information. Further, any memory may represent fixed or removable components of computer device 902. In one case, when the processor 904 executes associated instructions stored in any memory or combination of memories, the computer device 902 can perform any of the operations of the associated instructions. The computer device 902 also includes one or more drive mechanisms 908 for interacting with any memory, such as a hard disk drive mechanism, optical disk drive mechanism, and the like.

The computer device 902 may also include an input/output module 910 (I/O) for receiving various inputs (via input device 912) and for providing various outputs (via output device 914)). One particular output mechanism may include a presentation device 916 and an associated graphical user interface 918 (GUI). In other embodiments, input/output module 910 (I/O), input device 912, and output device 914 may not be included, but merely as a computer device in a network. The computer device 902 may also include one or more network interfaces 920 for exchanging data with other devices via one or more communication links 922. One or more communication buses 924 couple the above-described components together.

The communication link 922 may be implemented in any manner, for example, through a local area network, a wide area network (e.g., the internet), a point-to-point connection, etc., or any combination thereof. Communication link 922 may include any combination of hardwired links, wireless links, routers, gateway functions, name servers, etc., governed by any protocol or combination of protocols.

Corresponding to the method in fig. 1-2, 4-5, embodiments herein also provide a computer readable storage medium having a computer program stored thereon, which computer program, when being executed by a processor, performs the steps of the above method.

Embodiments herein also provide a computer readable instruction wherein the program therein causes the processor to perform the method as shown in fig. 1-2, 4-5 when the processor executes the instruction.

It should be understood that, in the various embodiments herein, the sequence number of each process described above does not mean the sequence of execution, and the execution sequence of each process should be determined by its functions and internal logic, and should not constitute any limitation on the implementation process of the embodiments herein.

It should also be understood that in embodiments herein, the term "and/or" is merely one relationship that describes an associated object, meaning that three relationships may exist. For example, a and/or B may represent: a exists alone, A and B exist together, and B exists alone. In addition, the character "/" herein generally indicates that the front and rear associated objects are an "or" relationship.

Those of ordinary skill in the art will appreciate that the elements and algorithm steps described in connection with the embodiments disclosed herein may be embodied in electronic hardware, in computer software, or in a combination of the two, and that the elements and steps of the examples have been generally described in terms of function in the foregoing description to clearly illustrate the interchangeability of hardware and software. Whether such functionality is implemented as hardware or software depends upon the particular application and design constraints imposed on the solution. Skilled artisans may implement the described functionality in varying ways for each particular application, but such implementation decisions should not be interpreted as causing a departure from the scope of the present disclosure.

It will be clear to those skilled in the art that, for convenience and brevity of description, specific working procedures of the above-described systems, apparatuses and units may refer to corresponding procedures in the foregoing method embodiments, and are not repeated herein.

In the several embodiments provided herein, it should be understood that the disclosed systems, devices, and methods may be implemented in other ways. For example, the apparatus embodiments described above are merely illustrative, e.g., the division of the units is merely a logical function division, and there may be additional divisions when actually implemented, e.g., multiple units or components may be combined or integrated into another system, or some features may be omitted or not performed. In addition, the coupling or direct coupling or communication connection shown or discussed with each other may be an indirect coupling or communication connection via some interfaces, devices, or elements, or may be an electrical, mechanical, or other form of connection.

The units described as separate units may or may not be physically separate, and units shown as units may or may not be physical units, may be located in one place, or may be distributed on a plurality of network units. Some or all of the elements may be selected according to actual needs to achieve the objectives of the embodiments herein.

In addition, each functional unit in the embodiments herein may be integrated in one processing unit, or each unit may exist alone physically, or two or more units may be integrated in one unit. The integrated units may be implemented in hardware or in software functional units.

The integrated units, if implemented in the form of software functional units and sold or used as stand-alone products, may be stored in a computer readable storage medium. Based on such understanding, the technical solutions herein are essentially or portions contributing to the prior art, or all or portions of the technical solutions may be embodied in the form of a software product stored in a storage medium, including several instructions to cause a computer device (which may be a personal computer, a server, or a network device, etc.) to perform all or part of the steps of the methods described in the embodiments herein. And the aforementioned storage medium includes: a U-disk, a removable hard disk, a Read-Only Memory (ROM), a random access Memory (RAM, random Access Memory), a magnetic disk, or an optical disk, or other various media capable of storing program codes.

Specific examples are set forth herein to illustrate the principles and embodiments herein and are merely illustrative of the methods herein and their core ideas; also, as will be apparent to those of ordinary skill in the art in light of the teachings herein, many variations are possible in the specific embodiments and in the scope of use, and nothing in this specification should be construed as a limitation on the invention.

Claims

1. The information acquisition method based on the shortest path of the knowledge graph is characterized in that the knowledge graph comprises a plurality of nodes and adjacent edges among the nodes, and the weight of the adjacent edges among the nodes represents the distance among the nodes, and the method comprises the following steps:

s12, forming a first node set by taking the nodes with the determined shortest paths and adjacent nodes with undetermined shortest paths as first nodes, selecting the adjacent nodes closest to the iteration starting point from the adjacent nodes with the undetermined shortest paths of the first nodes in the first node set to determine the shortest paths and updating the first node set;

S14, acquiring information from the knowledge graph according to the shortest path of each node and responding to the user request according to the acquired information;

in step S12, selecting the adjacent node closest to the iteration start point from among the adjacent nodes of the first node in the first node set, which are not determined to be the shortest paths, to determine the shortest paths includes:

s121, determining relevant information for a first node which does not determine relevant information in the first node set and removing the first node without relevant information from the first node set, wherein the relevant information of the first node comprises: the second node, the adjacent edge to be processed and the second node predict the shortest path length; the to-be-processed adjacent edge is an adjacent edge meeting the following conditions in all adjacent edges between the first node and adjacent nodes of undetermined shortest paths of the first node: the adjacent edge weight is the minimum value of all adjacent edges, and the sum of the adjacent edge weight and the determined path length of the first node is larger than the accumulated moving step length associated with the first node set; the second node is a non-first node of the adjacent edge to be processed; the second node predicts the shortest path length equal to the weight of the adjacent edge to be processed plus the determined path length of the first node;

S122, screening out the first node with the shortest path length estimated by the second node from the first node set;

s123, the second node related to the screened first node is the adjacent node closest to the iteration starting point;

s124, updating the accumulated moving step length associated with the first node set to be the estimated shortest path length of the second node associated with the screened first node;

s125, for the second node and the adjacent edge to be processed and the shortest path length predicted by the second node relevant to each first node, the following processing is executed:

s1251, when the predicted shortest path length of the second node is equal to the determined path length of the second node, taking the second node as a subsequent node, determining the related information of the first node according to the first node and the subsequent node which are newly added with a shortest path for the subsequent node, and if the related information is not available, removing the first node from the first node set;

and S1252, when the predicted shortest path length of the second node is smaller than the determined path length of the second node, taking the second node as a subsequent node, determining the related information of the first node according to the first node and the subsequent node which are newly added with a shortest path for the subsequent node, removing the first node from the first node set if the related information is not available, adding the second node newly added as the first node into the first node set, determining the related information of the newly added first node, and removing the newly added first node from the first node set if the related information is not available.

2. The method of claim 1, wherein if the shortest path searching policy is single source searching, setting a source node in the user request as an iteration start point, and performing step S12 and step S13 from the source node, where the determining condition of all expected shortest paths is that all nodes having determined shortest paths have no adjacent nodes having undetermined shortest paths;

if the shortest path searching strategy is single-source single-target forward searching, setting a source node in a user request as an iteration starting point, and executing step S12 and step S13 according to the forward searching direction from the source node to the target node;

if the shortest path searching strategy is single-source single-target reverse searching, setting a target node in a user request as an iteration starting point, and executing step S12 and step S13 according to the reverse searching direction from the source node to the target node;

if the shortest path searching strategy is single-source single-target bidirectional searching, setting a source node and a target node in a user request as iteration starting points, and executing the step S12 and the step S13 respectively according to the forward searching direction from the source node to the target node and the reverse searching direction from the target node to the source node;

for single-source single-target forward searching, single-source single-target reverse searching and single-source single-target bidirectional searching, associating iteration starting points of each searching direction with nodes of the determined shortest paths of each searching direction, associating the nodes with the target nodes, wherein the determination condition of all expected shortest paths is that the nodes exist and the source nodes and the target nodes are simultaneously associated.

3. The method of claim 1, wherein the shortest path of the node comprises: the precursor node of the node and the node have determined path lengths;

the determined path length of the node is equal to the sum of the determined path length of a precursor node of the node and the weight of an adjacent edge between the node and the precursor node of the node, and the node at least comprises one precursor node;

initially setting the iteration start point and determining the shortest path thereof in S11 includes: the precursor node of the iteration start point is set to be null, the determined path length of the iteration start point is zero, and the determined path lengths of the rest nodes are infinity.

4. The method of claim 1, wherein the method further comprises:

determining a third node according to the ordered adjacent edge linear table of each first node;

5. The method of claim 1 or 4, wherein adding a shortest path to the successor node based on the first node and the successor node comprises:

the precursor node of the newly added shortest path of the subsequent node is the first node;

the newly added shortest path length of the subsequent node is the weight of the adjacent edge between the first node and the subsequent node plus the determined path length of the first node.

6. The method according to claim 1 or 4, wherein after determining the relevant information of the first node further comprises:

7. The information acquisition method based on the shortest path of the knowledge graph is characterized in that the knowledge graph comprises a plurality of nodes and adjacent edges among the nodes, and the weight of the adjacent edges among the nodes represents the distance among the nodes, and the method comprises the following steps:

S24, if the relaxation operation set is empty or the heuristic path length of the node pB is smaller than the heuristic path length of the node pA, or the heuristic path length of the node pB is equal to the heuristic path length of the node pA and the determined path length of the node pB is larger than or equal to the determined path length of the node pA, executing the following small-step algorithm: selecting an adjacent node closest to the iteration starting point from adjacent nodes of the first node in the first node set, which are not determined to be the shortest paths, determining the shortest paths and updating the first node set;

S27, acquiring information from the knowledge graph according to the shortest path of each node and responding to a user request according to the acquired information;

in step S24, selecting the adjacent node closest to the iteration start point from among the adjacent nodes of the first node in the first node set, which are not determined to be the shortest paths, to determine the shortest paths includes:

s241, when the first node set is empty, moving the node with the minimum determined path length in the node set to be selected to the first node set and setting the accumulated moving step length associated with the first node set as the determined path length of the mobile node;

s242, determining relevant information for a first node in the first node set, where the relevant information is not determined, and removing the first node without relevant information from the first node set, where the relevant information of the first node includes: the second node, the adjacent edge to be processed and the second node predict the shortest path length; the to-be-processed adjacent edge is an adjacent edge meeting the following conditions in all adjacent edges between the first node and adjacent nodes of undetermined shortest paths of the first node: the adjacent edge weight is the minimum value of all adjacent edges, and the sum of the adjacent edge weight and the determined path length of the first node is larger than the accumulated moving step length associated with the first node set; the second node is a non-first node of the adjacent edge to be processed; the second node predicts the shortest path length equal to the weight of the adjacent edge to be processed plus the determined path length of the first node;

S243, a first node with the shortest path length which is predicted to be the smallest by a second node is screened out from the first node set; according to the first node which is screened, selecting nodes from the node set to be selected and moving the nodes to the first node set;

s244, the second node related to the first node is the adjacent node nearest to the iteration starting point;

s245, updating the accumulated moving step length associated with the first node set to be the estimated shortest path length of the second node associated with the screened first node;

s246, for the second node, the adjacent edge to be processed and the predicted shortest path length of the second node relevant to each first node, the following processing is executed:

s2461, when the predicted shortest path length of the second node is equal to the determined path length of the second node, using the second node as a subsequent node, determining the related information of the first node according to the first node and the subsequent node which are newly added with a shortest path for the subsequent node, and if no related information exists, removing the first node from the first node set;

and S2462, when the predicted shortest path length of the second node is smaller than the determined path length of the second node, taking the second node as a subsequent node, determining the related information of the first node according to the first node and the subsequent node which are newly added with a shortest path for the subsequent node, removing the first node from the first node set if the related information is not available, adding the second node newly added as the first node into the first node set, determining the related information of the newly added first node, and removing the newly added first node from the first node set if the related information is not available.

8. The method of claim 7, wherein if the shortest path look-up strategy is single source single target forward look-up, the iteration starting point is a source node, and performing steps S22 through S25 according to a forward look-up direction from the source node to the target node;

if the shortest path searching strategy is single-source single-target reverse searching, the iteration starting point is a target node, and the steps S22 to S25 are executed according to the reverse searching direction from the source node to the target node;

if the shortest path searching strategy is single-source single-target bidirectional searching, the iteration starting point is a source node and a target node, and the steps S22 to S25 are respectively executed according to the forward searching direction from the source node to the target node and the reverse searching direction from the target node to the source node;

9. The method of claim 7, wherein the step S25 of screening out nodes exceeding a second predetermined value from the first set of nodes and the set of nodes to be selected includes:

Determining excellent nodes in the first node set and the node set to be selected according to the following mode: screening out nodes of the determined shortest path of a second preset value before ranking according to the sequence of the heuristic path length from small to large and the determined path length from large to small;

and moving the non-excellent nodes in the first node set and the node set to be selected into a relaxation operation set.

10. The method of claim 9, wherein the second predetermined value determination strategy comprises:

setting a fixed second preset value according to the partial or total knowledge graph data; or (b)

Setting a fixed second preset value according to the difference between the iteration starting point and the iteration ending point; or (b)

According to the knowledge graph data and the upper limit and the lower limit of a second preset value designed by the application scene, the second preset value can be set as a value between the lower limit and the upper limit during initialization, and the second preset value is dynamically adjusted according to the following strategies: at each successive K ₀ In the iteration, if the number of nodes of the relaxation operation set moving to the node set to be selected is smaller than K ₁ The second predetermined value decreases M if the number of nodes moved by the set of relaxation operations to the set of nodes to be selected is greater than K ₂ A second predetermined value is increased by M, wherein K ₀ 、K ₁ M is a positive integer.

11. The method as recited in claim 9, further comprising:

when the first node set changes, a first intersection node is moved out of the relaxation operation set and the node set to be selected, wherein the first intersection node is an intersection node of the first node set, the relaxation operation set and the node set to be selected;

12. The method of claim 7, wherein the shortest path of the node comprises: the precursor node of the node and the determined path length of the node;

the precursor node of the iteration starting point is empty;

the determined path length of the node is equal to the sum of the determined path length of a precursor node of the node plus the weight of the adjacent edge between the node and the precursor node of the node, and the node at least comprises one precursor node.

13. The method of claim 7, wherein the heuristic path length of the edge node is calculated using the formula:

f(n)=g(n)+h(n)；

where f (n) is the heuristic path length of edge node n, n is the edge node, h (n) is the predicted path length of edge node n to the iteration end, h is the estimation function, and g (n) is the determined path length of edge node n from the iteration start.

14. The method of claim 7, wherein when the initial setting of the first node set in step S21 includes an iteration start, further setting the cumulative movement step associated with the first node set to zero;

step S24, updating the accumulated moving step length associated with the first node set;

the first node set and the node set to be selected are empty; or (b)

The heuristic path length of the excellent node is smaller than the maximum heuristic path length of the nodes in the first node set and the node set to be selected, and the determined path length of the excellent node is larger than or equal to the accumulated moving step length associated with the first node set.

15. The method of claim 7, wherein step S243 moves from selecting nodes from a set of nodes to be selected to the set of first nodes based on the first node being selected, comprising:

when the estimated shortest path length of the second node related to the screened first node is greater than or equal to the minimum determined path length of the nodes in the node set to be selected, the nodes in the node set to be selected are moved to the first node set according to the following steps:

Each node pX corresponding to the minimum determined path length in the node set to be selected, judging whether the second node related to the first node selected contains the node pX,

if not, the node pX is moved from the node set to be selected to the first node set, and related information is determined for the node pX, wherein the second node associated with the node pX predicts the shortest path length=the determined path length of the node px+the weight of the neighboring edge to be processed of the node pX, jumps to step S243 to execute the step again,

if yes, removing the node pX from the node set to be selected, and repeating the steps until the determined path length of the nodes in the node set to be selected is greater than the predicted shortest path length of the second node related to the first node.

16. The method of claim 7, wherein the small-step algorithm further comprises:

17. The method according to claim 7 or 16, wherein after determining the relevant information of the first node further comprises:

18. The method of claim 7 or 16, wherein adding a shortest path to the successor node based on the first node and the successor node comprises:

19. An information acquisition device based on a shortest path of a knowledge graph, wherein the knowledge graph comprises a plurality of nodes and adjacent edges among the nodes, and the weight of the adjacent edges among the nodes represents the distance among the nodes, and the device comprises:

The information acquisition unit is used for acquiring information from the knowledge graph according to the shortest path of each node and responding to the user request according to the acquired information;

wherein selecting the nearest neighbor node from the first node set to the iteration start point from among the neighbor nodes of the first node set for which the shortest path is not determined, determining the shortest path includes:

20. An information acquisition device based on a shortest path of a knowledge graph, wherein the knowledge graph comprises a plurality of nodes and adjacent edges among the nodes, and the weight of the adjacent edges among the nodes represents the distance among the nodes, and the device comprises:

an algorithm selection unit, configured to execute the following small-step algorithm if the relaxation operation set is null or the heuristic path length of the node pB is smaller than the heuristic path length of the node pA, or the heuristic path length of the node pB is equal to the heuristic path length of the node pA and the determined path length of the node pB is greater than or equal to the determined path length of the node pA: selecting an adjacent node closest to the iteration starting point from adjacent nodes of the first node in the first node set, which are not determined to be the shortest paths, determining the shortest paths and updating the first node set;

the information acquisition unit is used for acquiring information from the knowledge graph according to the shortest path of each node and responding to a user request according to the acquired information;

selecting, from among the adjacent nodes of the first node in the first set of nodes that are not determining the shortest path, the adjacent node closest to the iteration start point to determine the shortest path includes:

21. A computer device comprising a memory, a processor and a computer program stored on the memory and executable on the processor, wherein the processor implements the method of any one of claims 1 to 18 when the computer program is executed by the processor.

22. A computer storage medium having stored thereon a computer program, which, when executed by a processor of a computer device, performs the instructions of the method according to any of claims 1 to 18.