Journal articles: 'Shortest common superstring problem'

1

Gorbenko, Anna, and Vladimir Popov. "The shortest common superstring problem." Applied Mathematical Sciences 7 (2013): 2353–56. http://dx.doi.org/10.12988/ams.2013.13212.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Gorbenko, A., and V. Popov. "On multiple occurrences shortest common superstring problem." Applied Mathematical Sciences 7 (2013): 641–44. http://dx.doi.org/10.12988/ams.2013.13056.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Bilò, Davide, Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, Tobias Mömke, Sebastian Seibert, and Anna Zych. "Reoptimization of the Shortest Common Superstring Problem." Algorithmica 61, no. 2 (June 15, 2010): 227–51. http://dx.doi.org/10.1007/s00453-010-9419-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Popov, V. "On reoptimization of the shortest common superstring problem." Applied Mathematical Sciences 7 (2013): 1195–97. http://dx.doi.org/10.12988/ams.2013.13109.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Laube, Uli, and Maik Weinard. "CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM." International Journal of Foundations of Computer Science 16, no. 06 (December 2005): 1219–30. http://dx.doi.org/10.1142/s0129054105003777.

Full text

Abstract:

We investigate the shortest common superstring problem (SCSSP). As SCSSP is APX-complete it cannot be approximated within an arbitrarily small performance ratio. One heuristic that is widely used is the notorious greedy heuristic. It is known, that the performance ratio of this heuristic is at least 2 and not worse than 4. It is conjectured that the greedy heuristic's performance ratio is in fact 2 (the greedy conjecture). Even the best algorithms introduced for SCSSP can only guarantee an upper bound of 2.5. In [11] an even stronger version of the greedy conjecture is proven for a restricted class of orders in which strings are merged. We extend these results by broadening the class for which this stronger version can be established. We also show that the Triple inequality, introduced in [11] and crucial for their results, is inherently insufficient to carry the proof for the greedy conjecture in the general case. Finally we describe how linear programming can be used to support research along this line.

APA, Harvard, Vancouver, ISO, and other styles

6

Ma, Bin. "Why greed works for shortest common superstring problem." Theoretical Computer Science 410, no. 51 (November 2009): 5374–81. http://dx.doi.org/10.1016/j.tcs.2009.09.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Zaritsky, Assaf, and Moshe Sipper. "Coevolving solutions to the shortest common superstring problem." Biosystems 76, no. 1-3 (August 2004): 209–16. http://dx.doi.org/10.1016/j.biosystems.2004.05.013.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Turner, Jonathan S. "Approximation algorithms for the shortest common superstring problem." Information and Computation 83, no. 1 (October 1989): 1–20. http://dx.doi.org/10.1016/0890-5401(89)90044-8.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Laube, U., and M. Weinard. "ERRATUM: "CONDITIONAL INEQUALITIES AND THE SHORTEST COMMON SUPERSTRING PROBLEM"." International Journal of Foundations of Computer Science 17, no. 01 (February 2006): 247. http://dx.doi.org/10.1142/s0129054106003796.

Full text

APA, Harvard, Vancouver, ISO, and other styles

10

GLOOR, GREG, LILA KARI, MICHELLE GAASENBEEK, and SHENG YU. "TOWARDS A DNA SOLUTION TO THE SHORTEST COMMON SUPERSTRING PROBLEM." International Journal on Artificial Intelligence Tools 08, no. 04 (December 1999): 385–99. http://dx.doi.org/10.1142/s0218213099000269.

Full text

Abstract:

This paper proposes a DNA algorithm for solving an NP-complete problem (The Shortest Common Superstring Problem) by manipulation of biomolecules, and presents partial results of the experiment that implements our algorithm. We also discuss practical constraints that have to be taken into account when implementing the algorithm, propose a coding system as a solution to these practical restrictions, and discuss the control experiments performed for establishing the parameters controlling the specificity of the assay.

APA, Harvard, Vancouver, ISO, and other styles

11

Fici, Gabriele, Tomasz Kociumaka, Jakub Radoszewski, Wojciech Rytter, and Tomasz Waleń. "On the greedy algorithm for the Shortest Common Superstring problem with reversals." Information Processing Letters 116, no. 3 (March 2016): 245–51. http://dx.doi.org/10.1016/j.ipl.2015.11.015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

12

