Bidirectional Dijkstra algorithm whose time complexity is 8O(n~2) is proposed. The theory foundation is that the classical Dijkstra algorithm has not any directional feature during searching the shortest path. The alg...Bidirectional Dijkstra algorithm whose time complexity is 8O(n~2) is proposed. The theory foundation is that the classical Dijkstra algorithm has not any directional feature during searching the shortest path. The algorithm takes advantage of the adjacent link and the mechanism of bidirectional search, that is, the algorithm processes the positive search from start point to destination point and the negative search from destination point to start point at the same time. Finally, combining with the practical application of route-planning algorithm in embedded real-time vehicle navigation system (ERTVNS), one example of its practical applications is given, analysis in theory and the experimental results show that compared with the Dijkstra algorithm, the new algorithm can reduce time complexity, and guarantee the searching precision, it satisfies the needs of ERTVNS.展开更多
Dijkstra algorithm is a theoretical basis to solve transportation network problems of the shortest path, which has a wide range of application in path optimization. Through analyzing traditional Dijkstra algorithm,on ...Dijkstra algorithm is a theoretical basis to solve transportation network problems of the shortest path, which has a wide range of application in path optimization. Through analyzing traditional Dijkstra algorithm,on account of the insufficiency of this algorithm in path optimization,this paper uses adjacency list and circular linked list with combination to store date,and through the improved quick sorting algorithm for weight sorting, accomplish a quick search to the adjacent node,and so an improved Dijkstra algorithm is got.Then apply it to the optimal path search,and make simulation analysis for this algorithm through the example,also verify the effectiveness of the proposed algorithm.展开更多
Optimal path planning avoiding obstacles is among the most attractive applications of mobile robots(MRs)in both research and education.In this paper,an optimal collision-free algorithm is designed and implemented prac...Optimal path planning avoiding obstacles is among the most attractive applications of mobile robots(MRs)in both research and education.In this paper,an optimal collision-free algorithm is designed and implemented practically based on an improved Dijkstra algorithm.To achieve this research objectives,first,the MR obstacle-free environment is modeled as a diagraph including nodes,edges and weights.Second,Dijkstra algorithm is used offline to generate the shortest path driving the MR from a starting point to a target point.During its movement,the robot should follow the previously obtained path and stop at each node to test if there is an obstacle between the current node and the immediately following node.For this aim,the MR was equipped with an ultrasonic sensor used as obstacle detector.If an obstacle is found,the MR updates its diagraph by excluding the corresponding node.Then,Dijkstra algorithm runs on the modified diagraph.This procedure is repeated until reaching the target point.To verify the efficiency of the proposed approach,a simulation was carried out on a hand-made MR and an environment including 9 nodes,19 edges and 2 obstacles.The obtained optimal path avoiding obstacles has been transferred into motion control and implemented practically using line tracking sensors.This study has shown that the improved Dijkstra algorithm can efficiently solve optimal path planning in environments including obstacles and that STEAM-based MRs are efficient cost-effective tools to practically implement the designed algorithm.展开更多
A novel method of global optimal path planning for mobile robot was proposed based on the improved Dijkstra algorithm and ant system algorithm. This method includes three steps: the first step is adopting the MAKLINK ...A novel method of global optimal path planning for mobile robot was proposed based on the improved Dijkstra algorithm and ant system algorithm. This method includes three steps: the first step is adopting the MAKLINK graph theory to establish the free space model of the mobile robot, the second step is adopting the improved Dijkstra algorithm to find out a sub-optimal collision-free path, and the third step is using the ant system algorithm to adjust and optimize the location of the sub-optimal path so as to generate the global optimal path for the mobile robot. The computer simulation experiment was carried out and the results show that this method is correct and effective. The comparison of the results confirms that the proposed method is better than the hybrid genetic algorithm in the global optimal path planning.展开更多
This study is trying to address the critical need for efficient routing in Mobile Ad Hoc Networks(MANETs)from dynamic topologies that pose great challenges because of the mobility of nodes.Themain objective was to del...This study is trying to address the critical need for efficient routing in Mobile Ad Hoc Networks(MANETs)from dynamic topologies that pose great challenges because of the mobility of nodes.Themain objective was to delve into and refine the application of the Dijkstra’s algorithm in this context,a method conventionally esteemed for its efficiency in static networks.Thus,this paper has carried out a comparative theoretical analysis with the Bellman-Ford algorithm,considering adaptation to the dynamic network conditions that are typical for MANETs.This paper has shown through detailed algorithmic analysis that Dijkstra’s algorithm,when adapted for dynamic updates,yields a very workable solution to the problem of real-time routing in MANETs.The results indicate that with these changes,Dijkstra’s algorithm performs much better computationally and 30%better in routing optimization than Bellman-Ford when working with configurations of sparse networks.The theoretical framework adapted,with the adaptation of the Dijkstra’s algorithm for dynamically changing network topologies,is novel in this work and quite different from any traditional application.The adaptation should offer more efficient routing and less computational overhead,most apt in the limited resource environment of MANETs.Thus,from these findings,one may derive a conclusion that the proposed version of Dijkstra’s algorithm is the best and most feasible choice of the routing protocol for MANETs given all pertinent key performance and resource consumption indicators and further that the proposed method offers a marked improvement over traditional methods.This paper,therefore,operationalizes the theoretical model into practical scenarios and also further research with empirical simulations to understand more about its operational effectiveness.展开更多
Cornachia’s algorithm can be adapted to the case of the equation x2+dy2=nand even to the case of ax2+bxy+cy2=n. For the sake of completeness, we have given modalities without proofs (the proof in the case of the equa...Cornachia’s algorithm can be adapted to the case of the equation x2+dy2=nand even to the case of ax2+bxy+cy2=n. For the sake of completeness, we have given modalities without proofs (the proof in the case of the equation x2+y2=n). Starting from a quadratic form with two variables f(x,y)=ax2+bxy+cy2and n an integer. We have shown that a primitive positive solution (u,v)of the equation f(x,y)=nis admissible if it is obtained in the following way: we take α modulo n such that f(α,1)≡0modn, u is the first of the remainders of Euclid’s algorithm associated with n and α that is less than 4cn/| D |) (possibly α itself) and the equation f(x,y)=n. has an integer solution u in y. At the end of our work, it also appears that the Cornacchia algorithm is good for the form n=ax2+bxy+cy2if all the primitive positive integer solutions of the equation f(x,y)=nare admissible, i.e. computable by the algorithmic process.展开更多
Since Grover’s algorithm was first introduced, it has become a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The original application was the uns...Since Grover’s algorithm was first introduced, it has become a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The original application was the unstructured search problems with the time complexity of O(). In Grover’s algorithm, the key is Oracle and Amplitude Amplification. In this paper, our purpose is to show through examples that, in general, the time complexity of the Oracle Phase is O(N), not O(1). As a result, the time complexity of Grover’s algorithm is O(N), not O(). As a secondary purpose, we also attempt to restore the time complexity of Grover’s algorithm to its original form, O(), by introducing an O(1) parallel algorithm for unstructured search without repeated items, which will work for most cases. In the worst-case scenarios where the number of repeated items is O(N), the time complexity of the Oracle Phase is still O(N) even after additional preprocessing.展开更多
Grovers algorithm is a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The Amplitude Amplification in Grovers algorithm is T = O(N). This paper intr...Grovers algorithm is a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The Amplitude Amplification in Grovers algorithm is T = O(N). This paper introduces two new algorithms for Amplitude Amplification in Grovers algorithm with a time complexity of T = O(logN), aiming to improve efficiency in quantum computing. The difference between Grovers algorithm and our first algorithm is that the Amplitude Amplification ratio in Grovers algorithm is an arithmetic series and ours, a geometric one. Because our Amplitude Amplification ratios converge much faster, the time complexity is improved significantly. In our second algorithm, we introduced a new concept, Amplitude Transfer where the marked state is transferred to a new set of qubits such that the new qubit state is an eigenstate of measurable variables. When the new qubit quantum state is measured, with high probability, the correct solution will be obtained.展开更多
文摘Bidirectional Dijkstra algorithm whose time complexity is 8O(n~2) is proposed. The theory foundation is that the classical Dijkstra algorithm has not any directional feature during searching the shortest path. The algorithm takes advantage of the adjacent link and the mechanism of bidirectional search, that is, the algorithm processes the positive search from start point to destination point and the negative search from destination point to start point at the same time. Finally, combining with the practical application of route-planning algorithm in embedded real-time vehicle navigation system (ERTVNS), one example of its practical applications is given, analysis in theory and the experimental results show that compared with the Dijkstra algorithm, the new algorithm can reduce time complexity, and guarantee the searching precision, it satisfies the needs of ERTVNS.
基金supported by the "Taishan Scholarship" Construction Engineering and Shandong Province Graduate Innovative Project(SDYC08011).
文摘Dijkstra algorithm is a theoretical basis to solve transportation network problems of the shortest path, which has a wide range of application in path optimization. Through analyzing traditional Dijkstra algorithm,on account of the insufficiency of this algorithm in path optimization,this paper uses adjacency list and circular linked list with combination to store date,and through the improved quick sorting algorithm for weight sorting, accomplish a quick search to the adjacent node,and so an improved Dijkstra algorithm is got.Then apply it to the optimal path search,and make simulation analysis for this algorithm through the example,also verify the effectiveness of the proposed algorithm.
基金This research has been funded by Scientific Research Deanship at University of Ha’il–Saudi Arabia through Project Number BA-2107.
文摘Optimal path planning avoiding obstacles is among the most attractive applications of mobile robots(MRs)in both research and education.In this paper,an optimal collision-free algorithm is designed and implemented practically based on an improved Dijkstra algorithm.To achieve this research objectives,first,the MR obstacle-free environment is modeled as a diagraph including nodes,edges and weights.Second,Dijkstra algorithm is used offline to generate the shortest path driving the MR from a starting point to a target point.During its movement,the robot should follow the previously obtained path and stop at each node to test if there is an obstacle between the current node and the immediately following node.For this aim,the MR was equipped with an ultrasonic sensor used as obstacle detector.If an obstacle is found,the MR updates its diagraph by excluding the corresponding node.Then,Dijkstra algorithm runs on the modified diagraph.This procedure is repeated until reaching the target point.To verify the efficiency of the proposed approach,a simulation was carried out on a hand-made MR and an environment including 9 nodes,19 edges and 2 obstacles.The obtained optimal path avoiding obstacles has been transferred into motion control and implemented practically using line tracking sensors.This study has shown that the improved Dijkstra algorithm can efficiently solve optimal path planning in environments including obstacles and that STEAM-based MRs are efficient cost-effective tools to practically implement the designed algorithm.
文摘A novel method of global optimal path planning for mobile robot was proposed based on the improved Dijkstra algorithm and ant system algorithm. This method includes three steps: the first step is adopting the MAKLINK graph theory to establish the free space model of the mobile robot, the second step is adopting the improved Dijkstra algorithm to find out a sub-optimal collision-free path, and the third step is using the ant system algorithm to adjust and optimize the location of the sub-optimal path so as to generate the global optimal path for the mobile robot. The computer simulation experiment was carried out and the results show that this method is correct and effective. The comparison of the results confirms that the proposed method is better than the hybrid genetic algorithm in the global optimal path planning.
基金supported by Northern Border University,Arar,Kingdom of Saudi Arabia,through the Project Number“NBU-FFR-2024-2248-03”.
文摘This study is trying to address the critical need for efficient routing in Mobile Ad Hoc Networks(MANETs)from dynamic topologies that pose great challenges because of the mobility of nodes.Themain objective was to delve into and refine the application of the Dijkstra’s algorithm in this context,a method conventionally esteemed for its efficiency in static networks.Thus,this paper has carried out a comparative theoretical analysis with the Bellman-Ford algorithm,considering adaptation to the dynamic network conditions that are typical for MANETs.This paper has shown through detailed algorithmic analysis that Dijkstra’s algorithm,when adapted for dynamic updates,yields a very workable solution to the problem of real-time routing in MANETs.The results indicate that with these changes,Dijkstra’s algorithm performs much better computationally and 30%better in routing optimization than Bellman-Ford when working with configurations of sparse networks.The theoretical framework adapted,with the adaptation of the Dijkstra’s algorithm for dynamically changing network topologies,is novel in this work and quite different from any traditional application.The adaptation should offer more efficient routing and less computational overhead,most apt in the limited resource environment of MANETs.Thus,from these findings,one may derive a conclusion that the proposed version of Dijkstra’s algorithm is the best and most feasible choice of the routing protocol for MANETs given all pertinent key performance and resource consumption indicators and further that the proposed method offers a marked improvement over traditional methods.This paper,therefore,operationalizes the theoretical model into practical scenarios and also further research with empirical simulations to understand more about its operational effectiveness.
文摘Cornachia’s algorithm can be adapted to the case of the equation x2+dy2=nand even to the case of ax2+bxy+cy2=n. For the sake of completeness, we have given modalities without proofs (the proof in the case of the equation x2+y2=n). Starting from a quadratic form with two variables f(x,y)=ax2+bxy+cy2and n an integer. We have shown that a primitive positive solution (u,v)of the equation f(x,y)=nis admissible if it is obtained in the following way: we take α modulo n such that f(α,1)≡0modn, u is the first of the remainders of Euclid’s algorithm associated with n and α that is less than 4cn/| D |) (possibly α itself) and the equation f(x,y)=n. has an integer solution u in y. At the end of our work, it also appears that the Cornacchia algorithm is good for the form n=ax2+bxy+cy2if all the primitive positive integer solutions of the equation f(x,y)=nare admissible, i.e. computable by the algorithmic process.
文摘Since Grover’s algorithm was first introduced, it has become a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The original application was the unstructured search problems with the time complexity of O(). In Grover’s algorithm, the key is Oracle and Amplitude Amplification. In this paper, our purpose is to show through examples that, in general, the time complexity of the Oracle Phase is O(N), not O(1). As a result, the time complexity of Grover’s algorithm is O(N), not O(). As a secondary purpose, we also attempt to restore the time complexity of Grover’s algorithm to its original form, O(), by introducing an O(1) parallel algorithm for unstructured search without repeated items, which will work for most cases. In the worst-case scenarios where the number of repeated items is O(N), the time complexity of the Oracle Phase is still O(N) even after additional preprocessing.
文摘Grovers algorithm is a category of quantum algorithms that can be applied to many problems through the exploitation of quantum parallelism. The Amplitude Amplification in Grovers algorithm is T = O(N). This paper introduces two new algorithms for Amplitude Amplification in Grovers algorithm with a time complexity of T = O(logN), aiming to improve efficiency in quantum computing. The difference between Grovers algorithm and our first algorithm is that the Amplitude Amplification ratio in Grovers algorithm is an arithmetic series and ours, a geometric one. Because our Amplitude Amplification ratios converge much faster, the time complexity is improved significantly. In our second algorithm, we introduced a new concept, Amplitude Transfer where the marked state is transferred to a new set of qubits such that the new qubit state is an eigenstate of measurable variables. When the new qubit quantum state is measured, with high probability, the correct solution will be obtained.
