Search

International audience; In the context of exascale programming, we investigate a parallel distributed productivity-aware tree-search for exact optimization in Chapel. To this end, we present the DistBag-DFS distributed data structure, which is our revisited version of the Chapel’s DistBag data structure for depth-first search. The latter implements a distributed multi-pool, as well as an underlying locality-aware load balancing mechanism. Extensive experiments on large unbalanced tree-based problems are performed, and the competitiveness of our approach is reported against MPI+X implementations in terms of performance. For our best results, we achieve 94% of the ideal speed-up, using up to 64 computer nodes (8192 cores).

We present an algorithm for constructing a depth-first search tree in planar digraphs; the algorithm can be implemented in the complexity class AC^1(UL∩co-UL), which is contained in AC². Prior to this (for more than a quarter-century), the fastest uniform deterministic parallel algorithm for this problem was O(log^{10}n) (corresponding to the complexity class AC^{10} ⊆ NC^{11}). We also consider the problem of computing depth-first search trees in other classes of graphs, and obtain additional new upper bounds., LIPIcs, Vol. 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021), pages 7:1-7:22

We present the first parallel depth-first search algorithm for undirected graphs that has near-linear work and sublinear depth. Concretely, in any n-node m-edge undirected graph, our algorithm computes a DFS in Õ(g√n) depth and using Õ (m + n) work. All prior work either required ω(n) depth, and thus were essentially sequential, or needed a high poly(n) work and thus were far from being work-efficient., SPAA '23: Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures, ISBN:978-1-4503-9545-8

The Link-a-Pix puzzle, which is also known as Piczle , PathPix , Pictlink , Number Net , or Paint by Pairs , is a popular picture logic puzzle game where the player paints a grid by linking the hint points with number–color labels to obtain the solution as a pixel art picture. In this article, we propose a joint depth first searching and linear programming aided algorithm for the sake of automatically solving the Link-a-Pix puzzle. The experiments implemented on 40 puzzles with various types verify the effectiveness and feasibility of our proposed solver, which is conducive to both designing and solving the Link-a-Pix puzzles and related applications.

We investigated the computational power of a single mobile agent in an $n$-node graph with storage (i.e., node memory). Generally, a system with one-bit agent memory and $O(1)$-bit storage is as powerful as that with $O(n)$-bit agent memory and $O(1)$-bit storage. Thus, we focus on the difference between one-bit memory and oblivious (i.e., zero-bit memory) agents. Although their computational powers are not equivalent, all the known results exhibiting such a difference rely on the fact that oblivious agents cannot transfer any information from one side to the other across the bridge edge. Hence, our main question is as follows: Are the computational powers of one-bit memory and oblivious agents equivalent in 2-edge-connected graphs or not? The main contribution of this study is to answer this question under the relaxed assumption that each node has $O(\log\Delta)$-bit storage (where $\Delta$ is the maximum degree of the graph). We present an algorithm for simulating any algorithm for a single one-bit memory agent using an oblivious agent with $O(n^2)$-time overhead per round. Our results imply that the topological structure of graphs differentiating the computational powers of oblivious and non-oblivious agents is completely characterized by the existence of bridge edges., Comment: 14 pages, 2 figures

Digital mammography acts as a unique screening technology to protect the lives of females against breast cancer for the past few decades. Mammographic breast density is a well-known biomarker and plays a substantial role in breast cancer prediction and treatments. Breast density is calculated based on the opacity of fibro-glandular tissue reflected on digital mammograms concerning the whole area of the breast. The opacity of pectoral muscle and fibro-glandular tissue is similar to each other; hence, the small presence of the pectoral muscle in the breast area can hamper the accuracy of breast density classification. Successful removal of pectoral muscle is challenging due to changes in shape, size, and texture of pectoral muscle in every MLO and LMO views of mammogram. In this article, the depth-first search (DFS) algorithm is proposed to remove artifacts and pectoral muscle from digital mammograms. In the proposed algorithm, image enhancement is performed to improve the pixel quality of the input image. The whole breast as a single connected component is identified from the background region to remove the artifacts and tags. The depth-first search method with and without the heuristic approach is used to delineate the pectoral muscle, and then final suppression is performed on it. This algorithm is tested on 2675 images of the DDSM dataset, which is further divided into four density classes as per BIRADs classification. Segmentation results are calculated individually on each BIRADs density class of the DDSM dataset. Results are validated subjectively by the expert's Radiologist's ground truth with segmentation accuracy and objectively by the Jaccard coefficient and a dice similarity coefficient. This algorithm is found robust on each density class and provides overall segmentation accuracy of 86.18%, a mean value of Jaccard index, and a Dice similarity coefficient of 0.9315 and 0.9548, respectively. The experimental results show that the proposed algorithms applied for pectoral muscle removal follow the ground truth marked by an expert radiologist. The proposed algorithm can be part of the pre-processing unit of breast density measurement and breast cancer detection system used during clinical practice.

A graph-theoretical algorithm based on the depth-first search (DFS) procedure of graph analysis is proposed for determining a complete set of homodesmic reactions (HDRs) of organic compounds. The complete set of HDRs is constructed decomposing the molecular graph of a compound into a series of simpler components. Based on the resulting DFS algorithm, a program for plotting the HDR basis is devised that includes automated generation of the structures of homodesmic reaction participants and primary thermochemical analysis (i.e., calculating the heat effects of HDRs from absolute enthalpies of reactants obtained via user-selected quantum chemistry). The work of the algorithm is illustrated by the example of vinylcyclopropane. The use of complete sets of HDRs for the thermochemical analysis of molecular energetics is studied to determine its advantages: high precision; the possibility of controlling the reproducibility of data and screening out inconsistent or erroneous thermochemical data; quantitative consideration of the nonvalence structural effects in organic compounds; and block analysis of the thermochemistry of structurally similar organic compounds, which is analogous to the familiar concept of active thermochemical tables.