En-hui Yang and Zhen Zhang. "The shortest common superstring problem: average case analysis for both exact and approximate matching." IEEE Transactions on Information Theory 45, no. 6 (1999): 1867–86. http://dx.doi.org/10.1109/18.782108.

Full text

APA, Harvard, Vancouver, ISO, and other styles

13

Ledesma, Lucas, Daniel Manrique, and Alfonso Rodríguez-Patón. "A tissue P system and a DNA microfluidic device for solving the shortest common superstring problem." Soft Computing 9, no. 9 (August 11, 2004): 679–85. http://dx.doi.org/10.1007/s00500-004-0398-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

14

Ledesma, Lucas, Daniel Manrique, and Alfonso Rodríguez-Patón. "A tissue P system and a DNA microfluidic device for solving the shortest common superstring problem." Soft Computing 9, no. 9 (December 1, 2004): 691. http://dx.doi.org/10.1007/s00500-004-0423-2.

Full text

APA, Harvard, Vancouver, ISO, and other styles

15

Kusuma, Wisnu Ananta, and Albert Adrianus. "Pengkontruksian Bidirected Overlap Graph untuk Perakitan Sekuens DNA." Jurnal Teknologi Informasi dan Ilmu Komputer 7, no. 2 (February 18, 2020): 407. http://dx.doi.org/10.25126/jtiik.2020722070.

Full text

Abstract:

De novo DNA (Deoxyribonucleic Acid) sequence assembly atau perakitan sekuens DNA secara De novo adalah tahapan yang sangat penting dalam analisis sekuens DNA. Tahapan ini diperlukan untuk merakit atau menyambungkan kembali fragmen-fragmen DNA (reads) yang dihasilkan oleh Next Generation Sequencing menjadi genom yang utuh. Masalah perakitan DNA ini dapat direpresentasikan sebagai masalah Shortest Common Superstring (SCS). Perakitan ini memerlukan bantuan perangkat lunak untuk mendeteksi daerah yang sama pada reads DNA (overlap), mengkonstruksi overlap graph, dan kemudian mencari shortest path dari graf yang terbentuk. Metode ini dinamakan Overlap Layout Consensus (OLC). Hal yang penting dalam metode OLC adalah pendeteksian overlap dari masing-masing reads. Pada penelitian ini dikembangkan suatu teknik untuk membuat bidirected overlap graph. Suffix array digunakan untuk menentukan bagian overlap dari setiap reads dengan melakukan pengindeksan setiap suffix dari reads. Proses perakitan sekuens DNA merupakan suatu proses komputasi yang intensif. Untuk mengefisiensikan proses dilakukan perubahan masing-masing suffix dan prefix menjadi suatu nilai tertentu yang bersifat tunggal dan mencari overlap dengan membandingkan angka yang merupakan representasi dari setiap reads. Cara ini lebih efisien dibandingkan melakukan pendeteksian overlap dengan metode pencocokan string. Hasil perbandingan menunjukkan bahwa waktu yang diperlukan untuk mengeksekusi metode yang diusulkan (perbandingan angka) jauh lebih singkat dibandingkan dengan menggunakan metode pencocokan string. Untuk jumlah reads 2000 dan 5000 reads teknik yang diusulkan ini dapat menghasilkan overlap graph yang 100% akurat di mana semua reads dapat direpresentasikan ke dalam node yang dikonrtruksi dan semua overlap dapat direpresentasikan ke dalam edge. AbstractDe novo DNA sequence assembly is the important step in DNA sequence analysis. This step is required for assembling fragments or reads produced by Next Generation Sequencing to yield a whole genome. The problem of DNA assembly could be represented as the Shortest Common Superstring (SCS) problem. The assembly requires a software for detecting the overlap region among reads, constructing an overlap graph, and finding the shortest path from the overlap graph.. This method is popular as The Overlap Layout Consensus (OLC). The most important step in OLC is detecting overlaps among reads. This study develop a new approach to construct bidirected overlap graph. Suffis array is used for detecting overlap region from each reads by indexing suffix of each reads. DNA assembly process is computational intensive. To reduce the execution time suffix and prefix was converted into the single value so that the detection of overlap could be done by comparing the values. This method is much more efficient compared to that of using string matching. Using 2000 and 5000 reads, the proposed method (value comparison) could yield the perfect overlap graph, in which all reads and overlap could be represented as nodes and edges, respectively.

