کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
381784 659756 2016 7 صفحه PDF سفارش دهید دانلود کنید
عنوان انگلیسی مقاله ISI
BBFS-STT: An efficient algorithm for number rotation puzzle
ترجمه فارسی عنوان
BBFS-STT: یک الگوریتم کارآمد برای پازل چرخش تعداد
کلمات کلیدی
پازل چرخش تعداد (NRP)؛ پازل کشویی. حالت تشخیص تکراری؛جستجوی دوطرفه ؛ جدول انتقال حالات
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر هوش مصنوعی
چکیده انگلیسی


• It introduces a novel intellectual game, NRP, which is rarely addressed so far.
• It presents a novel and efficient solving algorithm, BBFS-STT.
• It develops a game application of NRP including automatically and manually solving.

This paper introduces a quite novel intellectual game, number rotation puzzle (NRP), and deeply compares NRP with 8-puzzle. It comprehensively discusses some issues relevant to solving NRP, such as state representation, state duplicate detection, transition relation between states, solvability judging, and optimal solution. Upon these work, this paper proposes a solving algorithm based on bidirectional breadth-first search (BBFS) and states transition table, which is called BBFS-STT. It takes full advantage of transition relation between states, as well as advantages of BBFS. BBFS-STT achieves high time efficiency and well stability. In addition, this paper designs a game application of NRP, whose prominent feature is that users can seamlessly switch between automatically solving and manually solving modes. Finally, this article carries out experimental analysis on the proposed algorithm, as well as comparison with some search algorithms, i.e., depth-limited DFS, traditional BFS, and A∗. Experimental results show that the proposed BBFS-STT outperforms these three search algorithms. The average time required for solving an instance of NRP is only 0.80592 ms when the test environment is configured as: Apple A6, 1.00 GHz; 1 GB memory. BBFS-STT meets the requirements of real-time solving and demonstration for NRP.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Entertainment Computing - Volume 12, January 2016, Pages 1–7
نویسندگان
, ,