15-謎問題(15-puzzle)的可達性判定

定義了15-謎問題的6個動作規(guī)則，在此基礎(chǔ)上證明了15-謎問題解的存在性判定的充分必要條件，其充分性的證明過程是一個構(gòu)造性證明方法，提供了求解15-謎問題的一個解的可實現(xiàn)算法；同時，對此結(jié)論進行了擴展，對于給定的一初始格局和任一目標格局，證明了初始格局可達目標格局的的充分必要條件，其結(jié)論有助于構(gòu)造問題的狀態(tài)空間與限界函數(shù)。這兩個結(jié)論從理論上完全解決了15-謎問題，對獲得最優(yōu)算法提供了理論基礎(chǔ)。
關(guān) 鍵 詞 15-謎問題; 格局; 可達性; 算法

Abstract Based on multiple-input-multiple-output (MIMO) scattering wireless fading channel model, a dynamic receiving and transmitting model for MIMO wireless channels is proposed in this paper, which is used for analyzing impact of mobility of transceiver antennas on spatial correlation and capacity of MIMO wireless channels. The conclusion is reached, which these effects are determined by the original positions of transceiver antennas and by their velocity. The simulation results validate this impact and show that there exists an optimum angular spread that forces spatial correlation, which decreases with increasing antenna spacing and does not consistently decrease with increasing angular spread, to reach minimum.
Key words 15-puzzle; pattern; reachability; algorithm