Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 26 for “"Backtracking search"”.
-
Some Enhancement Methods For Backtracking-Search In Solving Multiple Permutation Problems
… we present some enhancement methods for backtracking-search in solving multiple permutation problems. Some well-known NP-complete multiple permutation problems are Quasigroup Completion Problem and Sudoku. Multiple permutation problems have been getting a lot of attention in the …
-
AN EMPIRICAL STUDY OF DIFFERENT BRANCHING STRATEGIES FOR CONSTRAINT SATISFACTION PROBLEMS
… constraint satisfaction problems <i>(CSPs)</i>. Backtracking search algorithms are usually employed to solve <i>CSPs</i> and in backtracking search the choice of branching strategies can be critical since they specify how a search algorithm can instantiate a variable and how a problem can be …
-
Kakuro Solver Application
… Sudoku. Kakuro puzzles are NP-complete, where a search is effective to find solutions. Therefore among those algorithms, KakuroSolver employs the backtracking search along with several techniques that minimizes the search to increase the efficiency. The architecture of the application is also …
-
LLM-based exhaustive generation of data structures
… on imperative validity predicates and systematic backtracking search. This report empirically investigates whether large language models (LLMs) can serve as reliable bounded enumerators, given only a natural-language specification of the data structure and its invariants. We evaluate four …
-
A schema & constraint-based representation to understanding natural language
… as their inappropriateness is discovered. Thus, backtracking search which is known to be inefficient is avoided.
-
Randomization and Restart Strategies
… satisfiability problems (SAT) using systematic backtracking search has been shown to exhibit great variability. Randomization and restarts is an effective technique for reducing such variability to achieve better expected performance. Several restart strategies have been proposed and studied in …
-
On the Limits and Practice of Automatically Designing Self-Stabilization
… addresses this concern and, using a complete backtracking search, has automatically designed 4 new self-stabilizing protocols with minimal process space requirements: 2-state maximal matching on bidirectional rings, 5-state token passing on unidirectional rings, 3-state token passing on …
-
Program analysis techniques for algorithmic complexity and relational properties
… that combines reinforcement learning with backtracking search. A common theme among all these solutions is to exploit problem-specific structures and adapt existing techniques to exploit those structures accordingly.
-
Novel Value Ordering Heuristics Using Non-Linear Optimization In Boolean Satisfiability
… SAT is most commonly solved by a form of backtracking search which systematically explores the space of possible variable assignments. We show that the order in which variable polarities are assigned can have a significant impact on the performance of backtracking algorithms. We present …
-
Metodologias para a simulação simultânea dos três componentes de acelerogramas sísmicos
… utilizam um método de otimização evolutiva, o Backtracking Search Optimization Algorithm, para determinar os parâmetros apropriados de cada modelo para a geração simultânea dos três componentes da aceleração do solo.
-
Domain value mutation and other techniques for constraint satisfaction problems
… Solving a CSP usually requires chronological backtracking search that interleaves variable assignments with various kinds of inferences in order to reduce the search space. This dissertation comprises two parts. The first part deals with a modification of the classical CSP model that allows a …
-
MKorat : a novel approach for memorizing the Korat search and some potential applications
… as imperative predicates and implements a backtracking search that prunes large parts of the input space and enumerates all non-isomorphic inputs within a given bound on input size. Despite the effectiveness of Korat’s pruning, systematically creating and running large numbers of tests can …
-
Detecção de dano em estruturas utilizando identificação modal estocástica e um algoritmo de otimização
… de um algoritmo de otimização conhecido como Backtracking Search Algorithm (BSA) fazendo uso de uma função objetivo que utiliza as frequências naturais e modos de vibração identificados da estrutura. Simulações e testes são feitos a fim de verificar a concordância da metodologia para ambos os …
-
Backward-Korat : improving Korat search to enable backward input space exploration
… the desired ones. Korat performs a systematic backtracking search for input space exploration based on pruning and isomorphism breaking. The Korat search gains part of its efficiency by monitoring executions of the given predicate on candidate inputs and creating new candidates based on the …
-
Exploiting Structure in Backtracking Algorithms for Propositional and Probabilistic Reasoning
… reasoning represent two core problems in AI. Backtracking based algorithms have been applied in both problems. In this thesis, I investigate structure-based techniques for solving real world SAT and Bayesian networks, such as software testing and medical diagnosis instances. When solving a SAT …
-
Compression and cryptology
… the literature. In particular, it is shown how a backtracking search can be used for known and chosen plaintext attacks against fixed to variable length binary encoders (Huffman coding and splaying). It is shown how a good model of the source (a PPM model) can be used in an automatic ciphertext …
-
Adaptive strategies for solving contraint satisfaction problems
… CSPs have attracted the interest of many researchers. General speaking a strategy that uses the results of its own search experience to modify its subsequent behavior does adaptive search In this dissertation we explore adaptive strategies for backtracking search on various levels. First, we …
-
Searching for Simple Symmetric Venn Diagrams
… of these diagrams are introduced and different backtracking search algorithms are provided based on these representations. Using these algorithms we show that there are 39,020 non-isomorphic simple monotone 6-Venn diagrams in total. In the case of drawing Venn diagrams on a sphere, we prove that …
-
Enhancing the Reliability of Power Distribution Networks
… complexity, compromising reliability. This research focuses on efficiently identifying grid faults, minimizing outages, and reducing financial losses by accelerating restoration and optimizing PV penetration levels. The first contribution is a fault location method utilizing data from existing …
-
Enhancements to solving constraints written as imperative predicates
… focus is the Korat solver, which introduced a backtracking search algorithm to enumerate all object graphs that satisfy user given constraints (provided as a runnable check using an imperative language) within user given bounds. Korat has been applied to various applications including bounded …
Page 1 of 2