CN111130846B

CN111130846B - Target object determination method and device and storage medium

Info

Publication number: CN111130846B
Application number: CN201911175306.XA
Authority: CN
Inventors: 侯琛
Original assignee: Tencent Technology Shenzhen Co Ltd
Current assignee: Tencent Technology Shenzhen Co Ltd
Priority date: 2019-11-26
Filing date: 2019-11-26
Publication date: 2021-09-14
Anticipated expiration: 2039-11-26
Also published as: CN111130846A

Abstract

The application discloses a target object determination method, a target object determination device and a storage medium, wherein the method comprises the following steps: acquiring position information and identification information of at least three candidate objects in a target system; determining at least one bilateral ring according to the position information and the identification information of each candidate object; acquiring identification information of the candidate objects in each two-side ring to obtain an identification information set; constructing at least one identification information group according to the identification information set; each identification information group comprises at least two pieces of identification information; determining a candidate palindrome sub-identification information set corresponding to each identification information group; determining a target palindrome sub-identification information set according to at least one candidate palindrome sub-identification information set; and determining the candidate object corresponding to each identification information in the target palindromic sub-identification information set as a target object. By adopting the technical scheme, the maximum palindromic sub-identification information set in the target system and the corresponding target object can be quickly and accurately determined.

Description

Target object determination method and device and storage medium

Technical Field

The present application relates to the field of internet communication technologies, and in particular, to a method, an apparatus, and a storage medium for determining a target object.

Background

When determining the largest palindromic sub-network in the network, the prior art firstly searches from left to right in sequence in a traversal mode; if the palindromic subnetworks are searched, saving the palindromic subnetworks, and continuing to search until all the palindromic subnetworks are found; and finding out the palindromic sub-network with the most nodes from all the palindromic sub-networks, namely the maximum palindromic sub-network. However, in the prior art, the nodes of the same type are generally treated as two different nodes, and the search error rate is high; search spaces for searching the palindromic subnets in a traversal mode are exponentially exploded, and the search efficiency is low;

therefore, it is necessary to provide a target object determining method, device and storage medium, so as to achieve fast and accurate determination of the largest palindromic subnetwork in the target system and the corresponding target object.

Disclosure of Invention

The application provides a target object determination method, a device and a storage medium, which can be used for quickly and accurately determining a maximum palindromic sub-network in a target system and a target object corresponding to the maximum palindromic sub-network.

In one aspect, the present application provides a target object determination method, including:

acquiring position information and identification information of at least three candidate objects in a target system;

determining at least one bilateral ring according to the position information and the identification information of each candidate object;

acquiring identification information of the candidate objects in each two-side ring to obtain an identification information set;

constructing at least one identification information group according to the identification information set; each identification information group comprises at least two pieces of identification information;

determining a candidate palindrome sub-identification information set corresponding to each identification information group;

determining a target palindrome sub-identification information set according to at least one candidate palindrome sub-identification information set;

and determining the candidate object corresponding to each identification information in the target palindromic sub-identification information set as a target object.

Another aspect provides a target object determination apparatus, the apparatus comprising:

the information acquisition module is used for acquiring the position information and the identification information of at least three candidate objects in the target system;

the secondary ring determining module is used for determining at least one secondary ring according to the position information and the identification information of each candidate object;

the identification information set determining module is used for acquiring identification information of the candidate objects in each two-side ring to obtain an identification information set;

the identification information group construction module is used for constructing at least one identification information group according to the identification information set; each identification information group comprises at least two pieces of identification information;

the candidate palindrome sub-identification information set determining module is used for determining a candidate palindrome sub-identification information set corresponding to each identification information group;

the target reply sub-identification information set determining module is used for determining a target reply sub-identification information set according to at least one candidate reply sub-identification information set;

and the target object determining module is used for determining the candidate object corresponding to each identification information in the target palindromic sub-identification information set as the target object.

Another aspect provides a target object determining apparatus, which includes a processor and a memory, where at least one instruction or at least one program is stored in the memory, and the at least one instruction or the at least one program is loaded by the processor and executes the target object determining method described above.

Another aspect provides a computer storage medium storing at least one instruction or at least one program, which is loaded and executed by a processor to implement the target object determining method as described above.

The target object determining method, the target object determining device and the storage medium have the following technical effects:

according to the method, a symmetrical bilateral ring is constructed through position information and identification information of a candidate object in a target system, and all identification information sets meeting the bilateral ring are determined; then constructing an identification information group according to the identification information set, wherein each group comprises a fixed amount of identification information; determining the maximum reply sub-identification information set corresponding to each group, and finally determining the maximum target reply sub-identification information set in all the groups; therefore, the maximum palindrome sub-identification information set in the target system and the corresponding target object can be quickly and accurately determined.

Drawings

In order to more clearly illustrate the technical solutions and advantages of the embodiments of the present application or the prior art, the drawings used in the description of the embodiments or the prior art will be briefly described below, it is obvious that the drawings in the following description are only some embodiments of the present application, and other drawings can be obtained by those skilled in the art without creative efforts.

Fig. 1 is a schematic diagram of a target object determination system provided in an embodiment of the present application;

fig. 2 is a schematic flowchart of a target object determination method according to an embodiment of the present application;

fig. 3 is a schematic structural diagram of a palindromic subnetwork provided in an embodiment of the present application;

fig. 4 is a schematic structural diagram of a virtual network node according to an embodiment of the present application;

fig. 5 is a schematic flowchart of a method for determining a candidate palindromic sub-identity information set corresponding to each identity information group according to an embodiment of the present application;

fig. 6 is a flowchart illustrating a method for determining a target palindrome sub-identification information set according to an embodiment of the present application;

fig. 7 is a flowchart illustrating a method for determining a fault of a target system according to an embodiment of the present application;

fig. 8 is a flowchart illustrating a target object scheduling method according to an embodiment of the present application;