APA, Harvard, Vancouver, ISO, and other styles

16

Alexander, Kenneth S. "Shortest common superstrings of random strings." Journal of Applied Probability 33, no. 4 (December 1996): 1112–26. http://dx.doi.org/10.2307/3214990.

Full text

Abstract:

Given a finite collection of strings of letters from a fixed alphabet, it is of interest, in the contexts of data compression and DNA sequencing, to find the length of the shortest string which contains each of the given strings as a consecutive substring. In order to analyze the average behavior of the optimal superstring length, substrings of specified lengths are considered with the letters selected independently at random. An asymptotic expression is obtained for the savings from compression, i.e. the difference between the uncompressed (concatenated) length and the optimal superstring length.

APA, Harvard, Vancouver, ISO, and other styles

17

Alexander, Kenneth S. "Shortest common superstrings of random strings." Journal of Applied Probability 33, no. 04 (December 1996): 1112–26. http://dx.doi.org/10.1017/s002190020010052x.

Full text

Abstract:

Given a finite collection of strings of letters from a fixed alphabet, it is of interest, in the contexts of data compression and DNA sequencing, to find the length of the shortest string which contains each of the given strings as a consecutive substring. In order to analyze the average behavior of the optimal superstring length, substrings of specified lengths are considered with the letters selected independently at random. An asymptotic expression is obtained for the savings from compression, i.e. the difference between the uncompressed (concatenated) length and the optimal superstring length.

APA, Harvard, Vancouver, ISO, and other styles

18

Xikui, Liu, Li Yan, and Xu Jin. "DNA Directed Model for Shortest Superstring Problem." Journal of Computational and Theoretical Nanoscience 8, no. 10 (October 1, 2011): 2112–17. http://dx.doi.org/10.1166/jctn.2011.1933.

Full text

APA, Harvard, Vancouver, ISO, and other styles

19

Plociennik, Kai. "A probabilistic PTAS for shortest common superstring." Theoretical Computer Science 522 (February 2014): 44–53. http://dx.doi.org/10.1016/j.tcs.2013.12.005.

Full text

APA, Harvard, Vancouver, ISO, and other styles

20

Gorbenko, A., and V. Popov. "The swap common superstring problem." Applied Mathematical Sciences 7 (2013): 609–14. http://dx.doi.org/10.12988/ams.2013.13052.

Full text

APA, Harvard, Vancouver, ISO, and other styles

21

Na, Joong Chae, Sukhyeun Cho, Siwon Choi, Jin Wook Kim, Kunsoo Park, and Jeong Seop Sim. "A new graph model and algorithms for consistent superstring problems." Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences 372, no. 2016 (May 28, 2014): 20130134. http://dx.doi.org/10.1098/rsta.2013.0134.

Full text

Abstract:

Problems related to string inclusion and non-inclusion have been vigorously studied in diverse fields such as data compression, molecular biology and computer security. Given a finite set of positive strings and a finite set of negative strings , a string α is a consistent superstring if every positive string is a substring of α and no negative string is a substring of α . The shortest (resp. longest) consistent superstring problem is to find a string α that is the shortest (resp. longest) among all the consistent superstrings for the given sets of strings. In this paper, we first propose a new graph model for consistent superstrings for given and . In our graph model, the set of strings represented by paths satisfying some conditions is the same as the set of consistent superstrings for and . We also present algorithms for the shortest and the longest consistent superstring problems. Our algorithms solve the consistent superstring problems for all cases, including cases that are not considered in previous work. Moreover, our algorithms solve in polynomial time the consistent superstring problems for more cases than the previous algorithms. For the polynomially solvable cases, our algorithms are more efficient than the previous ones.

APA, Harvard, Vancouver, ISO, and other styles

22

Frieze, A., and W. Szpankowski. "Greedy Algorithms for the Shortest Common Superstring That Are Asymptotically Optimal." Algorithmica 21, no. 1 (May 1998): 21–36. http://dx.doi.org/10.1007/pl00009207.

Full text

APA, Harvard, Vancouver, ISO, and other styles

23

Gorbenko, Anna, and Vladimir Popov. "The shortest common parameterized supersequence problem." Applied Mathematical Sciences 7 (2013): 2373–80. http://dx.doi.org/10.12988/ams.2013.13214.

Full text

