|
Traveling Salesperson and NP-Complete Problems(a subtopic of Games & Puzzles)
Completing Latin Squares. By Ivars Peterson. Science News (May 6, 2000). "Latin squares are also linked to algebraic objects known as quasigroups. A quasigroup is defined in terms of a set, Q, of distinct symbols and a binary operation (called multiplication) involving only the elements of Q. A quasigroup's multiplication table turns out to be a Latin square. Each element of the set Q occurs exactly once in each row and each column of the table. The so-called quasigroup completion problem concerns a table that is correctly but only partially filled in. The question is whether the remaining blanks in the table can be filled in to obtain a complete Latin square (or a proper quasigroup multiplication table). Computer scientists have proved that the quasigroup completion problem belongs to a category of difficult computational problems described as NP-complete. As the number of elements, n, increases, a computer's solution time grows exponentially in the worst case. In effect, systematically solving such a worst-case problem involving many elements can take an enormous amount of time, even on the fastest available computers." Sudoku Science - A popular puzzle helps researchers dig into deep math. By Lauren Aaronson. IEEE Spectrum Online February 2006). "Millions of people around the world are tackling one of the hardest problems in computer science --- without even knowing it. The logic game Sudoku is a miniature version of a longstanding mathematical challenge, and it entices both puzzlers, who see it as an enjoyable plaything, and researchers, who see it as a laboratory for algorithm design. ... As a member of the NP-complete subset, Sudoku is an ideal tool for investigating the whole class of NP problems: an efficient algorithm for any NP-complete problem --- the toughest of NP problems --- automatically provides an efficient algorithm for solving all. Although most experts believe that no such algorithm exists, they continually search for improved algorithms that provide shorter, if not the very shortest, paths to solutions. Sudoku has already led some researchers to concrete advances in algorithm design. At the Intelligent Information Systems Institute at Cornell University, Ithaca, N.Y., director Carla Gomes experiments with Latin Squares, a version of Sudoku without subgrids. ... Sudoku follows in a long tradition of artificial intelligence research on games, most notably chess. But some of AI's most important advances stem from more modest games. The route-finding algorithm that powers car navigation systems, for instance, was first demonstrated on the Sliding Tile puzzle...." An Interactive Constraint-Based Approach to Sudoku. By Christopher Reeson, Ken Bayer, Berthe Y. Choueiry, and Kai-Chen Huang. In Proceedings of the Twenty-Second National Conference on Artificial Intelligence, 1976 - 1977. Menlo Park, Calif.: AAAI Press (2007). Abstract: "We present a Java applet, Solver, that allows a user to interactively solve a Sudoku problem using Constraint Processing (CP) techniques. We also present a companion Java applet, Constructor, that allows human users to enter and store new puzzle instances. Our system showcases the power of CP techniques in solving problems through a widely familiar and easily approachable puzzle. Our Solver is built to maximize the interactions between the human users and CP techniques. It allows the users to apply different consistency algorithms, work specifically on certain constraints, and make assignments and domain reductions on their own. We also designed a hint functionality that uses The Quasigroup Completion Problem. A very impressive (and colorful) demo from Carla P. Gomes.  Computer Scientist Solves Old Salesman Problem. From ScienceDaily Magazine. [Source: Washington University In St. Louis; date posted 1/16/2001] "The Traveling Salesman Problem is actually an umbrella term for a whole host of planning and scheduling problems, often involving routes; a classic one being a postman's route, for instance. ... Loosely speaking, NP-Complete is a class of problems that are believed unsolvable within a reasonable amount of time in the worst case. Thus, approximation algorithms are very important for solving real-world problems such as the payphone coin collector problem."
A Fast TSP solver Using A Genetic Algorithm. In this TSP demo, you can place the cities on the map! From The University of Texas at Arlington's Department of Computer Science and Engineering. Solving Traveling Salesman Problems. From the School of Industrial and Systems Engineering at Georgia Tech. A delightful site with a wonderful Pictorial History of the TSP. Accelerating Problem Solving. Listen to David Fogel, CEO of Natural Selection, explain GA's and the TSP. Presentation delivered at the Accelerating Change 2005 conference, and made available by IT Conversations. Related AI Topics Pages |
