A parallel algorithm for the eight-puzzle problem using analogical reasoning

✍ Scribed by Zoheir Ezziane

• Publisher: John Wiley and Sons
• Year: 2002
• Tongue: English
• Weight: 85 KB
• Volume: 17
• Category: Article
• ISSN: 0884-8173
• DOI: 10.1002/int.10027

✦ Synopsis

The emphasis in this article will be on people's analogical use of fairly explicit pieces of knowledge in problem solving situations. Analogical reasoning (AR) has long been recognized as an important component of problem solving. In general, AR involves using the (possibly modified) solution of one problem to solve another. The preconditions that need to be satisfied in order to apply AR are to locate the common features that are shared among the two problems. The case study considered here is the eight-puzzle problem.

The underlying learning is a three-stage process. First, is the building stage, where heuristic search techniques are used to find solutions to a set of initial puzzles. The next stage, the reminding stage, identifies a group of solutions with similar properties to the input puzzle (supposedly, this puzzle is solvable). During the final stage, the analogical transformation stage, many movement operators are applied to similar solutions already extracted from the reminding stage, in order to find the solution to the original (input) puzzle.

One of the major drawbacks is that AR requires a lot of computational power for global searching before it can be converged. Therefore, in order to outperform heuristic algorithms, a parallel version of AR is introduced. Parallel computation is focused on the last two stages of AR. A design and analysis of parallel algorithms of the reminding stage and the analogical transformation stage are presented.