fig. 9 is a schematic flowchart of a screening method for a maximum palindromic subnetwork according to an embodiment of the present application;

fig. 10 is a schematic structural diagram of a sensor network provided in an embodiment of the present application;

fig. 11 is a schematic structural diagram of a hardware platform provided in an embodiment of the present application;

FIG. 12 is a schematic structural diagram of a module in a user program according to an embodiment of the present application;

fig. 13 is a schematic structural diagram of a target object determination apparatus according to an embodiment of the present application;

fig. 14 is a block diagram of a hardware structure of a server for determining a target object according to an embodiment of the present application;

fig. 15 is a schematic structural diagram of a blockchain system according to an embodiment of the present disclosure;

fig. 16 is a block structure diagram according to an embodiment of the present disclosure.

Detailed Description

The technical solutions in the embodiments of the present application will be clearly and completely described below with reference to the drawings in the embodiments of the present application, and it is obvious that the described embodiments are only a part of the embodiments of the present application, and not all of the embodiments. All other embodiments, which can be derived by a person skilled in the art from the embodiments given herein without making any creative effort, shall fall within the protection scope of the present application.

It should be noted that the terms "first," "second," and the like in the description and claims of this application and in the drawings described above are used for distinguishing between similar elements and not necessarily for describing a particular sequential or chronological order. It is to be understood that the data so used is interchangeable under appropriate circumstances such that the embodiments of the application described herein are 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, system, article, or server that comprises a list of steps or elements is not necessarily limited to those steps or elements expressly listed, but may include other steps or elements not expressly listed or inherent to such process, method, article, or apparatus.

Referring to fig. 1, fig. 1 is a schematic diagram of a target object determining system according to an embodiment of the present disclosure, and as shown in fig. 1, the target object determining system may include at least a server 01 and a client 02.

Specifically, in this embodiment of the present disclosure, the server 01 may include a server that operates independently, or a distributed server, or a server cluster composed of a plurality of servers. The server 01 may comprise a network communication unit, a processor, a memory, etc. Specifically, the server 01 may be configured to determine a target object located in the largest palindromic subnetwork in the target system.

Specifically, in the embodiment of the present disclosure, the client 02 may include a physical device such as a smart phone, a desktop computer, a tablet computer, a notebook computer, a digital assistant, and a smart wearable device, and may also include software running in the physical device, such as a web page provided by some service providers to a user, and an application provided by the service providers to the user. Specifically, the client 02 may be used to query a target object located in the largest palindromic subnetwork in the target system on line.

A method for determining a target object of the present application is described below, and fig. 2 is a schematic flow chart of a method for determining a target object provided in an embodiment of the present application, and the present specification provides the method operation steps as described in the embodiment or the flow chart, but may include more or less operation steps based on conventional or non-inventive labor. The order of steps recited in the embodiments is merely one manner of performing the steps in a multitude of orders and does not represent the only order of execution. In practice, the system or server product may be implemented in a sequential or parallel manner (e.g., parallel processor or multi-threaded environment) according to the embodiments or methods shown in the figures. Specifically, as shown in fig. 2, the method may include:

s201: and acquiring the position information and the identification information of at least three candidate objects in the target system.

In embodiments of the present description, the target system may be an internet of things, a car networking, a sensor network, a neural network, or an intelligent network system. The candidate object is an object in the target system; for example, in a vehicle networking system, the candidate object may be a vehicle.

In the embodiment of the specification, since the palindromic sub-network in the target system needs to be determined, and at least three candidate objects are included in one palindromic sub-network, at least three candidate objects exist in the target system; for example, a network path consisting of three candidates is: a → b → a. The location information of the candidate object may be a location of the candidate object in a network where the target system is located. The identification information of the candidate object may be node identification information of the candidate object in the network where the target system is located.

Definition of "palindromic subnets in a network": a) a sub-network of the network; b) the transmission path of information from one end of the sub-network (the former) to the other end (the latter) is the same as the transmission path from the latter to the former. The sub-network whose set of nodes is { C, E, F, G, F, E, C } as in FIG. 3 is a palindromic sub-network.

Since a network is also a sub-network of its own, the palindromic sub-network in the network may also be the network itself; a "palindromic subnetwork" is so called because if the nodes of the network are considered to be text, the string of text read from one end of the subnetwork (the former) to the other end (the latter) is the same as the string of text read from the latter to the former (i.e., read back).

Definition of "maximum palindromic subnetwork in network": the above-mentioned palindromic subnetwork with the largest number of nodes is called the largest palindromic subnetwork.

In some embodiments, the method may further comprise:

based on the attribute information of each candidate object, identification information of each candidate object is determined.

In some embodiments, the identification information of the candidate object may be determined by attribute information of the candidate object, and the same identification information may be set for candidate objects with the same or similar attributes; for example, the candidate object is a vehicle, the attribute is the load of the vehicle, and the same identification information can be set for the vehicle with the load of 10-15 tons, so that the target reply sub-identification information set and the target object in the target system can be conveniently determined subsequently.

S203: and determining at least one bilateral ring according to the position information and the identification information of each candidate object.

The determining at least one bilateral ring based on the location information and the identification information of each candidate object may include:

s2031: constructing a directed graph based on the position information and the identification information of each candidate object;

s2033: constructing an adjacency matrix based on the directed graph;

s2035: based on the adjacency matrix, at least one bilateral ring is determined.

In this specification embodiment, a directed graph may be represented as G ═ V, E, where V is the set of all different network nodes (including virtual network nodes) and E is the set of all network node connections (directed edges).

In the embodiments of the present specification, a two-sided ring refers to a loop formed by two nodes on two sides, and both the sides and the nodes are in the loop.

In an embodiment of the present specification, before the step of determining at least one bilateral ring according to the location information and the identification information of each candidate object, the method may further include:

judging whether the identification information of any two adjacent candidate objects is the same;

if the two adjacent candidate objects are the same, adding a virtual object between the two adjacent candidate objects;