APA, Harvard, Vancouver, ISO, and other styles

24

Gorbenko, Anna. "The shortest common ordered supersequence problem." Applied Mathematical Sciences 7 (2013): 4813–19. http://dx.doi.org/10.12988/ams.2013.36321.

Full text

APA, Harvard, Vancouver, ISO, and other styles

25

Dondi, Riccardo. "The constrained shortest common supersequence problem." Journal of Discrete Algorithms 21 (July 2013): 11–17. http://dx.doi.org/10.1016/j.jda.2013.03.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

26

Gevezes, Theodoros, and Leonidas Pitsoulis. "A greedy randomized adaptive search procedure with path relinking for the shortest superstring problem." Journal of Combinatorial Optimization 29, no. 4 (May 17, 2013): 859–83. http://dx.doi.org/10.1007/s10878-013-9622-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

27

Gorbenko, Anna, and Vladimir Popov. "On the shortest common parameterized supersequence problem." Applied Mathematical Sciences 7 (2013): 4821–28. http://dx.doi.org/10.12988/ams.2013.36322.

Full text

APA, Harvard, Vancouver, ISO, and other styles

28

Middendorf, M. "The shortest common nonsubsequence problem is NP-complete." Theoretical Computer Science 108, no. 2 (February 1993): 365–69. http://dx.doi.org/10.1016/0304-3975(93)90200-d.

Full text

APA, Harvard, Vancouver, ISO, and other styles

29

Khaled Saifullah, C. M., and Md Rafiqul Islam. "Chemical reaction optimization for solving shortest common supersequence problem." Computational Biology and Chemistry 64 (October 2016): 82–93. http://dx.doi.org/10.1016/j.compbiolchem.2016.05.004.

Full text

APA, Harvard, Vancouver, ISO, and other styles

30

Rahmann, S. "The shortest common supersequence problem in a microarray production setting." Bioinformatics 19, Suppl 2 (September 27, 2003): ii156—ii161. http://dx.doi.org/10.1093/bioinformatics/btg1073.

Full text

APA, Harvard, Vancouver, ISO, and other styles

31

Mousavi, Sayyed Rasoul, Fateme Bahri, and Farzaneh Sadat Tabataba. "An enhanced beam search algorithm for the Shortest Common Supersequence Problem." Engineering Applications of Artificial Intelligence 25, no. 3 (April 2012): 457–67. http://dx.doi.org/10.1016/j.engappai.2011.08.006.

Full text

APA, Harvard, Vancouver, ISO, and other styles

32

Kowalski, Tomasz M., and Szymon Grabowski. "PgRC: pseudogenome-based read compressor." Bioinformatics 36, no. 7 (December 9, 2019): 2082–89. http://dx.doi.org/10.1093/bioinformatics/btz919.

Full text

Abstract:

Abstract Motivation The amount of sequencing data from high-throughput sequencing technologies grows at a pace exceeding the one predicted by Moore’s law. One of the basic requirements is to efficiently store and transmit such huge collections of data. Despite significant interest in designing FASTQ compressors, they are still imperfect in terms of compression ratio or decompression resources. Results We present Pseudogenome-based Read Compressor (PgRC), an in-memory algorithm for compressing the DNA stream, based on the idea of building an approximation of the shortest common superstring over high-quality reads. Experiments show that PgRC wins in compression ratio over its main competitors, SPRING and Minicom, by up to 15 and 20% on average, respectively, while being comparably fast in decompression. Availability and implementation PgRC can be downloaded from https://github.com/kowallus/PgRC. Supplementary information Supplementary data are available at Bioinformatics online.

APA, Harvard, Vancouver, ISO, and other styles

33

Alghamdi, Fahad A., Ahmed Younes Hamed, Abdullah M. Alghamdi, Abderrazak Ben Salah, Tamer Hashem Farag, and Walaa Hassan. "A genetic algorithm for shortest path with real constraints in computer networks." International Journal of Electrical and Computer Engineering (IJECE) 13, no. 1 (February 1, 2023): 435. http://dx.doi.org/10.11591/ijece.v13i1.pp435-442.

Full text

Abstract:

The shortest path problem has many different versions. In this manuscript, we proposed a muti-constrained optimization method to find the shortest path in a computer network. In general, a genetic algorithm is one of the common heuristic algorithms. In this paper, we employed the genetic algorithm to find the solution of the shortest path multi-constrained problem. The proposed algorithm finds the best route for network packets with minimum total cost, delay, and hop count constrained with limited bandwidth. The new algorithm was implemented on four different capacity networks with random network parameters, the results showed that the shortest path under constraints can be found in a reasonable time. The experimental results showed that the algorithm always found the shortest path with minimal constraints.

APA, Harvard, Vancouver, ISO, and other styles

34

Zhou, Yu, Wenfeng Zheng, and Zhixi Shen. "A New Algorithm for Distributed Control Problem with Shortest-Distance Constraints." Mathematical Problems in Engineering 2016 (2016): 1–6. http://dx.doi.org/10.1155/2016/1604824.

Full text

Abstract:

This paper investigates the distributed shortest-distance problem of multiagent systems where agents satisfy the same continuous-time dynamics. The objective of multiagent systems is to find a common point for all agents to minimize the sum of the distances from each agent to its corresponding convex region. A distributed consensus algorithm is proposed based on local information. A sufficient condition also is given to guarantee the consensus. The simulation example shows that the distributed shortest-distance consensus algorithm is effective for our theoretical results.

APA, Harvard, Vancouver, ISO, and other styles

35

Gallardo, José E. "A Multilevel Probabilistic Beam Search Algorithm for the Shortest Common Supersequence Problem." PLoS ONE 7, no. 12 (December 27, 2012): e52427. http://dx.doi.org/10.1371/journal.pone.0052427.

Full text

APA, Harvard, Vancouver, ISO, and other styles

36

Barros, Vanessa, Lingmin Liao, and Jérôme Rousseau. "On the shortest distance between orbits and the longest common substring problem." Advances in Mathematics 344 (February 2019): 311–39. http://dx.doi.org/10.1016/j.aim.2019.01.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

37

Yang, Lifeng, Liangming Chen, Ningwei Wang, and Zhifang Liao. "Routing Optimization Algorithms Based on Node Compression in Big Data Environment." Scientific Programming 2017 (2017): 1–7. http://dx.doi.org/10.1155/2017/2056501.

Full text

Abstract:

Shortest path problem has been a classic issue. Even more so difficulties remain involving large data environment. Current research on shortest path problem mainly focuses on seeking the shortest path from a starting point to the destination, with both vertices already given; but the researches of shortest path on a limited time and limited nodes passing through are few, yet such problem could not be more common in real life. In this paper we propose several time-dependent optimization algorithms for this problem. In regard to traditional backtracking and different node compression methods, we first propose an improved backtracking algorithm for one condition in big data environment and three types of optimization algorithms based on node compression involving large data, in order to realize the path selection from the starting point through a given set of nodes to reach the end within a limited time. Consequently, problems involving different data volume and complexity of network structure can be solved with the appropriate algorithm adopted.

APA, Harvard, Vancouver, ISO, and other styles

38

Luo, Fei, Cheng Chen, Joel Fuentes, Yong Li, and Weichao Ding. "An Opposition-Based Learning CRO Algorithm for Solving the Shortest Common Supersequence Problem." Entropy 24, no. 5 (May 3, 2022): 641. http://dx.doi.org/10.3390/e24050641.

Full text

Abstract:

As a non-deterministic polynomial hard (NP-hard) problem, the shortest common supersequence (SCS) problem is normally solved by heuristic or metaheuristic algorithms. One type of metaheuristic algorithms that has relatively good performance for solving SCS problems is the chemical reaction optimization (CRO) algorithm. Several CRO-based proposals exist; however, they face such problems as unstable molecular population quality, uneven distribution, and local optimum (premature) solutions. To overcome these problems, we propose a new approach for the search mechanism of CRO-based algorithms. It combines the opposition-based learning (OBL) mechanism with the previously studied improved chemical reaction optimization (IMCRO) algorithm. This upgraded version is dubbed OBLIMCRO. In its initialization phase, the opposite population is constructed from a random population based on OBL; then, the initial population is generated by selecting molecules with the lowest potential energy from the random and opposite populations. In the iterative phase, reaction operators create new molecules, where the final population update is performed. Experiments show that the average running time of OBLIMCRO is more than 50% less than the average running time of CRO_SCS and its baseline algorithm, IMCRO, for the desoxyribonucleic acid (DNA) and protein datasets.

APA, Harvard, Vancouver, ISO, and other styles

