In this paper we propose a random CSP model, called Model GB, which is a natural generalization of standard Model B. This paper considers Model GB in the case where each constraint is easy to satisfy. In this case Mod...
详细信息
In this paper we propose a random CSP model, called Model GB, which is a natural generalization of standard Model B. This paper considers Model GB in the case where each constraint is easy to satisfy. In this case Model GB exhibits non-trivial behaviour (not trivially satisfiable or unsatisfiable) as the number of variables approaches infinity. A detailed analysis to obtain an asymptotic estimate (good to 1+o(1)) of the average number of nodes in a search tree used by the backtracking algorithm on Model GB is also presented. It is shown that the average number of nodes required for finding all solutions or proving that no solution exists grows exponentially with the number of variables. So this model might be an interesting distribution for studying the nature of hard instances and evaluating the performance of CSP algorithms. In addition, we further investigate the behaviour of the average number of nodes as r (the ratio of constraints to variables) varies. The results indicate that as r increases, random CSP instances get easier and easier to solve, and the base for the average number of nodes that is exponential in n tends to 1 as r approaches infinity. Therefore, although the average number of nodes used by the backtracking algorithm on random CSP is exponential, many CSP instances will be very easy to solve when r is sufficiently large.
Network simulation is an important tool for testing and evaluating wireless sensor network applications. Parallel simulation strategies improve the scalability of these tools. However, achieving high performance depen...
详细信息
Network simulation is an important tool for testing and evaluating wireless sensor network applications. Parallel simulation strategies improve the scalability of these tools. However, achieving high performance depends on reducing the synchronization overhead among simulation processes. In this paper, we present an optimistic simulation algorithm with support for backtracking and re-execution. The algorithm reduces the number of synchronization cycles to the number of transmissions in the network under test. We implement SnapSim, an extension to the popular Avrora simulator, based on this algorithm. The experimental results show that our prototype system improves the performance of Avrora by 2 to 10 times for typical network-centric sensor network applications, and up to three orders of magnitude for applications that use the radio infrequently. We also implement a distributed version of SnapSim, D-SnapSim, which runs on a cluster. The experimental results show that D-SnapSim further improves the performance of SnapSim by up to 10 times for applications that use the radio frequently.
In this paper, we develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which...
详细信息
In this paper, we develop a formalism called a distributed constraint satisfaction problem (distributed CSP) and algorithms for solving distributed CSPs. A distributed CSP is a constraint satisfaction problem in which variables and constraints are distributed among multiple agents. Various application problems in Distributed Artificial Intelligence can be formalized as distributed CSPs. We present our newly developed technique called asynchronous backtracking that allows agents to act asynchronously and concurrently without any global control, while guaranteeing the completeness of the algorithm. Furthermore, we describe how the asynchronous backtracking algorithm can be modified into a more efficient algorithm called an asynchronous weak-commitment search, which can revise a bad decision without exhaustive search by changing the priority order of agents dynamically. The experimental results on various example problems show that the asynchronous weak-commitment search algorithm is, by far more, efficient than the asynchronous backtracking algorithm and can solve fairly large-scale problems.
A detailed description of an improved version of backtracking algorithms for finding t-designs proposed by G. B. Khosrovshahi and the authors of this paper [J Combin Designs 10 (2002),180-194] is presented. The algori...
详细信息
A detailed description of an improved version of backtracking algorithms for finding t-designs proposed by G. B. Khosrovshahi and the authors of this paper [J Combin Designs 10 (2002),180-194] is presented. The algorithm is then used to determine all 5-(14,6,3) designs admitting an automorphism of order 13, 11, or 7. It is concluded that a 5-(14,6,3) design with an automorphism of prime order p exists if and only if p = 2, 3, 7,13. (C) 2003 Wiley Periodicals
Many papers study the natural problem of drawing nonplanar graphs with few crossings per edge. In particular, a graph is 1-planar if it can be drawn in the plane with at most one crossing per edge. Unfortunately, whil...
详细信息
Many papers study the natural problem of drawing nonplanar graphs with few crossings per edge. In particular, a graph is 1-planar if it can be drawn in the plane with at most one crossing per edge. Unfortunately, while testing graph planarity is solvable in linear time and several efficient algorithms have been described in the literature, deciding whether a graph is 1-planar is NP-complete, even for restricted classes of graphs. Despite some polynomial-time algorithms are known for recognizing specific subfamilies of 1-planar graphs, there is still a lack of practical 1-planarity testing algorithms and no implementation is available for general graphs. This paper investigates the feasibility of a 1-planarity testing and embedding algorithm based on a backtracking strategy. Our contribution pro-vides initial indications that have the potential to stimulate further research on the design of practical approaches for the 1-planarity testing problem. On the one hand, our experiments show that a backtracking strategy can be successfully applied to graphs with up to 30 vertices. On the other hand, our study suggests that alternative techniques are needed to attack larger graphs. (C) 2022 Elsevier B.V. All rights reserved.
Identification and control of the pollutant load in sewer networks (SNs) are among the priorities for utilities to reduce the impact on water bodies and to individuate the presence of pathogens to prevent their furthe...
详细信息
Identification and control of the pollutant load in sewer networks (SNs) are among the priorities for utilities to reduce the impact on water bodies and to individuate the presence of pathogens to prevent their further spread, sometimes through interventions on a social scale. This goal can be achieved essentially through the development of a monitoring system. This paper proposes a backtracking methodology for efficiently planning a monitoring system in SNs assuming steady-state conditions during the analysis. The methodology is based on the calculation of the impact coefficient, which is related to the dilution and decay of contaminants and pathogens in the network, to evaluate the impact of each possible contaminated node on a downstream one in terms of concentration. This information supports the identification of candidate monitoring points, i.e., where to place measurement sensors to ensure complete coverage and control of the network. Additional analysis has been performed considering unsteady conditions for comparing the impact coefficient values averaged over 24 h and those of the steady-state methodology. Results show a similar value between steady-state and unsteady conditions, thus justifying the use of steady-state conditions for the proposed methodology, and also for real practical applications, with a significant improvement in terms both of simplicity and computational time saving.
暂无评论