《Thomson問題的機械化算法研究》是依託上海大學，由冷拓擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：Thomson問題的機械化算法研究
- 項目類別：青年科學基金項目
- 項目負責人：冷拓
- 依託單位：上海大學
中文摘要,結題摘要,
中文摘要
利用計算機在含離散變數的組合問題的可行解集中找出最優解，特別是求解過程中的機械化算法構建，早已成為定理機器證明的一個重要分支。著名的Thomson問題是一個具有深厚物理學背景的組合幾何問題。其主要難點在於隨著球麵點數的增大，計算複雜度將迅速增長從而超出計算機的處理能力。本項目的主要研究內容有：利用矩形區域剖分法、誤差可控的符號數值混合計算、GPU並行運算等方法建立通用的機械化算法求解Thomson問題中球面n點(n≤16)最優分布模型及距離的最大和上界，並適當探索Erdos-Szekeres問題的機械化解法。這些研究不僅具有很好的前沿性和較重要的理論意義，而且有著很好的套用前景。
結題摘要
本項目以Thomson問題低維情形等若干有難度組合最佳化問題為切入點，致力於對數學機械化算法的研究。該方向正是人工智慧中的符號推理與定理機器證明方向的具體體現，利用計算機和基於符號計算高效算法在含有離散變數的組合問題可行解集中找出最優解，亦是屬於數學和計算機科學交叉的前沿領域。三年內，我們的研究內容主要包括對Thomson問題的球面n點(n為奇素數)最優分布模型及距離最大和的上界不等式的研究；以及對基於符號數值混合算法的大間距離散不規則樣本重建算法和其實際套用；同時也對研究過程中的一些核心不等式如離散高階Wirtinger型不等式的逆形式和離散Holder型不等式的逆形式進行了推廣和探索。 我們主要取得的成果則包括：(1)建立了基於球極投影坐標、Wirtinger不等式範數逼近、區域剖分法等技術手段的機械化算法，在計算過程中對中間結式消元採用了誤差可控的符號數值混合計算，有效消解了中間過程膨脹問題，較好地解決了Thomson 問題中m = 3，n = 7， λ = 1的情形，驗證了球面上7點距離和最大時的最優分布模型。(2)提出了基於牛頓-龍格插值法的數值插值檢驗法和基於笛卡爾符號法則與Dixon結式的零點隔離法,對高次大多項式進行數值逼近,並由誤差值對精確值進行確定.之後由柱型代數分解法對高次不等式組進行證明，由此確定了球麵點間兩兩距離和的上界。(3)將符號數值混合插值逼近法運用到了電能大數據分析建模領域,建立了基於大間距樣本重建的電能傳輸質量評估體系,此成果和合作者獲得2017年上海市科技成果三等獎。本項目研究過程中得到的算法和其收斂性、終止性研究在信號分析、編碼理論、數據可視化等眾多領域中都有著廣泛和深遠的套用前景。