39

Ziraksima, Mahsa, Shahriar Lotfi, and Habib Izadkhah. "Using an evolutionary approach based on shortest common supersequence problem for loop fusion." Soft Computing 24, no. 10 (September 21, 2019): 7231–52. http://dx.doi.org/10.1007/s00500-019-04338-z.

Full text

APA, Harvard, Vancouver, ISO, and other styles

40

Luo, Fei, Cheng Chen, and Joel Fuentes. "An improved chemical reaction optimization algorithm for solving the shortest common supersequence problem." Computational Biology and Chemistry 88 (October 2020): 107327. http://dx.doi.org/10.1016/j.compbiolchem.2020.107327.

Full text

APA, Harvard, Vancouver, ISO, and other styles

41

Melaouene, Noussaiba, and Rahal Romadi. "An enhanced routing algorithm using ant colony optimization and VANET infrastructure." MATEC Web of Conferences 259 (2019): 02009. http://dx.doi.org/10.1051/matecconf/201925902009.

Full text

Abstract:

For the last fifty years, finding efficient vehicle routes has been studied as a representative logistics problem. In the transportation field, finding the shortest path in a road network is a common problem. VANET presents an innovation opportunity in the transportation field that enables services for intelligent transportation system (ITS) especially communication features. Because of VANET features [1] and despite road obstacles, a route for the shortest path can be established at a given moment. This paper proposes an enhanced algorithm, based on ACO Ant Colony Optimization and related to VANET infrastructure that aims to find the shortest path from the source to destination through the optimal path; in addition, a storage on static nodes is installed in each intersection in a VANET environment and for a specific time.

APA, Harvard, Vancouver, ISO, and other styles

42

Köppl, Dominik. "Inferring Spatial Distance Rankings with Partial Knowledge on Routing Networks." Information 13, no. 4 (March 25, 2022): 168. http://dx.doi.org/10.3390/info13040168.

Full text

Abstract:

The most common problem on routing networks is to compute the shortest paths from a source vertex to a set of target vertices. A variation of it, with applications for recommender systems, asks to merely rank the target vertices with respect to the shortest distances from the source. A classic solution is Dijkstra’s algorithm; however, it is too slow for large but meaningful applications. A setting where the target vertices are fixed but the source vertex is only known at query time allows for preprocessing. Following the line of research on preprocessing the routing network to speed up the computation of shortest paths, we study in this article a novel approach tackling the problem of ranking the static set of target vertices on the routing network with regard to the distance from a given source vertex to these target vertices by leveraging preprocessing. Our approach allows us to generate a partial solution by pre-computing the distances between all targets so that a shortest-path algorithm does not have to determine the shortest path from the source to every target in general. Our proposal can be adopted for both static and time-dependent networks, and it can be used in conjunction with a general shortest-path algorithm. We can experimentally observe significant speed-ups when using our proposed techniques.

APA, Harvard, Vancouver, ISO, and other styles

43

Ahmadi, Saman, Guido Tack, Daniel Harabor, and Philip Kilby. "Weight Constrained Path Finding with Bidirectional A*." Proceedings of the International Symposium on Combinatorial Search 15, no. 1 (July 17, 2022): 2–10. http://dx.doi.org/10.1609/socs.v15i1.21746.

Full text

Abstract:

Weight constrained path finding, known as a challenging variant of the classic shortest path problem, aims to plan cost optimum paths whose weight/resource usage is limited by a side constraint. Given the bi-criteria nature of the problem (i.e., the presence of cost and weight), solutions to the Weight Constrained Shortest Path Problem (WCSPP) have some properties in common with bi-objective search. This paper leverages the state-of-the-art bi-objective search algorithm BOBA* and presents WC-BA*, an exact A*-based WCSPP method that explores the search space in different objective orderings bidirectionally. We also enrich WC-BA* with two novel heuristic tuning approaches that can significantly reduce the number of node expansions in the exhaustive search of A*. The results of our experiments on a large set of realistic problem instances show that our new algorithm solves all instances and outperforms the state-of-the-art WCSPP algorithms in various scenarios.

APA, Harvard, Vancouver, ISO, and other styles

44

Vahidipour, S. Mehdi, Mohammad Reza Meybodi, and Mehdi Esnaashari. "Finding the Shortest Path in Stochastic Graphs Using Learning Automata and Adaptive Stochastic Petri Nets." International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems 25, no. 03 (May 22, 2017): 427–55. http://dx.doi.org/10.1142/s0218488517500180.