correspondingly, the determining at least one bilateral ring according to the location information and the identification information of each candidate object may include:

determining at least one bilateral ring according to the position information and the identification information of each candidate object and the position information and the identification information of each virtual object;

in the embodiment of the present specification, the introduction of a virtual object is equivalent to the introduction of a virtual network node in a network, and if two adjacent nodes in the network are the same, a virtual network node different from any other node in the network is added between the two nodes, as shown in fig. 4, a virtual node H is introduced between two same nodes H, so that a self-loop in the network can be avoided, and the subsequent rapid determination of a target palindromic subnetwork is facilitated.

Correspondingly, the obtaining the identification information of the candidate object in each bilateral ring to obtain the identification information set may include:

when each two-side ring comprises a virtual object, acquiring identification information of the candidate object and identification information of the virtual object in each two-side ring to obtain an identification information set;

and when each two-side ring does not comprise the virtual object, acquiring the identification information of the candidate object in each two-side ring to obtain an identification information set.

Correspondingly, at least one identification information group is constructed based on the identification information set; the identification information in each identification information group forms an N-edge ring, and the method comprises the following steps:

constructing at least one identification information group based on the identification information set; the identification information in each identification information group forms a 2M side ring, wherein M is more than or equal to 1 and is a positive integer.

In the embodiment of the specification, after the virtual node is introduced, no self-loop exists, the minimum loop is a-b-a, and the loops expanded on the basis of the self-loop are all even loops.

In embodiments of the present description, the set of identification information may be stored based on a blockchain system comprising a plurality of nodes forming a peer-to-peer network therebetween.

In some embodiments, the blockchain system may be the structure shown in fig. 15, a Peer-To-Peer (P2P) network is formed among a plurality of nodes, and the P2P Protocol is an application layer Protocol operating on top of a Transmission Control Protocol (TCP). In the blockchain system, any machine such as a server and a terminal can be added to become a node, and the node comprises a hardware layer, a middle layer, an operating system layer and an application layer.

Fig. 15 shows functions of each node in the blockchain system, and the related functions include:

1) routing, a basic function that a node has, is used to support communication between nodes.

Besides the routing function, the node may also have the following functions:

2) the application is used for being deployed in a block chain, realizing specific services according to actual service requirements, recording data related to the realization functions to form recording data, carrying a digital signature in the recording data to represent a source of task data, and sending the recording data to other nodes in the block chain system, so that the other nodes add the recording data to a temporary block when the source and integrity of the recording data are verified successfully.

3) And the Block chain comprises a series of blocks (blocks) which are mutually connected according to the generated chronological order, new blocks cannot be removed once being added into the Block chain, and recorded data submitted by nodes in the Block chain system are recorded in the blocks.

In some embodiments, the Block Structure (Block Structure) may be the Structure shown in fig. 16, where each Block includes a hash value of the Block storing the transaction record (hash value of the Block) and a hash value of a previous Block, and the blocks are connected by the hash values to form a Block chain. The block may include information such as a time stamp at the time of block generation. A Block chain (Block chain), which is essentially a decentralized database, is a series of data blocks associated by using cryptography, and each data Block contains related information for verifying the validity (anti-counterfeiting) of the information and generating a next Block.

S205: and acquiring the identification information of the candidate object in each two-side ring to obtain an identification information set.

In this embodiment, the identification information set includes at least two identification information sets, for example, for a two-sided ring identified as a-b-a, the corresponding identification information set is { a, b }.

S207: constructing at least one identification information group according to the identification information set; each identification information group includes at least two pieces of identification information.

In an embodiment of the present specification, the identification information set may be divided into a plurality of identification information groups, each of which includes a preset number of pieces of identification information.

In a specific embodiment, one identification information group may be composed of two identification information.

S209: and determining a candidate palindromic sub-identification information set corresponding to each identification information group.

In the embodiment of the present specification, the maximum palindromic subnetwork corresponding to each identifying information group (node pair) is determined.

In this embodiment of the present specification, as shown in fig. 5, the determining the candidate palindromic sub-identity information set corresponding to each identity information group may include:

s2091: determining N side rings corresponding to each identification information group and located in a preset area based on the identification information in each identification information group, wherein N is more than or equal to 2 and is a positive integer;

in this embodiment of the present disclosure, the preset area may be a central area of the target system, for example, an identification information group is { a, b }, and it may be determined that a bilateral ring of the central area corresponds to the identification a-b-a, or it may be determined that a larger bilateral ring of the central area corresponds to the identification c-a-b-a-c.

S2093: taking the N side rings corresponding to each identification information group and located in a preset area as current nodes;

in this embodiment of the present specification, an N-side ring located in a preset region and corresponding to each identification information group may be used as a node, and on this basis, a two-side ring is reconstructed.

S2095: and determining a candidate palindromic sub-identification information set corresponding to each identification information group based on the current node corresponding to each identification information group.

Specifically, in some embodiments, the determining, based on the current node corresponding to each identification information group, a candidate palindromic sub-identification information set corresponding to each identification information group may include:

when the two adjacent identification information of the current node are the identification information centralized target identification information, determining a two-edge ring corresponding to each identification information group according to the current node corresponding to each identification information group and the identification information centralized target identification information, and taking the identification information set in the two-edge ring as the current node again; the candidate objects corresponding to the two adjacent identification information are respectively positioned at two ends of the candidate object corresponding to the current node;

and when at least one of the two adjacent identification information of the current node corresponding to each identification information group is not the target identification information in the identification information set, determining the candidate object set corresponding to the current node as the candidate palindrome sub-identification information set.

Specifically, in some embodiments, a point in a node of the bilateral ring is optionally selected, so that the point and the current node form a new bilateral ring, which is equivalent to performing expansion on the basis of the first bilateral ring; for example, the first two-sided ring is a-b-a, then the expanded two-sided ring is c-a-b-a-c, i.e. a palindromic subnetwork;

