In this paper we present a classical parallel quantum algorithm for the satisfiability problem. We have exploited the classical parallelism of quantum algorithms developed in [G.L. Long and L. Xiao, Phys. Rev. A 69 （...In this paper we present a classical parallel quantum algorithm for the satisfiability problem. We have exploited the classical parallelism of quantum algorithms developed in [G.L. Long and L. Xiao, Phys. Rev. A 69 （2004） 052303], so that additional acceleration can be gained by using classical parallelism. The quantum algorithm first estimates the number of solutions using the quantum counting algorithm, and then by using the quantum searching algorithm, the explicit solutions are found.展开更多
In order to facilitate solution, a complex problem is normally decomposed into many small sub-problems during product development process. Teams are formed to resolve each sub-problem. The original problem is resolved...In order to facilitate solution, a complex problem is normally decomposed into many small sub-problems during product development process. Teams are formed to resolve each sub-problem. The original problem is resolved from solutions of sub-problems. Ideally, sub-problems are not only mutually independent but also inherent parameters of original problem. Solution of original problem can be directly derived from the collection of solutions from simplified sub-problems. In practice, the degree of interdependency is indeed reduced, sub-problems are neither totally independent nor all inherent parameters of original problem. This paper discusses team coordination under this condition and design solution from each team, which not only satisfies total requirements but also is an optimal one. The suggested optimized constraint decomposition method will insure workable Pareto solution.展开更多
The Balanced Academic Curriculum Problem （BACP） is a constraint satisfaction problem classified as （Non-deterministic Polynomial-time Hard） NP-Hard. This problem consists in the allocation of courses in the period...The Balanced Academic Curriculum Problem （BACP） is a constraint satisfaction problem classified as （Non-deterministic Polynomial-time Hard） NP-Hard. This problem consists in the allocation of courses in the periods that are part of a curriculum such that the prerequisites are satisfied and the load of courses is balanced for the students. This paper presents the solution for a modified BACP where the academic loads and number of curses may be the same or different for each one of the periods and allows having some courses in a specific period. This problem is modeled as an integer programming problem and is proposed the use of Tabu search with short-term memory for its solution because it is not possible to find solutions for all the instances of this modified problem with an exact method.展开更多
The number of scientific investigations on women＇s football specific to the topics of player characteristics and demands of the game has considerably increased in recent years due to the increased popularity of the w...The number of scientific investigations on women＇s football specific to the topics of player characteristics and demands of the game has considerably increased in recent years due to the increased popularity of the women＇s game worldwide, although they are not yet as numerous as in the case of men＇s football. To date, only two scientific publications have attempted to review the main findings of studies published in this area. However, one of them was published about 20 years ago, when women＇s football was still in its infancy and there were only a few studies to report on. The other review was more recent. Nonetheless, its main focus was on the game and training demands of senior elite female players. Thus, information on female footballers of lower competitive levels and younger age groups was not included. Consequently, an updated review is needed in this area. The present article therefore aims to provide an overview of a series of studies that have been published so far on the specific characteristics of female football players and the demands of match-play. Mean values reported in the literature for age （12-27 years）, body height （155-174 cm）, body mass （48-72 kg）, percent body fat （13%-29%）, maximal oxygen uptake （45.1-55.5 mL/kg/min）, Yo-Yo Intermittent Recovery Test Level l （780-1379 m）, maximum heart rate （189-202 bpm）, 30 m sprint times （4.34-4.96 s）, and counter- movement jump or vertical jump （28-50 cm） vary mostly according to the players＇ competitive level and positional role. There are also some special considerations that coaches and other practitioners should he aware of when working with female athletes such as the menstrual cycle, potential pregnancy and lactation, common injury risks （particularly knee and head injuries） and health concerns （e.g., female athlete triad, iron deficiency, and anemia） that may affect players＇ football performance, health or return to play. Reported mean values for total distance covered （4-13 km）, distance covered at high-speed （0.2-1.7 km）, average/peak heart rate （74%-87%/94%-99% HRmax）, average/peak oxygen uptake （52%-77%/96%-98% VO2max）, and blood lactate （2.2-7.3 mmol/L） during women＇s football match-play vary according to the players＇ competitive level and positional role. Methodological differences may account for the discrepancy of the reported values as well. Finally, this review also aims to identify literature gaps that require further scientific research in women＇s football and to derive a few practical recom-mendations. The information presented in this report provides an objective point of reference about player characteristics and game demands at various levels of women＇s football, which can help coaches and sport scientists to design more effective training programs and science-based strategies for the further improvement of players＇ football performance, health, game standards, and positive image of this sport.展开更多
This paper presents a new look on emergence from the aspect of locality andglobality of evaluation functions for solving traditional computer problems. We first translate theConstraint Satisfaction Problem (CSP) into ...This paper presents a new look on emergence from the aspect of locality andglobality of evaluation functions for solving traditional computer problems. We first translate theConstraint Satisfaction Problem (CSP) into the multi-agent system, and then show how a globalsolution emerges from the system in which every agent uses a local evaluation function to decide itsaction, while comparing to other traditional algorithms, such as Local search and SimulatedAnnealing which use global evaluation functions. We also give some computer experimental results onlarge-scale N-queen problems and κ-Coloring problems, and show that emergence only depends onproblem instance, not details of agent settings, i.e. in some CSPs, the system can self-organize toa global solution, but can not in some other CSPs no matter what settings of agents have.展开更多
An algorithm for solving the satisfiability problem is presented. It isproceed that this algorithm solves 2-SAT and Horn-SAT in linear time and k-positiveSAT (in which every clause contains at most k positive literals...An algorithm for solving the satisfiability problem is presented. It isproceed that this algorithm solves 2-SAT and Horn-SAT in linear time and k-positiveSAT (in which every clause contains at most k positive literals) ill time O(F.),where F is the length of input F, n is the number of atoms occurring in F, and k isthe greatest real number satisfying the equation x = 2-. Compared with previousresults, this nontrivial upper bound on time complexity could only be obtained fork-SAT, which is a subproblem of k-positive SAT.展开更多
基金supported by 973 Program under Grant No.2006CB921106National Natural Science Foundation of China under Grant No.60635040the Key Grant Project of the Ministry of Education under Grant No.306020
文摘In this paper we present a classical parallel quantum algorithm for the satisfiability problem. We have exploited the classical parallelism of quantum algorithms developed in [G.L. Long and L. Xiao, Phys. Rev. A 69 （2004） 052303], so that additional acceleration can be gained by using classical parallelism. The quantum algorithm first estimates the number of solutions using the quantum counting algorithm, and then by using the quantum searching algorithm, the explicit solutions are found.
基金Supportedby 86 3/CIMS (No .2 0 0 1AA4 1114 0 )andtheNationalNaturalScienceFoundationofChina (No .6 0 10 4 0 0 8)
文摘In order to facilitate solution, a complex problem is normally decomposed into many small sub-problems during product development process. Teams are formed to resolve each sub-problem. The original problem is resolved from solutions of sub-problems. Ideally, sub-problems are not only mutually independent but also inherent parameters of original problem. Solution of original problem can be directly derived from the collection of solutions from simplified sub-problems. In practice, the degree of interdependency is indeed reduced, sub-problems are neither totally independent nor all inherent parameters of original problem. This paper discusses team coordination under this condition and design solution from each team, which not only satisfies total requirements but also is an optimal one. The suggested optimized constraint decomposition method will insure workable Pareto solution.
文摘The Balanced Academic Curriculum Problem （BACP） is a constraint satisfaction problem classified as （Non-deterministic Polynomial-time Hard） NP-Hard. This problem consists in the allocation of courses in the periods that are part of a curriculum such that the prerequisites are satisfied and the load of courses is balanced for the students. This paper presents the solution for a modified BACP where the academic loads and number of curses may be the same or different for each one of the periods and allows having some courses in a specific period. This problem is modeled as an integer programming problem and is proposed the use of Tabu search with short-term memory for its solution because it is not possible to find solutions for all the instances of this modified problem with an exact method.
文摘The number of scientific investigations on women＇s football specific to the topics of player characteristics and demands of the game has considerably increased in recent years due to the increased popularity of the women＇s game worldwide, although they are not yet as numerous as in the case of men＇s football. To date, only two scientific publications have attempted to review the main findings of studies published in this area. However, one of them was published about 20 years ago, when women＇s football was still in its infancy and there were only a few studies to report on. The other review was more recent. Nonetheless, its main focus was on the game and training demands of senior elite female players. Thus, information on female footballers of lower competitive levels and younger age groups was not included. Consequently, an updated review is needed in this area. The present article therefore aims to provide an overview of a series of studies that have been published so far on the specific characteristics of female football players and the demands of match-play. Mean values reported in the literature for age （12-27 years）, body height （155-174 cm）, body mass （48-72 kg）, percent body fat （13%-29%）, maximal oxygen uptake （45.1-55.5 mL/kg/min）, Yo-Yo Intermittent Recovery Test Level l （780-1379 m）, maximum heart rate （189-202 bpm）, 30 m sprint times （4.34-4.96 s）, and counter- movement jump or vertical jump （28-50 cm） vary mostly according to the players＇ competitive level and positional role. There are also some special considerations that coaches and other practitioners should he aware of when working with female athletes such as the menstrual cycle, potential pregnancy and lactation, common injury risks （particularly knee and head injuries） and health concerns （e.g., female athlete triad, iron deficiency, and anemia） that may affect players＇ football performance, health or return to play. Reported mean values for total distance covered （4-13 km）, distance covered at high-speed （0.2-1.7 km）, average/peak heart rate （74%-87%/94%-99% HRmax）, average/peak oxygen uptake （52%-77%/96%-98% VO2max）, and blood lactate （2.2-7.3 mmol/L） during women＇s football match-play vary according to the players＇ competitive level and positional role. Methodological differences may account for the discrepancy of the reported values as well. Finally, this review also aims to identify literature gaps that require further scientific research in women＇s football and to derive a few practical recom-mendations. The information presented in this report provides an objective point of reference about player characteristics and game demands at various levels of women＇s football, which can help coaches and sport scientists to design more effective training programs and science-based strategies for the further improvement of players＇ football performance, health, game standards, and positive image of this sport.
基金This paper is supported by the International Program of Santa Fe Institute and the grant of China National Science Foundation(No.70171052).
文摘This paper presents a new look on emergence from the aspect of locality andglobality of evaluation functions for solving traditional computer problems. We first translate theConstraint Satisfaction Problem (CSP) into the multi-agent system, and then show how a globalsolution emerges from the system in which every agent uses a local evaluation function to decide itsaction, while comparing to other traditional algorithms, such as Local search and SimulatedAnnealing which use global evaluation functions. We also give some computer experimental results onlarge-scale N-queen problems and κ-Coloring problems, and show that emergence only depends onproblem instance, not details of agent settings, i.e. in some CSPs, the system can self-organize toa global solution, but can not in some other CSPs no matter what settings of agents have.
文摘An algorithm for solving the satisfiability problem is presented. It isproceed that this algorithm solves 2-SAT and Horn-SAT in linear time and k-positiveSAT (in which every clause contains at most k positive literals) ill time O(F.),where F is the length of input F, n is the number of atoms occurring in F, and k isthe greatest real number satisfying the equation x = 2-. Compared with previousresults, this nontrivial upper bound on time complexity could only be obtained fork-SAT, which is a subproblem of k-positive SAT.