Vehicular communication technology keeps promising to reduce the current road accidents and introduce smarter, safer, and more seamless ground transportation system. The wide deployment of 5G cellular network, supported with device-to-device (D2D) technology, can afford a good solution to enhance vehicular communication performance. The main challenges here are to guarantee reliability for all vehicle-to-vehicle (V2V) links while maximizing ergodic capacity for all vehicles-to-infrastructure (V2I) links and maximizing network's utilization. This paper offers a promising solution for all mentioned challenges in efficient runtime. Two mechanisms for allocating powers to transmitting nodes are proposed. These mechanisms are MAX-mechanism and OPT-mechanism. Moreover, an analytical model is proposed to share the available resources among nodes, where multiple V2V links should share the same channel with a V2I link. Then depth first search tree (DFST) algorithm is proposed to distribute all nodes on available resources in efficient runtime. Finally, simulation results are presented showing the performance enhancement of proposed solutions.

Pathfinder algorithm (PFA) for finding the best food area or prey based on the leadership of collective action in animal groups is a new metaheuristic algorithm for solving optimization problems with different structures. PFA is divided into two stages to search: pathfinder stage and follower stage. They represent the exploration phase and mining phase of PFA respectively. However, the original algorithm also has the problem of falling into a local optimum. In order to solve this problem, the teaching phase in the teaching and learning algorithm is added to the pathfinder stage in the text. In order to balance the exploration and mining capabilities of the algorithm, the learning phase of the teaching and learning algorithm is added to the follower phase in the article. In order to further enhance the depth search ability of the algorithm and increase the convergence speed, the exponential step is given to the followers. Therefore, a teaching-learning-based pathfinder algorithm (TLPFA) is proposed. 19 benchmark functions of four different types and six engineering design problems are used to test of the TLPFA exploration and exploiting capabilities. The experimental results show that the proposed TLPFA algorithm is superior to the state-of-the-art metaheuristic algorithms in terms of the performance measures.

The presented work in this paper deals with various step sizes used in incremental conductance (INC) related to the maximum power point tracking (MPPT) technique. In the solar photovoltaic system, the variable step size selection method for INC is proposed and compared. The MATLAB/Simulink and hardware setup are used for assessing and analyzing step size methods. The variable step size (DVS), fixed step size (DFS) are comprehensively studied and compared. This DVS method is having a lower ON delay time $\left ({{T_{d_{ON}}} }\right)$ as 148 msec as regard to 164 msec in the DFS method. On the other hand, the lowest peak-peak oscillations in load current as 0.04 amp for DVS as compared to 0.5A for the DFS method, lower peak current as 1.96A for DVS as compare to 2.37A for the DFS method. In this way, the performance of the DVS method is found superior as it is analyzed and compared with the DFS algorithm.

Предлагаемый в настоящей работе теоретико-графовый алгоритм для анализа энергетики химических соединений основан на гомодесмическом подходе. В работе описаны основные этапы конструирования базисного набора гомодесмических реакций. Работа алгоритма проиллюстрирована на молекуле метилциклобутан. В разработанной программе для построения гомодесмических реакций использовался метод поиска в глубину DFS. Application of the DFS Algorithm to the Homodesmic Analysis of Chemical Compounds The graph-theoretic algorithm proposed in this work for the analysis of the energetics of chemical compounds is based on the homodesmic approach. The paper describes the main stages of constructing a basic set of homodesmic reactions. The operation of the algorithm is illustrated on the methylcyclobutane molecule. In the developed program for constructing homodesmic reactions, the DFS depth-first search method was used.

In this paper, a data-driven method is proposed for fast cascading outage screening in power systems. The proposed method combines a deep convolutional neural network (deep CNN) and a depth-first search (DFS) algorithm. First, a deep CNN is constructed as a security assessment tool to evaluate system security status based on observable information. With its automatic feature extraction ability and the high generalization, a well-trained deep CNN can produce estimated AC optimal power flow (ACOPF) results for various uncertain operation scenarios, i.e., fluctuated load and system topology change, in a nearly computation-free manner. Second, a scenario tree is built to represent the potential operation scenarios and the associated cascading outages. The DFS algorithm is developed as a fast screening tool to calculate the expected security index value for each cascading outage path along the entire tree, which can be a reference for system operators to take predictive measures against system collapse. The simulation results of applying the proposed deep CNN and the DFS algorithm on standard test cases verify their accuracy, and the computational efficiency is thousands of times faster than the model-based traditional approach, which implies the great potential of the proposed algorithm for online applications.

This paper proposes a new algorithm for detecting and generating simple circuits within a directed graph. Before generating all simple circuits in a directed graph, the algorithm first detects whether there is a simple circuit in directed graph, and the detection can divide the directed graph into trivial graphs or strongly connected components. In the process of detecting the existence of simple circuit, the algorithm repeatedly reduces the number of vertices in vertex set along with edge pruning. Based on depth-first traversal, we can get all simple circuits of the directed graph. Especially, instead of proceeding depth-first traversals based on all vertices, the algorithm starts with a random vertex in a strongly connected component to reduce the number of depth-first traversals, and obtain all simple circuits of this strongly connected component. The difficulty of the algorithm is to detect and delete the repeated circuits in the process of generating all simple circuits, which can reduce both the storage space and time complexity. As a result, the output of the algorithm does not contain any repeated circuits. The algorithm simplifies the edge set of directed graphs and greatly reduces the number of depth-first traversals, thereby reducing the computational complexity and improving the computational efficiency.