if no symmetric node exists at the two ends of the current node, the current two-side ring is the maximum palindromic sub-network (candidate palindromic sub-object set) corresponding to the current identification information group.

Specifically, in some embodiments, the determining, based on the current node corresponding to each identification information group, a candidate palindrome sub-identification information set corresponding to each identification information group includes:

when two adjacent identification information of the current node are the same, determining a two-edge ring corresponding to each identification information group according to the current node corresponding to each identification information group and the adjacent identification information, and using an identification information set in the two-edge ring as the current node again; the candidate objects corresponding to the two adjacent identification information are respectively positioned at two ends of the candidate object corresponding to the current node;

and when the two adjacent identification information of the current node corresponding to each identification information group are different, determining the candidate object set corresponding to the current node as the candidate palindrome sub-identification information set.

In this embodiment of the present specification, when the two identification information groups include two identification information, the determining, based on the identification information in each identification information group, the N-side ring located in the preset region corresponding to each identification information group includes:

determining a two-sided ring and/or a three-sided ring including a self-ring corresponding to each identification information group and located in a preset area based on the identification information in each identification information group;

in the embodiment of the present specification, for one identification information group of { a, b }, it may correspond to a two-sided ring identified as a-b-a, or may correspond to a three-sided ring identified as a-b-b-a and including a self-ring b-b.

In this embodiment of the present specification, when the identification information groups include at least three pieces of identification information, the determining, based on the identification information in each identification information group, an N-side ring located in a preset region corresponding to each identification information group includes:

determining a two-sided ring and/or a three-sided ring including a self-ring corresponding to each identification information group and located in a preset area based on two preset identification information in each identification information group;

and determining N side rings corresponding to each identification information group and located in the preset area based on the identification information except the two preset identification information in each identification information group and the two side rings of the preset area and/or the three side rings including the self ring.

In this embodiment of the present specification, after an identification information group is determined, it is necessary to determine N side rings including a self-ring and N side rings not including a self-ring corresponding to the identification information group, and perform subsequent expansion processing, respectively, so as to determine a candidate palindromic sub-identification information set corresponding to each identification information group.

S2011: and determining a target palindrome sub-identification information set according to at least one candidate palindrome sub-identification information set.

In the embodiment of the present specification, a target palindromic sub-network with the largest amount of identification information is determined according to the largest palindromic sub-network corresponding to a plurality of identification information groups;

in an embodiment of the present specification, as shown in fig. 6, the determining a target palindromic sub-identity information set according to at least one candidate palindromic sub-identity information set may include:

s20111: determining the number of candidate objects in each candidate palindromic sub-identification information set;

s20113: sorting the at least one candidate palindrome sub-identification information set from small to large according to the number of candidate objects;

s20115: and determining the candidate palindromic sub-identification information set of the last ordered position as a target palindromic sub-identification information set.

In this embodiment of the present specification, all candidate palindromic sub-identity information sets may be sorted according to the number of candidate objects in each candidate palindromic sub-identity information set, so that the candidate palindromic sub-identity information set with the largest number of candidate objects is determined as the target palindromic sub-identity information set.

S2013: and determining the candidate object corresponding to each identification information in the target palindromic sub-identification information set as a target object.

In the embodiment of the present specification, when the target system is an internet of vehicles system, a largest-scale palindrome sub-fleet (symmetric fleet) can be determined according to the target palindrome sub-identification information set.

In an embodiment of this specification, after the step of determining a candidate object corresponding to each identification information in the target palindromic sub-identification information set as the target object, the method may further include:

determining the position information of the target object corresponding to the center identification information in the target palindrome sub-identification information set;

and dividing the target palindromic sub-identification information set into a first identification information set and a second identification information set according to the position information of the target object corresponding to the central identification information, wherein the identification information in the first identification information set is the same as the identification information in the second identification information set.

The first identification information set includes at least three first identification information, and the second identification information set includes at least three second identification information.

In this specification, the central identification information may be identification information located at a middle position of the set, which corresponds to the central axis.

The first identification information set and the second identification information set are in a symmetrical relation, and the identification information and the number of the first identification information set and the second identification information set are the same.

In one implementation, for example, in vehicle-road coordination, in a palindromic subnetwork, vehicles on both sides of a center are in one-to-one correspondence except for one or two vehicles at the center, in an internet of vehicles system, there is no need to consider the influence of vehicles in a symmetric region on the system, and if a region has a network delay problem, it can be determined that the influence is caused by internal factors (such as infrastructure equipment and network) of the internet of vehicles system in the region, so that there is no need to separately take two batches of vehicles to detect the infrastructure equipment of the vehicle network.

In this embodiment, the target system includes a first target system and a second target system, and as shown in fig. 7, the method may further include:

s7011: determining a first target area according to position information of a first target object corresponding to each first identification information in the first identification information set, wherein the first target area corresponds to the first target system;

in an embodiment of the present specification, the first target system may be configured to provide a background service for a first target object in the first target area.

S7013: determining a second target area according to position information of a second target object corresponding to each second identification information in the second identification information set, wherein the second target area corresponds to the second target system;

in an embodiment of the present specification, the second target system may be configured to provide a background service for a second target object in the second target area. The first target area and the second target area may be two different areas.

S7015: sending target instructions to each first target object and each second target object through the target object corresponding to the central identification information;

s7017: calculating the sum of the time of each first target object for receiving the target instruction to obtain first time;

s7019: calculating the sum of the time of each second target object for receiving the target instruction to obtain second time;

s70111: and when the difference value between the first time and the second time is greater than or equal to a preset time threshold value, determining that the first target system has a fault.

In an embodiment of the present specification, the method may further include:

and sending a notification message to the first target system so that the first target system overhauls the infrastructure equipment and the network of the target object in the first target area.

In the embodiment of the present specification, when there is a delay in receiving the target instruction by two target areas, it is described that there is a failure in the infrastructure equipment or network, etc. in the target system of one of the target areas.

