The Fifteen Puzzle- A New Approach through Hybridizing Three Heuristics Methods
Fifteen Puzzle problem is one of the most classical problems that have captivated mathematical enthusiasts for centuries. This is mainly because of the huge size of the state space with approximately 1013 states that have to be explored and several algorithms have been applied to solve the Fifteen Puzzle instances. In this paper, to deal with this large state space, Bidirectional A* (BA*) search algorithm with three heuristics, such as Manhattan distance (MD), linear conflict (LC), and walking distance (WD) has been used to solve the Fifteen Puzzle problems. The three mentioned heuristics will be hybridized in a way that can dramatically reduce the number of generated states by the algorithm. Moreover, all those heuristics require only 25KB of storage but help the algorithm effectively reduce the number of generated states and expand fewer nodes. Our implementation of BA* search can significantly reduce the space complexity, and guarantee either optimal or near-optimal solutions.1
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Heuristics, Answer Set Programming and Markov Decision Process for Solving a Set of Spatial Puzzles
Spatial puzzles composed of rigid objects, flexible strings and holes offer interesting domains for reasoning about spatial entities that are common in the human daily-life's activities. The goal of this work is to inves…
Q-LearningReinforcement LearningReinforcement Learning (RL)Fast Game Content Adaptation Through Bayesian-based Player Modelling
In games, as well as many user-facing systems, adapting content to users' preferences and experience is an important challenge. This paper explores a novel method to realize this goal in the context of dynamic difficulty…
Near Optimal Solving of the (N2-1)-puzzle Using Heuristics Based on Artificial Neural Networks
We address the design of heuristics for near-optimal solving of the (N2–1)-puzzle using the A* search algorithm in this paper. The A* search algorithm explores configurations of the puzzle in the order determined by a he…
On the Design of a Heuristic based on Artificial Neural Networks for the Near Optimal Solving of the (N2-1)-puzzle
This paper addresses optimal and near-optimal solving of the (N2–1)-puzzle using the A* search algorithm. We develop a novel heuristic based on artificial neural networks (ANNs) called ANN-distance that attempts to estim…
Learning Empirically Admissible Neural Heuristics for Combinatorial Search
Finding optimal solution paths for combinatorial puzzles like the Rubik's Cube, sliding tile puzzles, and Lights Out remains a classical challenge in artificial intelligence. Heuristic search algorithms, such as A* , gua…
Reinforcement Learning