earticle

논문검색

논문

N-Puzzle과 3n+1 문제의 행위적 유사성 분석

원문정보

Analysis on Behavioral Similarity of N-Puzzle with 3n+1 Problem

아흐마드이자즈, 신석주

피인용수 : 0(자료제공 : 네이버학술정보)

초록

영어

3n+1 problem is well known in mathematics as arithmetically simplest to state yet hard to prove conjecture. The difficulty in finding a proof for the conjecture lies in its isolation from other mathematical areas and the fact that no pattern can be seen in the sequence. The N-puzzle is a tile game in which a sequence of moves is performed to reach goal state from any initial configuration. In this paper we present the study of 3n+1 problem’s iterations with respect to the moves of N-puzzle. We have implemented the Modified Syracuse algorithm to find length of T-trajectory of 3n+1 problem, and A* algorithm with Manhattan distance for finding optimal number of moves in N-puzzle. We have shown that in N-puzzle the sequence of optimal moves behaves similar to the random nature of 3n+1 problem iteration based on the Hamming distance and Kendall tau distance of N-puzzle initial configuration and goal state.

한국어

3n+1 문제는 산술적으로는 단순하나 이에 대한 추정을 수학적으로는 증명하기 어려운 문제로 유명하다. 이 추정에대한 증명을 찾는 것이 어려운 이유는 다른 수학 분야들과 다소 동떨어진 분야이고, 수렴하는 순서에 있어서 특정패턴이 존재하지 않는다는 사실에 있다. N-puzzle은 초기 상태로부터 최종 목적 상태에 도달하기 위해 순서적으로타일을 움직이는 타일 게임 중 하나이다. 본 논문에서는 N-puzzle 에서의 타일 이동 패턴에 대한 3n+1 문제의 반복에 따른 수렴 패턴의 유사성을 연구하였다. 3n+1 문제에 대한 T-trajectory의 길이를 찾기 위하여 변형 시라쿠스(Modified Syracuse) 알고리즘을 구현하였고, N-puzzle에서 최적의 이동수를 도출하기 위해 맨하탄 디스턴스(Manhattan Distance)를 고려한 A* 알고리즘을 구현하였다. 연구로부터 N-puzzle의 초기 상태로부터 목적 상태까지의 Hamming distance와 Kendall tau distance에 기반하여 3n+1 문제의 반복 랜덤 특성이 N-puzzle 의 최적 이동 순서와 유사한 행위를 보임을 증명하였다.

목차

요약
 Abstract
 1. Introduction
 2. 3n+1 Problem
 3. N-Puzzle
 4. Implementation Results and Analysis
 5. Conclusion
 참고문헌

저자정보

  • 아흐마드이자즈 Ahmad Ijaz. Department of Computer Engineering, Chosun University Gwangju, Republic of Korea
  • 신석주 Seokjoo Shin. Department of Computer Engineering, Chosun University Gwangju, Republic of Korea

참고문헌

자료제공 : 네이버학술정보

    ※ 원문제공기관과의 협약에 따라 모든 이용자에게 무료로 제공됩니다.

    0개의 논문이 장바구니에 담겼습니다.