In a palindromic subnetwork, except for one or two vehicles at the center, the vehicles at the two sides of the center are in one-to-one correspondence, in a vehicle networking system, the influence of the vehicles in a symmetrical area on the system does not need to be considered, if network delay or other problems exist, the influence can be determined to be caused by other factors such as regional equipment or a network, and therefore two batches of vehicles do not need to be taken out separately to be detected, but the vehicles in the existing network are used for detection; after detection, adjustment can be carried out, and the stability and normal operation of the car networking system are ensured.

In this embodiment, each first identification information in the first identification information set corresponds to a first target object and each second identification information in the second identification information set corresponds to a second target object and is located in a first road and a second road, and the first road and the second road correspond to the same target location, as shown in fig. 8, the method may further include:

s801: calculating the sum of preset index values of the target object corresponding to each piece of first identification information in the first identification information set based on a preset index to obtain a first index value;

in this embodiment, when the target object is a vehicle, the preset index may be a cargo capacity corresponding to each vehicle.

S803: calculating the sum of preset index values of the target object corresponding to each second identification information in the second identification information set based on the preset index to obtain a second index value;

s805: and when the difference between the first index value and the second index value is greater than or equal to a preset index difference value, sending a notification message to the target system so that the target system schedules the target object in the first road or the second road.

In this embodiment of the present specification, when the preset index is a cargo capacity corresponding to a vehicle, and a difference between the first index value and the second index value is greater than or equal to a preset index difference value, it indicates that the vehicle is overloaded in the first road, and may send a notification message to the target system, so that the target system schedules the target object in the first road.

In one embodiment, for example, in a formation of vehicles, a fleet of palindromic sub-networks is identified on two roads leading to the same destination (with the approved loads of the vehicles identifying the vehicle and identifying the fleet of palindromic sub-networks), a determination is made as to whether the loads of the vehicles on the two roads are balanced, and if not, scheduling is advised.

Specifically, in the embodiment of the present specification, in a car networking system, the method can be used for finding a maximum-scale bilateral symmetry car fleet; for example, when the total cargo carrying amount of the vehicles on two sides is the same, the cargo carrying amount of the vehicles is used as an index; keeping balance; in intelligent traffic, the utilization rate of each road is balanced; judging whether the loads of the vehicles covering the two roads are balanced or not; determining palindromic sub-network vehicles on two roads leading to the same destination, judging whether a palindromic sub-vehicle group exists, if so, determining whether the loads of the corresponding vehicles are balanced, and if not, recommending improvement. The traffic at each position is ideal as much as possible, and the balance is achieved; and dispatching the freight and the passenger.

The palindromic sub-network is a special sub-network in a network structure, and how to search out the palindromic sub-network with the most nodes (the largest palindromic sub-network) from the existing network is one of the key problems faced by the Internet of things.

The screening method of the maximum palindromic subnetwork in the network can be used for products such as a neural network, a sensor network, an internet of things, an internet of vehicles, a vehicle-road cooperation system and a multi-agent system on a product side. In particular to the products of neural networks, sensor networks, internet of things, internet of vehicles, vehicle-road cooperation, multi-agent and the like of palindromic subnetworks. The application scenario of the application needs to satisfy the following conditions:

1) for the connection between the network nodes, only the direction and the weight of the connection are considered;

2) the connection relation between the network nodes can be obtained, namely, for any network node, which network node points to the network node and which network node the network node points to is acquirable;

3) any network node has only one edge pointing to it and only one edge from it. A many-to-one or many-to-many path in the network may be decomposed into a plurality of one-to-one paths.

In a specific embodiment, for a target network, as shown in fig. 9, the screening method of the corresponding maximum palindromic subnetwork is as follows:

1.1) introducing a virtual network node: if two adjacent nodes in the network are the same, adding a virtual network node different from any other node between the two nodes; if not, no action is required;

1.2) abstracting the processed target network into a directed graph G ═ V, E, where V is a set of all different network nodes (including virtual network nodes), and E is a set of all network node connections (directed edges);

the same network node may be represented by the same node number or symbol or number, such as network node C, E, F in fig. 3;

1.3) write the adjacency matrix of the target network, and mark A ═ a_ij)_n×nWherein a is_ijDenotes the ith row and jth column element, a_ijK denotes that there are k edges pointing from graph node j to graph node i, a_ij0 means that no edge points from graph node j to graph node i; n represents the total number of different network nodes, i.e. the total number of graph nodes;

a set of graph nodes is a set of distinct network nodes. For example, the set of graph nodes (the set of different network nodes) corresponding to the set of network nodes { C, E, F, G, F, E, C } in fig. 3 is { C, E, F, G };

1.4) finding out nodes in all two-edge loops. Specifically, with

The network node corresponding to the nonzero diagonal element is positioned on two sidesIn the ring, the node set in the two-edge loop is recorded as

1.5) optional node pairs

If it is not

And there is no slave except for the edge of the two-sided loop

Departure or arrival

The edge of (1); then

In the same palindrome, note as

1.6) optional

If it is not

(or

) And there is no slave except for the edge of the two-sided loop

Departure or arrival

The edge of (1); then

Updating in the same palindromic network

Make it equal to

1.7) repeat the above steps until all and

nodes in the same palindromic sub-network are removed from all virtual nodes, and the node set in the original network is V_{Go back to}The sub-network of (a) is of a type comprising nodes

A maximum palindromic subnetwork;

1.8) replacing the node pair of the step 1.5), and repeating the steps 1.6) and 1.7) to obtain the maximum palindromic sub-network containing the latest node pair;

1.9) the node pairs are changed and the steps 1.5) to 1.8) are repeated until all palindromic subnets are found. Among these subnetworks, the network with the largest number of nodes is the largest palindromic subnetwork.

The implementation of the present invention will be described in detail below using the embodiment of the sensor network shown in fig. 10.

