This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log^3n) time with n processors. The algorithms uses a divide and conquer approach and is base...This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log^3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.展开更多
In this figure, it finds a vertex to another vertex k shortest path algorithm. Provided there are n vertices and edges in the diagram. If the path loops, the time complexity of the algorithm is allowed O（w ＋ n log 2...In this figure, it finds a vertex to another vertex k shortest path algorithm. Provided there are n vertices and edges in the diagram. If the path loops, the time complexity of the algorithm is allowed O（w ＋ n log 2 n ＋ kw log 2 k）. If the request path does not contain the loop, the time complexity of the algorithm O（kn（w ＋ n log2 n）＋ kw log2 k）. The algorithm utilizes a simple extension of the Dijkstra algorithm determined the end of the length of the shortest path to the other vertices, and then, based on these data, branch and bound method to identify the required path. Experimental results show that the actual running time has relations with the structure of FIG.展开更多
Stope mining design is a very important and complicated task in daily production design and technical management of an underground mine.Based on workface technology and human-computer interaction technology,this study...Stope mining design is a very important and complicated task in daily production design and technical management of an underground mine.Based on workface technology and human-computer interaction technology,this study introduces a method of 3D parametric design for the irregular structure of stope bottoms,and focuses on solving technical problems in surface modeling of stope bottom structure.Optimization of the minimum span length algorithm(MSLA) and the shortest path search algorithm(SPSA) is conducted to solve the problem of contour-line based instant modeling of stope bottom structures,which makes possible the 3D parametric design for irregular structure of stope bottom.Implementation process and relevant methods of the proposed algorithms are also presented.Feasibility and reliability of the proposed modeling method are testified in a case study.In practice,the proposed 3 D parameterization design method for irregular structure stope bottom proves to be very helpful to precise 3D parametric design.This method is capable of contributing to improved efficiency and precision of stope design,and is worthy of promotion.展开更多
After analyzing the merits and shortcomings of Fixed-Alternated Routing algorithm (FAR) and Least Loaded Routing algorithm (LLR),we propose one novel dynamic optical routing algorithm. Having considered the influences...After analyzing the merits and shortcomings of Fixed-Alternated Routing algorithm (FAR) and Least Loaded Routing algorithm (LLR),we propose one novel dynamic optical routing algorithm. Having considered the influences of path’s length and path’s congestion just like in FAR and LLR,we take into account the network resource status-amount of free wavelengths in the network. Proposed algorithm sets up connections on three possible paths according to amount of available free wave-lengths in the network,which effectively decreases the blocking probability. The National Science Foundation (NSF) network and mesh-torus network simulation results show that the performance of this algorithm is better than that of FAR and LLR.展开更多
A k-shortest path based algorithm considering layout density and signal integrity for good buffer candidatelocations is proposed in this paper. Theoretical results for computing the maximal distance betweenbuffers are...A k-shortest path based algorithm considering layout density and signal integrity for good buffer candidatelocations is proposed in this paper. Theoretical results for computing the maximal distance betweenbuffers are derived under the timing, noise and slew rate constraints. By modifying the traditional uniformwire segmenting strategy and considering the impact of tile size on density penalty function, this work proposesk-shortest path algorithm to find the buffer insertion candidate locations. The experiments show thatthe buffers inserted can significantly optimize the design density, alleviate signal degradation, save thenumber of buffers inserted and the overall run time.展开更多
Simulated annealing(SA) algorithm is a heuristic algorithm,proposed one approximation algorithm of solving optimization combinatorial problems inspired by objects in the annealing process of heating crunch. The algori...Simulated annealing(SA) algorithm is a heuristic algorithm,proposed one approximation algorithm of solving optimization combinatorial problems inspired by objects in the annealing process of heating crunch. The algorithm is superior to the traditional greedy algorithm,which avoids falling into local optimum and reaches global optimum. There are often some problems to find the shortest path,etc in the logistics and distribution network, and we need optimization for logistics and distribution path in order to achieve the shortest,best,most economical,and so on. The paper uses an example of SA algorithm validation to verify it,and the method is proved to be feasible.展开更多
This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linea...This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.展开更多
Signal Detection Theory （SDT） offers an unparalleled deterministic set of decision variables necessary to formulate applied risks in transportation. SDT has distinct advantages over basic prediction models since the...Signal Detection Theory （SDT） offers an unparalleled deterministic set of decision variables necessary to formulate applied risks in transportation. SDT has distinct advantages over basic prediction models since the latter may not represent an entirely accurate analysis. Thresholds based on elements of stimulus （signal and noise） and response for： a Type I discrimination of response variable where decision outcomes and rates are computed for metacognition to discriminate a Type II of decision outcomes was set. We also adapted the classical Dijkstra＇s shortest path algorithm within a GIS environment using Avenue programming. Contours derived from LiDARwere used to set flood levels while satellite imagery corresponding to Red River of the North inundated （signal） areas were acquired amongst other spatial datasets. The signal information was further dichotomized using a binary yes-no model. Origin and destination points constrained within Fargo-Morehead were generated using a random point generator. From these points, trips were generated with some connected segments traversing through flooded areas. By analyzing False Alarm Rate （FAR） and Corrected Rejection （CRR） computation, we found out that, when Hit Rate （HR） and FAR are both low then there was an increased corresponding sensitivity. At 30-35 ft flood level, the values for FAR and HR was 0.97 and 0.91 respectively.When FAR〉HR, lower set flood levels offered numerous route choices. Corresponding routes with associated impedance can be classified for risk-averse drivers or risk-takers While the risk-averse avoid risky and unfavorable routes, the risk-taker optimizes at an adjustment factor of ω = 0.1 or ω = 0.2. An idealistic stage is achieved for a conservative, co, equal to 0.4 or 0.5, which indicates maximum achievement in terms of time gain and safety simultaneously. At ω = 0.0 the prevailing conditions can be considered unrealistic since they incorporate areas considered impassable with absolute resistance like segments with a ＂Road Closed＂ or ＂Detour＂ sign. The applicability of our approach can be used to design multi-level and multi-modal transportation systems involving risk.展开更多
Traditional sensor network and robot navigation are based on the map of detecting the fields available in advance. The optimal algorithms are developed to solve the energy saving, the shortest path problems, etc. Howe...Traditional sensor network and robot navigation are based on the map of detecting the fields available in advance. The optimal algorithms are developed to solve the energy saving, the shortest path problems, etc. However, in the practical enviroranent, there are many fields, whose map is difficult to get, and needs to be detected. In this paper a kind of ad-hoc navigation algorithm is explored, which is based on the hybrid sensor network without the prior map in advance. The navigation system is composed of static nodes and dynamic trades. The static nodes monitor the occurrances of the events and broadcast them. In the syston, a kind of algorithm is to locate the rdbot, which is based on duster broadcasting. The dynamic nodes detect the adversary or dangerous fields and broadcast warning messages. The robot gets the message and follows ad-hoc routine to arrive where the events occur. In the whole process, energy saving has been taken into account. The algorithms, which are based on the hybrid sensor network, are given in this paper. The simulation and practical results are also available.展开更多
文摘This paper presents an efficient parallel algorithm for the shortest path problem in planar layered digraphs that runs in O(log^3n) time with n processors. The algorithms uses a divide and conquer approach and is based on the novel idea of a one-way separator, which has the property that any directed path can be crossed only once.
文摘In this figure, it finds a vertex to another vertex k shortest path algorithm. Provided there are n vertices and edges in the diagram. If the path loops, the time complexity of the algorithm is allowed O（w ＋ n log 2 n ＋ kw log 2 k）. If the request path does not contain the loop, the time complexity of the algorithm O（kn（w ＋ n log2 n）＋ kw log2 k）. The algorithm utilizes a simple extension of the Dijkstra algorithm determined the end of the length of the shortest path to the other vertices, and then, based on these data, branch and bound method to identify the required path. Experimental results show that the actual running time has relations with the structure of FIG.
基金Supported by the National High Technology Research and Development Programme of China(No.2011AA060407)Yunnan Province Science and Technology Innovation Platform Construction Plans,China(No.2010DH005)
文摘Stope mining design is a very important and complicated task in daily production design and technical management of an underground mine.Based on workface technology and human-computer interaction technology,this study introduces a method of 3D parametric design for the irregular structure of stope bottoms,and focuses on solving technical problems in surface modeling of stope bottom structure.Optimization of the minimum span length algorithm(MSLA) and the shortest path search algorithm(SPSA) is conducted to solve the problem of contour-line based instant modeling of stope bottom structures,which makes possible the 3D parametric design for irregular structure of stope bottom.Implementation process and relevant methods of the proposed algorithms are also presented.Feasibility and reliability of the proposed modeling method are testified in a case study.In practice,the proposed 3 D parameterization design method for irregular structure stope bottom proves to be very helpful to precise 3D parametric design.This method is capable of contributing to improved efficiency and precision of stope design,and is worthy of promotion.
文摘After analyzing the merits and shortcomings of Fixed-Alternated Routing algorithm (FAR) and Least Loaded Routing algorithm (LLR),we propose one novel dynamic optical routing algorithm. Having considered the influences of path’s length and path’s congestion just like in FAR and LLR,we take into account the network resource status-amount of free wavelengths in the network. Proposed algorithm sets up connections on three possible paths according to amount of available free wave-lengths in the network,which effectively decreases the blocking probability. The National Science Foundation (NSF) network and mesh-torus network simulation results show that the performance of this algorithm is better than that of FAR and LLR.
基金Supported by the National Key Project of Scientific and Technical Supporting Programs (No. 2006BAK07B04).
文摘A k-shortest path based algorithm considering layout density and signal integrity for good buffer candidatelocations is proposed in this paper. Theoretical results for computing the maximal distance betweenbuffers are derived under the timing, noise and slew rate constraints. By modifying the traditional uniformwire segmenting strategy and considering the impact of tile size on density penalty function, this work proposesk-shortest path algorithm to find the buffer insertion candidate locations. The experiments show thatthe buffers inserted can significantly optimize the design density, alleviate signal degradation, save thenumber of buffers inserted and the overall run time.
基金National Natural Science Foundation of China(No.50574037)Henan Soft Science Research Project(No.102400410033No.102400410032)
文摘Simulated annealing(SA) algorithm is a heuristic algorithm,proposed one approximation algorithm of solving optimization combinatorial problems inspired by objects in the annealing process of heating crunch. The algorithm is superior to the traditional greedy algorithm,which avoids falling into local optimum and reaches global optimum. There are often some problems to find the shortest path,etc in the logistics and distribution network, and we need optimization for logistics and distribution path in order to achieve the shortest,best,most economical,and so on. The paper uses an example of SA algorithm validation to verify it,and the method is proved to be feasible.
文摘This paper presents an efficient parallel algorithm for the shortest-path problem in interval graph for computing shortest-paths in a weighted interval graph that runs in O(n) time with n intervals in a graph. A linear processor CRCW algorithm for determining the shortest-paths in an interval graphs is given.
文摘Signal Detection Theory （SDT） offers an unparalleled deterministic set of decision variables necessary to formulate applied risks in transportation. SDT has distinct advantages over basic prediction models since the latter may not represent an entirely accurate analysis. Thresholds based on elements of stimulus （signal and noise） and response for： a Type I discrimination of response variable where decision outcomes and rates are computed for metacognition to discriminate a Type II of decision outcomes was set. We also adapted the classical Dijkstra＇s shortest path algorithm within a GIS environment using Avenue programming. Contours derived from LiDARwere used to set flood levels while satellite imagery corresponding to Red River of the North inundated （signal） areas were acquired amongst other spatial datasets. The signal information was further dichotomized using a binary yes-no model. Origin and destination points constrained within Fargo-Morehead were generated using a random point generator. From these points, trips were generated with some connected segments traversing through flooded areas. By analyzing False Alarm Rate （FAR） and Corrected Rejection （CRR） computation, we found out that, when Hit Rate （HR） and FAR are both low then there was an increased corresponding sensitivity. At 30-35 ft flood level, the values for FAR and HR was 0.97 and 0.91 respectively.When FAR〉HR, lower set flood levels offered numerous route choices. Corresponding routes with associated impedance can be classified for risk-averse drivers or risk-takers While the risk-averse avoid risky and unfavorable routes, the risk-taker optimizes at an adjustment factor of ω = 0.1 or ω = 0.2. An idealistic stage is achieved for a conservative, co, equal to 0.4 or 0.5, which indicates maximum achievement in terms of time gain and safety simultaneously. At ω = 0.0 the prevailing conditions can be considered unrealistic since they incorporate areas considered impassable with absolute resistance like segments with a ＂Road Closed＂ or ＂Detour＂ sign. The applicability of our approach can be used to design multi-level and multi-modal transportation systems involving risk.
基金supported by the National nature Science Fund(No.50875247)
文摘Traditional sensor network and robot navigation are based on the map of detecting the fields available in advance. The optimal algorithms are developed to solve the energy saving, the shortest path problems, etc. However, in the practical enviroranent, there are many fields, whose map is difficult to get, and needs to be detected. In this paper a kind of ad-hoc navigation algorithm is explored, which is based on the hybrid sensor network without the prior map in advance. The navigation system is composed of static nodes and dynamic trades. The static nodes monitor the occurrances of the events and broadcast them. In the syston, a kind of algorithm is to locate the rdbot, which is based on duster broadcasting. The dynamic nodes detect the adversary or dangerous fields and broadcast warning messages. The robot gets the message and follows ad-hoc routine to arrive where the events occur. In the whole process, energy saving has been taken into account. The algorithms, which are based on the hybrid sensor network, are given in this paper. The simulation and practical results are also available.