High utility itemset (HUI) mining identifies an interesting pattern from transactional databases by taking into consider the utility of each in the transaction for instance, margins or profits. Many candidates are generated for HUIs which reduces the mining performance. Frequent pattern-growth (FP-Growth) algorithm was widely used to discover the frequent itemsets using FP-Tree. But, UP-Tree was constructed to store high utility item set. The mining of UP-Tree by FP-Growth extracts high utility itemset and generates too many candidates. So, UP-Growth and UP-Growth+ was proposed to shorten the candidate itemsets. In UP-Growth, two tactics such as discarding local unpromising items (DLU) and decreasing local node (DLN) were used in FP-Growth. In UP-Growth+, two strategies such as DLU and its estimated node utilities (DNU) and DLN tools for the nodes of internal UP-Tree by evaluated the descendant nodes (DNN) were incorporated in FP-Growth. However, the UP-Growth and UP-Growth+ has the problem of poor spatial and temporal localities. Initially, the UP-Tree is created in available main memory then extended to secondary memory when the transaction is large. The storage of data structure in secondary memory and accessibility is not clearly derived in existing algorithms. In this paper, the spatial locality issues of UP-Growth and UP-Growth+ is solved by rearranging nodes of UP-Tree in a depth first manner and temporal locality issues of UP-Growth and UP-Growth+ is solved by page blocking technique which reorganizes the execution part of UP-Growth and UP-Growth+. The computational part is rearranged. In addition to, the memory management strategy is introduced to minimize the space requirement of high utility itemsets. Thus the proposed Improved Adaptive UP-Growth (IAUP-Growth) and Improved Adaptive UP-Growth+ (IAUP-Growth+) overcomes the spatial and temporal locality problem and effectively reduces the memory usage.

We present an analysis of the depth-first search algorithm in a random digraph model with geometric outdegree distribution. We give also some extensions to general outdegree distributions. This problem posed by Donald Knuth in his next to appear volume of The Art of Computer Programming gives interesting insight in one of the most elegant and efficient algorithm for graph analysis due to Tarjan., LIPIcs, Vol. 225, 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022), pages 11:1-11:15

This paper studies the multi-depot joint distribution vehicle routing problem considering energy consumption with time-dependent networks (MDJDVRP-TDN). Aiming at the multi-depot joint distribution vehicle routing problem where the vehicle travel time depends on the variation characteristics of the road network speed in the distribution area, considering the influence of the road network on the vehicle speed and the relationship between vehicle load and fuel consumption, a multi-depot joint distribution vehicle routing optimization model is established to minimize the sum of vehicle fixed cost, fuel consumption cost and time window penalty cost. Traditional vehicle routing problems are modeled based on symmetric graphs. In this paper, considering the influence of time-dependent networks on routes optimization, modeling is based on asymmetric graphs, which increases the complexity of the problem. A hybrid genetic algorithm with variable neighborhood search (HGAVNS) is designed to solve the model, in which the nearest neighbor insertion method and Logistic mapping equation are used to generate the initial solution firstly, and then five neighborhood structures are designed to improve the algorithm. An adaptive neighborhood search times strategy is used to balance the diversification and depth search of the population. The effectiveness of the designed algorithm is verified through several groups of numerical instances with different scales. The research can enrich the relevant theoretical research of multi-depot vehicle routing problems and provide the theoretical basis for transportation enterprises to formulate reasonable distribution schemes.

Cache efficiency is an important factor in the performance of graph processing due to the irregular memory access patterns caused by the sparse nature of graphs. To increase the cache hit rate, prior studies proposed a variety of preprocessing approaches based on the reordering, which permutes the vertexes’ labels to improve the locality of graph structures. However, the locality enhancement of existing reordering approaches does not bring much performance benefit in depth-first traversal, which is widely adopted in a majority of graph processing applications. Furthermore, the state-of-the-art reordering approach suffers from an obvious overhead on preprocessing which will greatly limit the application of their approach. In this paper, we propose SeqDFS, a depth-first graph traversal method that optimizes the cache efficiency by adjusting the order of vertexes visited and can be further extended to dynamic scenarios. We conduct extensive experiments on 16 real-world datasets and 3 representative depth-first graph applications, of which the results show that our proposal achieves a significant speed-up on both directed and undirected graphs.

Problem ovog završnog rada je bio proširiti postojeću digitalnu igru s alatom za ispitivanje rješivosti razina i prikaz njihovih rješenja. U igri se osim igranja razina mogu uređivati i dodavati i nove s pomoću alata Level Editor. Cilj rada bio je dodati novi alat za provjeru rješivosti razina i prikaz tog rješenja. Do rješenja razina se dolazi pretraživanjem prostora stanja. Za pretraživanje prostora stanja postoje razni algoritmi. U ovom radu obrađeni su algoritam Depth-First Search (DFS) i njegova manja modifikacija. The topic of this thesis was to extend the existing digital game with a tool to examine the solvability of the levels and display their solutions. In the game, in addition to playing levels, one can also edit and add new levels by using the Level Editor tool. A new tool was added to check the solvability of levels and display this solution. The solution of the levels is reached by searching the state space. There are various algorithms for searching the state space. The Depth-First Search (DFS) algorithm and its minor modification are discussed.

Selection of threshold values to generate nonredundant filtered images in attribute profiles (APs) is an unresolved issue. This paper presents a novel filtering approach to the construction of APs that does not require the definition of any threshold value. The proposed approach creates a max-tree (or min-tree), traverse to the first encountered leaf node using depth first traversal, and defines a leaf attribute function (LAF) to demonstrate the changes in attribute values from leaf to root node. The LAF is analyzed based on a novel criterion to automatically detect the node along the path that has a first significant difference in the attribute value. All its descendant nodes are merged to it and the process is repeated for each unvisited leaf node to create the final filtered tree which is transformed back as a filtered image. The proposed approach can incorporate maximum spatial information by applying a few filtering operations without the need to define any threshold value. This is of great importance in spectral–spatial classification applications. Moreover, since the proposed approach requires one depth first traversal to generate a filtered image, it is very efficient in terms of computation time. To show the effectiveness of the proposed method, three real hyperspectral data sets are considered and the results are compared to the state-of-the-art method considering five different attributes. The results show that the proposed method has several important advantages with respect to the existing threshold-based filtering techniques. Furthermore, the proposed method is also effective when compared with different spectral–spatial classification techniques.

The layout is displayed in one of the most complex tasks in the gravity pipe network project because there are several factors to consider and often a choice of unassociated or smaller layout. Currently, the designer’s experience is needed so different layout alternatives be analyzed to reduce the depths of the network. Generally, this operation is manual and does not ensure the best result. For this research, a depth-first search algorithm was presented, which allows the optimization of the layout of a gravity pipe network, assessing the topographic conditions of the manholes (nodes), leading to a layout that has the sum of lower unfavorable slopes. A hypothetical and a real network were used. The computational time required was considered negligible. The results showed a robust model, which works for the complete layout of any network, of any size, resulting in the lowest possible depths.

Depth first search (DFS) tree is a fundamental data structure for solving graph problems. The classical algorithm [SiComp74] for building a DFS tree requires $O(m+n)$ time for a given graph $G$ having $n$ vertices and $m$ edges. Recently, Baswana et al. [SODA16] presented a simple algorithm for updating DFS tree of an undirected graph after an edge/vertex update in $\tilde{O}(n)$ time. However, their algorithm is strictly sequential. We present an algorithm achieving similar bounds, that can be adopted easily to the parallel environment. In the parallel model, a DFS tree can be computed from scratch using $m$ processors in expected $\tilde{O}(1)$ time [SiComp90] on an EREW PRAM, whereas the best deterministic algorithm takes $\tilde{O}(\sqrt{n})$ time [SiComp90,JAlg93] on a CRCW PRAM. Our algorithm can be used to develop optimal (upto polylog n factors deterministic algorithms for maintaining fully dynamic DFS and fault tolerant DFS, of an undirected graph. 1- Parallel Fully Dynamic DFS: Given an arbitrary online sequence of vertex/edge updates, we can maintain a DFS tree of an undirected graph in $\tilde{O}(1)$ time per update using $m$ processors on an EREW PRAM. 2- Parallel Fault tolerant DFS: An undirected graph can be preprocessed to build a data structure of size O(m) such that for a set of $k$ updates (where $k$ is constant) in the graph, the updated DFS tree can be computed in $\tilde{O}(1)$ time using $n$ processors on an EREW PRAM. Moreover, our fully dynamic DFS algorithm provides, in a seamless manner, nearly optimal (upto polylog n factors) algorithms for maintaining a DFS tree in semi-streaming model and a restricted distributed model. These are the first parallel, semi-streaming and distributed algorithms for maintaining a DFS tree in the dynamic setting., Comment: Accepted to appear in SPAA'17, 32 Pages, 5 Figures

In an active towed array sonar, it is important to find the optimal operation depth. Generally, the optimal depth can be chosen via numerical simulations for all sonar depths and this imposes great burdens of time and cost.In this paper, an efficient approach is proposed to find the optimal depth using the optimisation technique. First, the sonar performance function is newly defined as a measure of how well the active sonar might perform. This function depends on the properties of the ocean environment and the positions of sonar and underwater target. Then, the simulated annealing to find an optimal solution for maximising sonar performance is used. The optimised depth agrees well with the depth obtained from direct searching for all depths of source and receiver combinations, but its computational time is largely reduced.

Convolutional neural networks (CNNs) now also start to reach impressive performance on non-classification image processing tasks, such as denoising, demosaicing, super-resolution, and super slow motion. Consequently, CNNs are increasingly deployed on very high-resolution images. However, the resulting high-resolution feature maps pose unseen requirements on the memory system of neural network processing systems, as on-chip memories are too small to store high-resolution feature maps, while off-chip memories are very costly in terms of I/O bandwidth and power. This paper first shows that the classical layer-by-layer inference approaches are bounded in their external I/O bandwidth versus on-chip memory tradeoff space, making it infeasible to scale up to very high resolutions at a reasonable cost. Next, we demonstrate how an alternative depth-first network computation can reduce I/O bandwidth requirements up to >200× for a fixed on-chip memory size or, alternatively, reduce on-chip memory requirements up to >10000× for a fixed I/O bandwidth limitation. We further introduce an enhanced depth-first method, exploiting both line buffers and tiling, to further improve the external I/O bandwidth versus on-chip memory capacity tradeoff and quantify its improvements beyond the current state of the art. ispartof: IEEE Journal on Emerging and Selected Topics in Circuits and Systems vol:9 issue:2 pages:323-331 status: Published online

Companion vehicle discovery received much attention from the research community. It has been widely adopted by traffic management departments in many aspects such as the involved vehicle tracking. Since there are a massive amount of traffic data that have complex and inaccurate accompanying vehicle relationships, companion vehicle discovery has become a challenge yet hot research topic. Several algorithms have been proposed to solve this issue on transactional datasets some of which are based on the frequent item mining algorithms that are used to extract knowledge from data in several real-world applications, such as market basket analysis, crime detection/prevention, and crowd mining. However, most of those algorithms mostly fail on large-scale datasets since it needs to scan the datasets iteratively for several times, which makes them unfeasible and time-consuming while dealing with big data. To this end, we proposed a novel HD-FIM algorithm to extract the companion vehicles from a massive amount of traffic data with the best execution efficiency on spark platform. It works in a hybrid approach between depth first and breadth first to handle the big data in distributed clusters. Experiment results show that the proposed algorithm, HD-FIM, outperforms the existing typical frequent itemset mining algorithms through practical vehicle set extraction calculations and it can be applied in any applicable traffic big data.

Arabic is one of the international languages and the language of the Qur'an widely used in Islam. Learning basic Arabic is important because the language is the foundation of learning Islam. The fault in determining the verb form will relate to wrong meaning. Overcoming the problem, Shorof is a part of the linguistic arabic used to determine the form and utility of a word. Shorof Praktis Krapyak is one of the shorof books that has been widely used by students in Indonesia because of its reliability and simplicity in recognizing the form of Arabic words. The research was conducted to build a system to determine the Arabic verb forms and their utilities by implementing the Depth First Search (DFS) algorithm. DFS is a blind search algorithm in the artificial intelligent discussion that represents a problem into states, generates them systematically and tests them until a goal state is found. Rules made in recognizing the verb form refer to the Shorof Praktis Krapyak which the system is implemented in an Android application. The test results showed that the system can recognize 100 word samples with 100% accuracy. In functionality, all of 30 respondents said that test results stated that the system can run properly. The usability test of the system stated that 55.0% of respondents strongly agreed, 41.6% are agreed and 3.3% choose neutral that this system can help them to recognize and analyze the verb forms in Arabic words.

Spoken term detection (STD) refers to discovering all occurrences of a given term in a set of speech utterances. One of the well-known approaches for the STD system is the phone lattice search (PLS) that produces a phone-based lattice of speech utterances. Since the accuracy of a phone recognizer affects the accuracy of the STD system, the PLS approach utilizes the minimum edit distance (MED) measure to compensate the phone recognizer errors. While this measure increases the detection rate, it also raises the false alarm rate. In this paper, we consider the PLS approach as the baseline. Then, we use Viterbi scoring and Jaro-Winkler similarity measure in order to decrease the false alarm rate. Since the proposed approach uses more techniques than the baseline approach, the search speed may decrease. To overcome this problem, we use lattice pruning and indexing techniques such as depth first search algorithm to increase the search speed in online and offline applications, respectively. We report the experimental results for monophone-based and triphone-based STD system. The results indicate that using triphone-based STD system improved the performance about 2% in comparison with monophone-based STD system. Moreover, when we used triphone-based models, the proposed approach including MED measure, Viterbi scores and Jaro-Winkler similarity measure improved the accuracy of the method with only MED measure, about 17%.

Aiming at the multi-depot heterogeneous vehicle routing problem under the time-dependent road network and soft time window, considering vehicle fixed cost, time window penalty cost and vehicle transportation cost, an optimization model of time-dependent multi-depot heterogeneous vehicle routing problem is established with the objective of minimizing distribution cost. According to the characteristics of the problem, a hybrid genetic algorithm with variable neighborhood search considering the temporal–spatial distance is designed. Customers are clustered according to the temporal–spatial distance to generate initial solutions, which improves the quality of the algorithm. The depth search capability of the variable neighborhood search algorithm is applied to the local search strategy of the genetic algorithm to enhance the local search capability of the algorithm. An adaptive neighborhood search number strategy and a new acceptance mechanism of simulated annealing are proposed to balance the breadth and depth required for population evolution. The validity of the model and algorithm is verified by several sets of examples of different scales. The research results not only deepen and expand the relevant research on vehicle routing problem, but also provide theoretical basis for logistics enterprises to optimize distribution scheme.

In the high-efficiency video coding standard, the division process of coding units is an optimal depth search process. Due to the block method of the quadtree, the depth selection process of the coding unit will consume a lot of coding time. This paper proposes an algorithm for fast selection of coding unit depth based on the minimum risk Bayesian criterion. It uses huge database information to learn Bayesian threshold and Bayesian conditional probability density offline, establishes a look-up table, and selects the most Excellent subset of coding features. This algorithm can effectively reduce the time for the current coding unit to select depth. The experimental results show that compared with the standard test software HM16.16, this algorithm saves 41.8% of the total coding time on average.

Various path or route solving algorithms have been widely researched for the last 30 years. It has been applied in many different robotic systems such as bomb sniffing robots, path exploration and search rescue operation. For instance, an autonomous robot has been used to locate and assist a person trapped in the jungle or building to exit. Today, numerous maze solving algorithms have been proposed based on the some information available regarding the maze or remotely control. In real scenario, a robot is usually placed in an unknown environment. It is required for the robot to learn the path, and exhibit a good decision making capability in order to navigate the path successfully without human’ assistance. In this project, an Artificial Intelligence (AI) based algorithm called Recursive Backtracking Depth First Search (RBDS) is proposed to explore a maze to reach a target location, and to take the shortest route back to the start position. Due to the limited energy and processing resource, a simple search tree algorithm has been proposed. The proposed algorithm has been evaluated in a robot that has the capability to keep track of the path taken while trying to calculate the optimum path by eliminating unwanted path using Cul-de-Sac technique. Experimental results have shown that the proposed algorithm can solve different mazes. The robot has also shown the capability to learn and remember the path taken, to return to the start and back to target area successfully.

With the increasing complexity of distribution network structure originated from high penetration of renewable energy and responsive loads, fast and accurate fault location technology of distribution network is a prerequisite for rapid isolation of faults and restoration of power supply. In this paper, a fault location method based on community graph depth-first traversal is proposed for fast location of single-phase ground faults in distribution network. First, this paper defines the fault graph weight of the vertices in the distribution network graph model, which are used to reflect the topology of the vertices and fault points as well as the fluctuation of the vertices' currents. Then, the vertices on the graph model are clustered by using an improved parallel louvain method (IPLM). Finally, the community formed by IPLM is used as the smallest unit for depth-first traversal to achieve fast and accurate location of the fault section. The paper builds the distribution network graph model of IEEE 33-bus system on the graph database for testing. And three other methods were selected for comparison with IPLMDF. The test results show that IPLMDF can achieve fast and accurate fault location when half of the nodes in the distribution network are equipped with D-PMUs. When some of the D-PMUs lose time synchronization, it is still possible to locate the fault section, and at the same time, the locating results can be avoided to fall into local optimal solutions.

Storage of secure records and recovering is one of the most bursting investigations heading in cloud computing. In spite of the way that various available encryption plans have been proposed, very few of them support profitable recuperation over the records which are encoded reliant on their characteristics. Currently, progressive quality based encryption model is intended for a record collection. A lot of records can be encoded together on the off chance that they share an integrated access structure. For improving the search viability DFS algorithm is used for the ARF tree. It can be further improved using cloud computing. Our system can be implemented for the purpose of document collection by slightly modifying the ARF tree.

The Split-Radix Fast Fourier Transform has the same low arithmetic complexity as the related Conjugate Pair Fast Fourier Transform. Both transforms have an irregular datapath structure which is straightforwardly expressed only in recursive forms. Furthermore, the conjugate pair variant has a complicated input indexing pattern which requires existing iterative implementations to rely on precomputed tables. It however allows optimization of the memory bandwidth as it requires a single twiddle factor load per radix-4 butterfly. In existing algorithms, this comes at the cost of using additional precomputed tables or performing recursive function calls. In this paper we present two novel approaches that handle both the butterfly scheduling and the input index generation of the Conjugate Pair Fast Fourier Transform. The proposed algorithm is cache-friendly because it is depth-first, non-recursive and does not rely on precomputed index tables. In order to achieve this, we relate the butterfly execution pattern of the Split-Radix and Conjugate Pair FFTs to the binary carry sequence. Based on this finding, we describe how common integer arithmetic and bitwise operations can be used to perform input reordering and depth-first traversal of the transform datapath with O(1) space complexity.

GPGPU (General-Purpose Graphics Processing Unit) consists of hardware resources that can execute tens of thousands of threads simultaneously. However, in reality, the parallelism is limited as resource allocation is performed by the base unit called thread block, which is not managed judiciously in the current GPGPU systems. To schedule threads in GPGPU, a specialized hardware scheduler allocates thread blocks to the computing unit called SM (Stream Multiprocessors) in a Round-Robin manner. Although scheduling in hardware is simple and fast, we observe that the Round-Robin scheduling is not efficient in GPGPU, as it does not consider the workload characteristics of threads and the resource balance among SMs. In this article, we present a new thread block scheduling model that has the ability of analyzing and quantifying the performances of thread block scheduling. We implement our model as a GPGPU scheduling simulator and show that the conventional thread block scheduling provided in GPGPU hardware does not perform well as the workload becomes heavy. Specifically, we observe that the performance degradation of Round-Robin can be eliminated by adopting DFA (Depth First Allocation), which is simple but scalable. Moreover, as our simulator consists of modular forms based on the framework and we publicly open it for other researchers to use, various scheduling policies can be incorporated into our simulator for evaluating the performance of GPGPU schedulers.

Artificial intelligent techniques provide different kind of searching methods in tree structure and those methods are implemented sequential and parallel manner using structured programming. Depth-first search is a tree search algorithm which enables the traversal from source node to neighbour nodes adjacent to source node in a graph and implemented sequentially in this fashion. The improvement of the sequential Depth-first search is sought in several research studies. One of the solutions to the improvement of Depth-first search is the design of multi agent system for the searching problem. In this research study, the proposed multi agent system for Depth-first search divides the entire graph into several clusters using bi-connected region method and consigns the agents to each cluster to perform the Depth-first search sequentially. The proposed method reveals the significance improvement in terms of the performance measure of the system than sequential Depth-first search.

In recent years, the application of automated guided vehicles (AGVs) in industrial manufacture has attracted more and more attention. Based on reinforcement learning, an automated guided logistics handling vehicles routing algorithm was proposed under a multi-task scenario. First, the algorithm calculated routing paths for each task node using Q-learning to solve the “curse of dimensionality” problem. Then, with the objective of comprehensive cost considering the time window, the optimal routing sequence was obtained using the depth first search algorithm (DFS). Finally, an example is given to illustrate the algorithm.

Convolutional neural networks (CNNs) have been playing an important role in various applications, e.g., computer vision. Since CNN computations require numerous multiply-accumulate (MAC) operations, how to get them done efficiently is a crucial issue for CNN hardware accelerators. In this paper, we propose a high-speed power-efficient convolver architecture for CNN acceleration. A 3×3 convolver is asked to produce an output every cycle and is commonly accomplished by summing up the results of nine parallel multiplications, which requires ten carry-propagation adders (CPAs) in total. However, the proposed coarse-grained convolver can break the boundary between multipliers and reduce all partial products in a more global way. Consequently, it requires only one CPA to generate the final outcome. It also features a globally delay-optimized partial product reduction tree and a depth-first compression scheme for both area and power minimization. The proposed convolver has been implemented using TSMC 40nm technology. Compared to a conventional 3×3 convolver baseline design, our design can reduce area and power by 15.8% and 26.5% respectively at the clock rate of 1GHz.

The requirements of the ensuing software provided by the client are studied by software developers before the preparation of the project charter. The schedule, cost and person-days estimation are made by the developer using an activity chart. This activity chart is transformed into the graphical form using standard semiotics then manually the critical path, i.e. least long path from start to end is identified. This procedure may have several shortfalls (i) Time-consuming (ii) Manual process. In addition to this, a manual process is an error-prone approach. When the number of activities is increased, the determination of the critical path is a herculean task. In such a case, there is quintessence to develop an automated methodology that determines the critical path. This paper contains a proposed automated methodology for the determination of the critical path through a modified depth-first search (DFS) algorithm. Instead of activity chart representation, we have transformed the tabular information of dependencies and time taken by each activity into n × n matrix form and then developed an algorithm to compute critical path it takes time complexity of O(n2).

Computer games are divided into complete information games and incomplete information games. Military chess games, as a kind of incomplete information games, have shortcomings in many aspects. In view of the fact that the game tree of the military chess game in the middle and late stages of attacking the banner is too large, this paper proposes an algorithm for deep searching the chessboard according to the military chess rules. In this paper, the bidirectional deep search algorithm is adopted, which reduces the time needed to calculate the approximate optimal solution by nearly 97% compared with using the algorithm of two-way deep search. Compared with the original depth search algorithm, the algorithm in this paper is highly optimized in terms of time complexity. The experiment shows that the search algorithm based on deep search can reduce the operation time of each step and achieve good results.

U suparničkim igrama za više igrača važno je donositi ispravne odluke u stvarnom vremenu. U igri Zatacka, to se odnosi na odabir trajektorije koja osigurava najduže preživljavanje i ostvarivanje što boljeg konačnog rezultata. Algoritam pretraživanja korišten za planiranje je pretraživanje u dubinu s ograničenom dubinom. Algoritam na temelju početne pozicije agenta određuje moguće pozicije do kojih agent može doći u budućnosti. Na temelju ukupnog broja skretanja potrebnih za dolazak do svake buduće pozicije određuje se najsigurniji put kojim se agent treba kretati. Making the right decisions in real time is one of the most important things in adversarial multiplayer games. In the game called Zatacka, this refers to the selection of the trajectory that ensures the longest survival and the best possible final result. The search algorithm used for planning is Depth-first search with limited depth. Based on the initial position of the agent, the algorithm determines positions that the agent may reach in the future. Based on the total number of turns required to reach each future position, the safest route for the agent to move is determined.

Passenger behavior analysis is a key issue in passenger assignment research, in which the path choice is a fundamental component. A highly complex transit network offers multiple paths for each origin&ndash, destination (OD) pair and thus resulting in more flexible choices for each passenger. To reflect a passenger&rsquo, s flexible choice for the transit network, the optimal strategy was proposed by other researchers to determine passenger choice behavior. However, only strategy links have been searched in the optimal strategy algorithm and these links cannot complete the whole path. To determine the paths for each OD pair, this study proposes the depth-first path generation algorithm, in which a strategy node concept is newly defined. The proposed algorithm was applied to the Beijing metro network. The results show that, in comparison to the shortest path and the K-shortest path analysis, the proposed depth-first optimal strategy path generation algorithm better represents the passenger behavior more reliably and flexibly.

To improve the flocking convergence speed for completing some emergent tasks, e.g. search and rescue in an accident, this paper proposes a novel fast convergent flocking control method for multi-agent systems with switching communication topology. First, a new distributed per-step convergence factor (D-PCF) is defined to indicate flocking convergence speed of each agent, whose summation indicates the overall convergence speed of multi-agent systems. Then, to decrease the D-PCF and thus increase the flocking convergence speed of the overall multi-agent system, a new distributed fast synchronization (DFS) algorithm is developed to determine position-dependent and velocity-dependent adjacency weights on every communication channel of an ad hoc network with switching topologies. The simulation results show that compared with a conventional flocking control, the flocking control using the DFS algorithm with switching communication topology can significantly increase the flocking convergence speed without requiring larger control inputs.

This paper designs a Distributed Arithmetic Coding (DAC) decoder using the depth-first search method. In addition, a method is proposed to control the decoder complexity. Simulation results compare the DFD with the traditional Breadth-First Decoder (BFD) showing that under the same complexity constraints, the DFD outperforms the BFD when the code length is not too long and the quality of side information is not too poor.

Evolution of Phasor Measurement Units (PMU) improves the power system estimator’s performance. PMUs are widely use in transmission systems and by considering its contribution there, it is expected that in future it will be used in distribution networks. First and foremost step towards implementation of micro-PMUs in distribution system is to determine optimal location of µPMUs. Since PMUs are generally used in transmission systems so mostly algorithms related to optimal placement (OPP) are not considered the radial structure of distribution network. In this piece of work, Traditional Depth Search Algorithm and a Proposed Modified Depth Search Algorithm are adopted to solve judicious µPMU placement problem. Proposed Methods are tested on 40 and 85 IEEE radial distribution feeder, randomly integrated with distributed energy resources. Results obtained indicated that proposed algorithm overcomes the drawback of depth first search algorithm of not providing optimal solution.

In a range-dependent and time-varying environment, such as at the Shallow Water 2006 (SW06) experimental site, matched field processing often has difficulty localizing a moving source emitting a narrowband signal when signal mismatch is difficult to mitigate given only the nominal sound speed profile and bottom properties along the source track. Based on the range-averaged mode wavenumbers and depth functions estimated from data received on a vertical line array by synthetic beamforming (without any environmental information) using Doppler shift as a reference, a method is proposed in this paper to search for the source depth first and then the source range. Source localization is demonstrated with the SW06 data for two source runs along and oblique to the shelf. Robustness is achieved by minimizing/breaking the coupling between range and depth, when one of them can be estimated using non-environment-related input.

In the interest of privacy concerns, cloud service users choose to encrypt their personal data before outsourcing them to cloud. However, it is difficult to achieve efficient search over encrypted cloud data. Therefore, how to design an efficient and accurate search scheme over large-scale encrypted cloud data is a challenge. In this paper, we integrate bisecting k-means algorithm and multibranch tree structure and propose the α-filtering tree search scheme based on bisecting k-means clusters. The novel index tree is built from bottom-up, and a greedy depth first algorithm is used for filtering the nonrelevant document cluster by calculating the relevance score between the filtering vector and the query vector. The α-filtering tree can improve the efficiency without the loss of search accuracy. The experiment on a real-world dataset demonstrates the effectiveness of our scheme.

The lexicographic depth-first search (Lex-DFS) is one of the first basic graph problems studied in the context of space-efficient algorithms. It is shown independently by Asano et al. [ISAAC 2014] and Elmasry et al. [STACS 2015] that Lex-DFS admits polynomial-time algorithms that run with O(n)-bit working memory, where n is the number of vertices in the graph. Lex-DFS is known to be P-complete under logspace reduction, and giving or ruling out polynomial-time sublinear-space algorithms for Lex-DFS on general graphs is quite challenging. In this paper, we study Lex-DFS on graphs of bounded treewidth. We first show that given a tree decomposition of width O(n^(1-ε)) with ε > 0, Lex-DFS can be solved in sublinear space. We then complement this result by presenting a space-efficient algorithm that can compute, for w ≤ √n, a tree decomposition of width O(w √nlog n) or correctly decide that the graph has a treewidth more than w. This algorithm itself would be of independent interest as the first space-efficient algorithm for computing a tree decomposition of moderate (small but non-constant) width. By combining these results, we can show in particular that graphs of treewidth O(n^(1/2 - ε)) for some ε > 0 admits a polynomial-time sublinear-space algorithm for Lex-DFS. We can also show that planar graphs admit a polynomial-time algorithm with O(n^(1/2+ε))-bit working memory for Lex-DFS.

In these days enterprises are using cloud space to keep their data. This practice saves the cost of hardware purchasing and maintenance as well as infrastructure cost. Although privacy and security of the data are the important issues because the cloud server is either un-trusted or semi trusted. Various methods and schemes have been used to achieve the objective of data security and privacy. To keep data safe and secure, data is encrypted before uploading at cloud space. Therefore to search particular information at cloud space the plaintext keyword searching method is obsolete. The new method for searching the data upon cloud is searching upon encrypted data. The authors proposed here a multi keyword rank search scheme, which returns top most relevant documents as an output of search. The tf x idf model as well as vector space model is used to form the table that keeps the index and queries. For encryption of index and query kNN algorithm can be used. The authors have formed a tree known as M way balanced search (MBS) for search and indexing in a better way. The authors also proposed a dfsm (depth first searching method) scheme for multi key synonym rank search. The certainty and efficiency of dfsm is scalable but MBS tree is taking sub linear time complexity. For calculating the complexity computational methods were used.

Decision trees play an important role both in Machine Learning and Knowledge Representation. They are attractive due to their immediate interpretability. In the spirit of Occam’s razor, and interpretability, it is desirable to calculate the smallest tree. This, however, has proven to be a challenging task and greedy approaches are typically used to learn trees in practice. Nevertheless, recent work showed that by the use of SAT solvers one may calculate the optimal size tree for real-world benchmarks. This paper proposes a novel SAT-based encoding that explicitly models paths in the tree, which enables us to control the tree’s depth as well as size. At the level of individual SAT calls, we investigate splitting the search space into tree topologies. Our tool outperforms the existing implementation. But also, the experimental results show that minimizing the depth first and then minimizing the number of nodes enables solving a larger set of instances.

We show that the profile of the tree constructed by the Depth First Search Algorithm in the giant component of an Erd\H{o}s-R\'enyi graph with $N$ vertices and connection probability $c/N$ converges to an explicit deterministic shape. This makes it possible to exhibit a long non-intersecting path of length $\left( \rho_c - \frac{\mathrm{Li}_2(\rho_c)}{c} \right) \times N$, where $\rho_c$ is the density of the giant component., Comment: 16 pages, 3 figures