Full text

Abstract:

Shortest path problem in stochastic graphs has been recently studied in the literature and a number of algorithms has been provided to find it using varieties of learning automata models. However, all these algorithms suffer from two common drawbacks: low speed and lack of a clear termination condition. In this paper, we propose a novel learning automata-based algorithm for this problem which can speed up the process of finding the shortest path using parallelism. For this parallelism, several traverses are initiated, in parallel, from the source node towards the destination node in the graph. During each traverse, required times for traversing from the source node up to any visited node are estimated. The time estimation at each visited node is then given to the learning automaton residing in that node. Using different time estimations provided by different traverses, this learning automaton gradually learns which neighbor of the node is on the shortest path. To set a condition for the termination of the proposed algorithm, we analyze the algorithm using a recently introduced model, Adaptive Stochastic Petri Net (ASPN-LA). The results of this analysis enable us to establish a necessary condition for the termination of the algorithm. To evaluate the performance of the proposed algorithm in comparison to the existing algorithms, we apply it to find the shortest path in six different stochastic graphs. The results of this evaluation indicate that the time required for the proposed algorithm to find the shortest path in all graphs is substantially shorter than that required by similar existing algorithms.

APA, Harvard, Vancouver, ISO, and other styles

45

Smirnov, Alexander Valeryevich. "The Polynomial Algorithm of Finding the Shortest Path in a Divisible Multiple Graph." Modeling and Analysis of Information Systems 29, no. 4 (December 18, 2022): 372–87. http://dx.doi.org/10.18255/1818-1015-2022-4-372-387.

Full text

Abstract:

In this paper, we study undirected multiple graphs of any natural multiplicity к > 1. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of к linked edges, which connect 2 or (к + 1) vertices, correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common end of к linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of another multi-edge. Divisible multiple graphs are characterized by a possibility to divide the graph into к parts, which are adjusted on the linked edges and which have no common edges. Each part is an ordinary graph. As for an ordinary graph, we can define the integer function of the length of an edge for a multiple graph and set the problem of the shortest path joining two vertices. Any multiple path is a union of к ordinary paths, which are adjusted on the linked edges of all multiple and multi-edges. In the article, we show that the problem of the shortest path is polynomial for a divisible multiple graph. The corresponding polynomial algorithm is formulated. Also we suggest the modification of the algorithm for the case of an arbitrary multiple graph. This modification has an exponential complexity in the parameter к.

APA, Harvard, Vancouver, ISO, and other styles

46

Grabusts, Peter, and Jurijs Musatovs. "THE SEARCH FOR THE SHORTEST ROUTE FOR TOURISTS VISITING SIGHTSEEING OBJECTS OF THE RAZNA NATIONAL PARK." Latgale National Economy Research 1, no. 10 (September 18, 2018): 45. http://dx.doi.org/10.17770/lner2018vol1.10.3457.

Full text

Abstract:

The aim of the paper is to popularize the Razna National Park’s tourist attractions. The opportunity to choose the shortest route to visit all the most interesting potential sightseeing objects is offered. The authors continue their research on the theoretical and practical aspects of searching for the shortest route. Theoretical research has been carried out and mathematically the shortest route has been calculated for various sightseeing objects of the Razna National Park. The paper also provides mapping of these objects and an analysis of the locations of the sightseeing objects at different levels. The main goal of the paper is to show the possibilities of applying mathematical models in solving practical tasks – to determine the shortest route between the sightseeing objects. This research describes an optimization method called Simulated Annealing. The Simulated Annealing method is widely used for various combinatorial optimization tasks. Simulated Annealing is a stochastic optimization method that can be used to minimize the specified cost function given a combinatorial system with multiple degrees of freedom. In this paper, the application of the Travelling Salesman Problem is demonstrated, and an experiment aimed to find the shortest route between the Razna National Park sightseeing objects is performed. Common research methods are used in this research: the descriptive research method, the statistical method, mathematical modelling.

APA, Harvard, Vancouver, ISO, and other styles

47

Bukáček, Michal. "People vs Differential Evolution in Search of The Shortest Path." Journal of Advanced Engineering and Computation 4, no. 3 (September 30, 2020): 207. http://dx.doi.org/10.25073/jaec.202043.292.