Example objectives: the screening method of the maximum palindromic sub-network in the network provided by the invention is adopted to select the maximum palindromic sub-network and count the accuracy of screening.

The implementation steps are as follows: the screening method of the maximum palindromic subnetwork in the network is implemented according to the following steps:

1) building a hardware platform, as shown in fig. 11, where the hardware platform may include a user side, the internet or a satellite, and a sensor node in a monitoring area; fig. 12 is a schematic structural diagram of a module in a user program, where the user program is responsible for introducing virtual nodes, abstracting a target network (abstracting the target network into a directed graph), calculating an adjacency matrix, determining a two-sided loop, and determining a palindromic subnetwork, that is, screening a maximum palindromic subnetwork;

2) according to the steps 1.1) -1.9), determining the largest palindromic subnetwork;

3) the experiment was repeated 100 times using the prior art and the method of the present application, respectively, and the accuracy of the screening was counted as shown in table 1 (total number of correct screening divided by total number of experiments);

the prior art method for screening the largest palindromic subnetwork is as follows:

1) searching from left to right in sequence in a traversing mode;

2) if the palindromic subnetworks are searched, saving the palindromic subnetworks, and continuing to search until all the palindromic subnetworks are found;

3) and finding out the palindromic sub-network with the most nodes from all the palindromic sub-networks, namely the maximum palindromic sub-network.

TABLE 1

In the prior art, the nodes of the same type are treated as two different nodes, and the search error rate is high; in the prior art, the search space of the largest palindromic subnetwork is exponentially exploded.

In the invention, the virtual nodes are introduced to avoid the interference caused by the self-loop of the graph and reduce the search error rate; the invention only needs to use the adjacent matrix of the network and the second power of the adjacent matrix, and does not need to calculate the higher power of the adjacent matrix; in the invention, the nodes of the same type are endowed with the same number in the directed graph, which is beneficial to reducing the search error rate; the invention avoids the traversing searching mode in the prior art and reduces the searching space of the largest palindromic sub-network.

As can be seen from the technical solutions provided by the embodiments of the present specification, in the embodiments of the present specification, a symmetric bilateral ring is constructed according to the position information and the identification information of the candidate object in the target system, and all identification information sets satisfying the bilateral ring are determined; then constructing an identification information group according to the identification information set, wherein each group comprises a fixed amount of identification information; determining the maximum reply sub-identification information set corresponding to each group, and finally determining the maximum target reply sub-identification information set in all the groups; therefore, the maximum palindrome sub-identification information set in the target system and the corresponding target object can be quickly and accurately determined.

An embodiment of the present application further provides a target object determining apparatus, as shown in fig. 13, the apparatus includes:

an information obtaining module 1310, configured to obtain location information and identification information of at least three candidate objects in a target system;

a bilateral ring determining module 1320, configured to determine at least one bilateral ring according to the location information and the identification information of each candidate object;

an identification information set determining module 1330, configured to obtain identification information of the candidate object in each bilateral ring, to obtain an identification information set;

an identification information fabric modeling block 1340, configured to construct at least one identification information group according to the identification information set; each identification information group comprises at least two pieces of identification information;

a candidate palindromic sub-identity information set determining module 1350, configured to determine a candidate palindromic sub-identity information set corresponding to each identity information group;

a target reply sub-identification information set determining module 1360 configured to determine a target reply sub-identification information set according to at least one candidate reply sub-identification information set;

a target object determining module 1370, configured to determine, as a target object, a candidate object corresponding to each identification information in the target palindromic sub-identification information set.

In some embodiments, the candidate palindrome sub-identification information set determination module may include:

the device comprises an N-edge ring determining unit, a N-edge ring determining unit and a judging unit, wherein the N-edge ring determining unit is used for determining N-edge rings, corresponding to each identification information group, in a preset area based on the identification information in each identification information group, N is more than or equal to 2, and N is a positive integer;

a current node determining unit, configured to use the N-edge ring located in the preset region and corresponding to each identifier information group as a current node;

and the candidate palindromic sub-identification information set determining unit is used for determining the candidate palindromic sub-identification information set corresponding to each identification information group based on the current node corresponding to each identification information group.

In some embodiments, the candidate palindrome sub-identification information set determination unit may include:

a first current node determining subunit, configured to determine, when two adjacent pieces of identification information of the current node are the target identification information in the identification information set, a two-sided ring corresponding to each identification information group according to the current node corresponding to each identification information group and the target identification information in the identification information set, and regard the identification information set in the two-sided ring as the current node again; the candidate objects corresponding to the two adjacent identification information are respectively positioned at two ends of the candidate object corresponding to the current node;

a first candidate palindromic sub-identity information set determining subunit, configured to determine, when at least one of two neighboring identity information of a current node corresponding to each identity information group is not the target identity information in the identity information set, a candidate object set corresponding to the current node as the candidate palindromic sub-identity information set.

a second current node determining subunit, configured to determine, when two adjacent identification information of the current node are the same, a two-edge ring corresponding to each identification information group according to the current node and the adjacent identification information corresponding to each identification information group, and regard an identification information set in the two-edge ring as the current node again; the candidate objects corresponding to the two adjacent identification information are respectively positioned at two ends of the candidate object corresponding to the current node;

and the second candidate palindromic sub-identification information set determining subunit is used for determining the candidate object set corresponding to the current node as the candidate palindromic sub-identification information set when the two adjacent identification information of the current node corresponding to each identification information group are different.

In some embodiments, the apparatus may further comprise:

the identification information judgment module is used for judging whether the identification information of any two adjacent candidate objects is the same;

a virtual object adding module, configured to add a virtual object between the two adjacent candidate objects if the identification information of the two adjacent candidate objects is the same;

accordingly, the two-scale ring determination module may include:

the two-side ring determining unit is used for determining at least one two-side ring according to the position information and the identification information of each candidate object and the position information and the identification information of each virtual object;

accordingly, the identification information set determination module may include:

a first identification information set determining unit, configured to, when each of the two side rings includes a virtual object, obtain identification information of a candidate object in each of the two side rings and identification information of the virtual object, to obtain an identification information set;

and the second identification information set determining unit is used for acquiring the identification information of the candidate object in each bilateral ring to obtain the identification information set when the virtual object is not included in each bilateral ring.

In some embodiments, the target palindrome sub-identification information set module may include:

the number determining unit of the candidate objects is used for determining the number of the candidate objects in each candidate palindromic sub-identification information set;

the sorting unit is used for sorting the at least one candidate palindrome sub-identification information set from small to large according to the number of the candidate objects;

and the target palindrome sub-identification information set determining unit is used for determining the candidate palindrome sub-identification information set of the last order as the target palindrome sub-identification information set.

In some embodiments, the apparatus may further comprise:

the position information determining module of the target object is used for determining the position information of the target object corresponding to the central identification information in the target palindrome sub-identification information set;

and the identification information set dividing module is used for dividing the target palindromic sub-identification information set into a first identification information set and a second identification information set according to the position information of the target object corresponding to the central identification information, wherein the identification information in the first identification information set is the same as the identification information in the second identification information set.

In some embodiments, the target system comprises a first target system and a second target system, the apparatus may further comprise:

a first target area determining module, configured to determine a first target area according to location information of a first target object corresponding to each piece of first identification information in the first identification information set, where the first target area corresponds to the first target system;

a second target area determining module, configured to determine a second target area according to location information of a second target object corresponding to each piece of second identification information in the second identification information set, where the second target area corresponds to the second target system;

the target instruction sending module is used for sending target instructions to each first target object and each second target object through the target object corresponding to the central identification information;

the first time determining module is used for calculating the sum of the time of each first target object for receiving the target instruction to obtain first time;

the second time determining module is used for calculating the sum of the time of receiving the target instruction by each second target object to obtain second time;

and the fault determining module is used for determining that the first target system has a fault when the difference value between the first time and the second time is greater than or equal to a preset time threshold value.

In some embodiments, each first identification information in the first set of identification information corresponds to a first target object located in a first road, each second identification information in the second set of identification information corresponds to a second target object located in a second road, the first road and the second road corresponding to a same target location, and the apparatus may further include:

the first index value determination module is used for calculating the sum of preset index values of the target object corresponding to each piece of first identification information in the first identification information set based on a preset index to obtain a first index value;

the second index value determining module is used for calculating the sum of preset index values of the target object corresponding to each second identification information in the second identification information set based on the preset index to obtain a second index value;

and the notification message sending module is used for sending a notification message to the target system when the difference between the first index value and the second index value is greater than or equal to a preset index difference value, so that the target system schedules the target object in the first road or the second road.

The device and method embodiments in the device embodiment described are based on the same inventive concept.

The embodiment of the present application provides a target object determining apparatus, which includes a processor and a memory, where the memory stores at least one instruction or at least one program, and the at least one instruction or the at least one program is loaded and executed by the processor to implement the target object determining method provided by the above method embodiment.

Embodiments of the present application further provide a computer storage medium, where the storage medium may be disposed in a terminal to store at least one instruction or at least one program for implementing a target object determination method in the method embodiments, and the at least one instruction or the at least one program is loaded and executed by the processor to implement the target object determination method provided in the method embodiments.

Alternatively, in the present specification embodiment, the storage medium may be located at least one network server among a plurality of network servers of a computer network. Optionally, in this embodiment, the storage medium may include, but is not limited to: a U-disk, a Read-Only Memory (ROM), a Random Access Memory (RAM), a removable hard disk, a magnetic or optical disk, and other various media capable of storing program codes.

The memory described in the embodiments of the present disclosure may be used to store software programs and modules, and the processor may execute various functional applications and data processing by operating the software programs and modules stored in the memory. The memory can mainly comprise a program storage area and a data storage area, wherein the program storage area can store an operating system, application programs needed by functions and the like; the storage data area may store data created according to use of the apparatus, and the like. Further, the memory may include high speed random access memory, and may also include non-volatile memory, such as at least one magnetic disk storage device, flash memory device, or other volatile solid state storage device. Accordingly, the memory may also include a memory controller to provide the processor access to the memory.

The target object determination method provided by the embodiment of the application can be executed in a mobile terminal, a computer terminal, a server or a similar operation device. Taking an example of the application running on a server, fig. 14 is a block diagram of a hardware structure of a server for determining a target object according to an embodiment of the present application. As shown in fig. 14, the server 1400 may have a relatively large difference due to different configurations or performances, and may include one or more Central Processing Units (CPUs) 1410 (the processor 1410 may include but is not limited to a Processing device such as a microprocessor MCU or a programmable logic device FPGA), a memory 1430 for storing data, and one or more storage media 1420 (e.g., one or more mass storage devices) for storing application programs 1423 or data 1422. Memory 1430 and storage medium 1420 may be, among other things, transient storage or persistent storage. The program stored on the storage medium 1420 may include one or more modules, each of which may include a series of instruction operations on a server. Still further, a central processor 1410 may be provided in communication with the storage medium 1420 to execute a series of instruction operations in the storage medium 1420 on the server 1400. The server 1400 may also include one or more power supplies 1460, one or more wired or wireless network interfaces 1450, one or more input-output interfaces 1440, and/or one or more operating systems 1421, such as Windows Server, Mac OS XTM, UnixTM, LinuxTM, FreeBSDTM, etc.

The input/output interface 1440 may be used to receive or transmit data via a network. Specific examples of the network described above may include a wireless network provided by a communication provider of the server 1400. In one example, the i/o Interface 1440 includes a Network Interface Controller (NIC) that can be connected to other Network devices via a base station to communicate with the internet. In one example, the i/o interface 1440 may be a Radio Frequency (RF) module, which is used to communicate with the internet in a wireless manner.

It will be understood by those skilled in the art that the structure shown in fig. 14 is only an illustration and is not intended to limit the structure of the electronic device. For example, server 1400 may also include more or fewer components than shown in FIG. 14, or have a different configuration than shown in FIG. 14.

As can be seen from the embodiments of the target object determining method, device, server, or storage medium provided by the present application, a symmetric bilateral ring is constructed according to the position information and the identification information of the candidate object in the target system, and all identification information sets satisfying the bilateral ring are determined; then constructing an identification information group according to the identification information set, wherein each group comprises a fixed amount of identification information; determining the maximum reply sub-identification information set corresponding to each group, and finally determining the maximum target reply sub-identification information set in all the groups; therefore, the maximum palindrome sub-identification information set in the target system and the corresponding target object can be quickly and accurately determined.

It should be noted that: the sequence of the embodiments of the present application is only for description, and does not represent the advantages and disadvantages of the embodiments. And specific embodiments thereof have been described above. Other embodiments are within the scope of the following claims. In some cases, the actions or steps recited in the claims may be performed in a different order than in the embodiments and still achieve desirable results. In addition, the processes depicted in the accompanying figures do not necessarily require the particular order shown, or sequential order, to achieve desirable results. In some embodiments, multitasking and parallel processing may also be possible or may be advantageous.

The embodiments in the present specification are described in a progressive manner, and the same and similar parts among the embodiments are referred to each other, and each embodiment focuses on the differences from the other embodiments. In particular, as for the apparatus, device, and storage medium embodiments, since they are substantially similar to the method embodiments, the description is relatively simple, and reference may be made to some descriptions of the method embodiments for relevant points.

It will be understood by those skilled in the art that all or part of the steps for implementing the above embodiments may be implemented by hardware, or may be implemented by a program instructing relevant hardware, where the program may be stored in a computer storage medium, and the above storage medium may be a read-only memory, a magnetic disk, an optical disk, or the like.

The above description is only exemplary of the present application and should not be taken as limiting the present application, as any modification, equivalent replacement, or improvement made within the spirit and principle of the present application should be included in the protection scope of the present application.

Claims

1. A method for target object determination, the method comprising:

determining N side rings corresponding to each identification information group and located in a preset area based on the identification information in each identification information group, wherein N is more than or equal to 2 and is a positive integer;

taking the N side rings corresponding to each identification information group and located in a preset area as current nodes;

determining a candidate palindromic sub-identification information set corresponding to each identification information group based on the current node corresponding to each identification information group;

2. The method of claim 1, wherein determining the candidate palindromic sub-identity information set corresponding to each identity information group based on the current node corresponding to each identity information group comprises:

3. The method of claim 1, wherein determining the candidate palindromic sub-identity information set corresponding to each identity information group based on the current node corresponding to each identity information group comprises:

4. The method of claim 1, wherein the step of determining at least one bilateral ring based on the location information and the identification information of each candidate object is preceded by the method further comprising:

correspondingly, the determining at least one bilateral ring according to the position information and the identification information of each candidate object includes:

correspondingly, the obtaining the identification information of the candidate object in each bilateral ring to obtain the identification information set includes:

5. The method of claim 1, wherein determining a target palindromic sub-identity information set based on at least one candidate palindromic sub-identity information set comprises:

determining the number of candidate objects in each candidate palindromic sub-identification information set;

sorting the at least one candidate palindrome sub-identification information set from small to large according to the number of candidate objects;

determining the candidate palindromic sub-identification information set of the last order as a target palindromic sub-identification information set;

after the step of determining the candidate object corresponding to each identification information in the target palindromic sub-identification information set as the target object, the method further includes:

6. The method of claim 5, wherein the target system comprises a first target system and a second target system, the method further comprising:

determining a first target area according to position information of a first target object corresponding to each first identification information in the first identification information set, wherein the first target area corresponds to the first target system;

determining a second target area according to position information of a second target object corresponding to each second identification information in the second identification information set, wherein the second target area corresponds to the second target system;

sending target instructions to each first target object and each second target object through the target object corresponding to the central identification information;

calculating the sum of the time of each first target object for receiving the target instruction to obtain first time;

calculating the sum of the time of each second target object for receiving the target instruction to obtain second time;

and when the difference value between the first time and the second time is greater than or equal to a preset time threshold value, determining that the first target system has a fault.

7. The method of claim 5, wherein each first identification information in the first set of identification information corresponds to a first target object being located in a first road, wherein each second identification information in the second set of identification information corresponds to a second target object being located in a second road, and wherein the first road and the second road correspond to a same target location, the method further comprising:

calculating the sum of preset index values of the target object corresponding to each piece of first identification information in the first identification information set based on a preset index to obtain a first index value;

calculating the sum of preset index values of the target object corresponding to each second identification information in the second identification information set based on the preset index to obtain a second index value;

and when the difference between the first index value and the second index value is greater than or equal to a preset index difference value, sending a notification message to the target system so that the target system schedules the target object in the first road or the second road.

8. A target object determination apparatus, characterized in that the apparatus comprises:

the candidate palindrome sub-identification information set determining module is used for determining a candidate palindrome sub-identification information set corresponding to each identification information group; the candidate palindrome sub-identification information set determination module comprises: the device comprises an N-edge ring determining unit, a N-edge ring determining unit and a judging unit, wherein the N-edge ring determining unit is used for determining N-edge rings, corresponding to each identification information group, in a preset area based on the identification information in each identification information group, N is more than or equal to 2, and N is a positive integer; a current node determining unit, configured to use the N-edge ring located in the preset region and corresponding to each identifier information group as a current node; a candidate palindrome sub-identification information set determining unit, configured to determine a candidate palindrome sub-identification information set corresponding to each identification information group based on the current node corresponding to each identification information group;

9. A computer storage medium having at least one instruction or at least one program stored therein, the at least one instruction or the at least one program being loaded and executed by a processor to perform the method of object determination as claimed in any one of claims 1 to 7.