8N階三重幻方的構(gòu)造和相關(guān)問題的研究.pdf

1、幻方問題是一個(gè)歷史悠久的組合數(shù)學(xué)問題，也是一個(gè)典型的NP難問題。1890年法國(guó)數(shù)學(xué)家G.Pfeffermann發(fā)現(xiàn)了第一個(gè)多重幻方—8階二重幻方，幻方專家們因此翻開了構(gòu)造多重幻方的新篇章。
　　隨著計(jì)算機(jī)飛速發(fā)展，其運(yùn)算速度也急劇提高，人們逐漸將計(jì)算機(jī)引入到幻方的求解中?；梅絾栴}的復(fù)雜性在于，搜索空間隨階數(shù)指數(shù)遞增，但其解在搜索空間中所占的比例，隨階數(shù)指數(shù)遞減。如果不利用幻方的一些特性來進(jìn)行優(yōu)化，只用窮舉法，即使采用世界上運(yùn)行速度

2、最快的超級(jí)計(jì)算機(jī)來求解，也不能在可行時(shí)間內(nèi)求出。需要選擇合適的算法，仔細(xì)分析規(guī)律。
　　本文在比較了現(xiàn)有的構(gòu)造多重幻方的方法后，采用回溯法來進(jìn)行8N階三重幻方的求解，并采用啟發(fā)式的思想來設(shè)計(jì)算法。其難點(diǎn)在于如何減小搜索空間以及如何使初始矩陣盡量在最終解較密集的那塊區(qū)域搜索，以達(dá)到減少回溯、縮短搜索時(shí)間的目的。
　　幻方的搜索空間大的超乎想象，沒有合適的結(jié)構(gòu)規(guī)律，即使采用回溯法，也很難求出。本文引入了兩個(gè)重要的概念—奇偶偏補(bǔ)序