Full text

Abstract:

The most common aim of computer game optimisation is to find the shortest path within a game or to solve a problem of a travelling salesman within a small group of cities. This article deals with the possibilities of comparing the ascertained solutions of a given problem of human intelligence and evolutionary algorithms. Human intelligence is represented by mobile game players programmed for the Android operating system, by their conduct during playing the game, and by the achieved the results. Evolutionary algorithms are represented by differential evolution. The best possible parameter estimation will be sought and compared with the player's results. The goal is to nd parameter estimation of an equal or better quality in comparison with results of human players. Another task is to verify whether this setting is suitable for all mazes and whether people or the differential evolution are better at searching. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium provided the original work is properly cited.

APA, Harvard, Vancouver, ISO, and other styles

48

Alani, Sameer, Atheer Baseel, Mustafa Maad Hamdi, and Sami Abduljabbar Rashid. "A hybrid technique for single-source shortest path-based on A* algorithm and ant colony optimization." IAES International Journal of Artificial Intelligence (IJ-AI) 9, no. 2 (June 1, 2020): 356. http://dx.doi.org/10.11591/ijai.v9.i2.pp356-363.

Full text

Abstract:

In the single-source shortest path (SSSP) problem, the shortest paths from a source vertex v to all other vertices in a graph should be executed in the best way. A common algorithm to solve the (SSSP) is the A* and Ant colony optimization (ACO). However, the traditional A* is fast but not accurate because it doesn’t calculate all node's distance of the graph. Moreover, it is slow in path computation. In this paper, we propose a new technique that consists of a hybridizing of A* algorithm and ant colony optimization (ACO). This solution depends on applying the optimization on the best path. For justification, the proposed algorithm has been applied to the parking system as a case study to validate the proposed algorithm performance. First, A*algorithm generates the shortest path in fast time processing. ACO will optimize this path and output the best path. The result showed that the proposed solution provides an average decreasing time performance is 13.5%.

APA, Harvard, Vancouver, ISO, and other styles

49

Plonski, Patrick A., and Volkan Isler. "Approximation algorithms for tours of height-varying view cones." International Journal of Robotics Research 38, no. 2-3 (July 31, 2018): 224–35. http://dx.doi.org/10.1177/0278364918784353.

Full text

Abstract:

We introduce a novel coverage problem that arises in aerial surveying applications. The goal is to compute a shortest path that visits a given set of cones. The apex of each cone is restricted to lie on the ground plane. The common angle [Formula: see text] of the cones represent the field of view of the onboard camera. The cone heights, which can be varying, correspond with the desired observation quality (e.g. resolution). This problem is a novel variant of the traveling salesman problem with neighborhoods (TSPN). We name it Cone-TSPN. Our main contribution is a polynomial time approximation algorithm for Cone-TPSN. We analyze its theoretical performance and show that it returns a solution whose length is at most [Formula: see text] times the length of the optimal solution where [Formula: see text] and [Formula: see text] are the heights of the tallest and shortest input cones, respectively.We demonstrate the use of our algorithm in a representative precision agriculture application. We further study its performance in simulation using randomly generated cone sets. Our results indicate that the performance of our algorithm is superior to standard solutions.

APA, Harvard, Vancouver, ISO, and other styles

50

Ding, Mei-Shuang, Ning-De Jin, and Zhong-Ke Gao. "Modality transition-based network from multivariate time series for characterizing horizontal oil–water flow patterns." International Journal of Modern Physics C 26, no. 03 (February 25, 2015): 1550034. http://dx.doi.org/10.1142/s0129183115500345.

Full text

Abstract:

The simultaneous flow of oil and water through a horizontal pipe is a common occurrence during petroleum industrial processes. Characterizing the flow behavior underlying horizontal oil–water flows is a challenging problem of significant importance. In order to solve this problem, we carry out experiment to measure multivariate signals from different flow patterns and then propose a novel modality transition-based network to analyze the multivariate signals. The results suggest that the local betweenness centrality and weighted shortest path of the constructed network can characterize the transitions of flow conditions and further allow quantitatively distinguishing and uncovering the dynamic flow behavior underlying different horizontal oil–water flow patterns.

APA, Harvard, Vancouver, ISO, and other styles

Journal articles on the topic 'Shortest common superstring problem'

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles