《圖的剖分問題中近似算法的研究》是依託南京大學，由韓喬明擔任項目負責人的青年科學基金項目。
《圖的剖分問題中近似算法的研究》是依託南京大學，由韓喬明擔任項目負責人的青年科學基金項目。項目摘要NP-完全問題的近似算法的研究是國際最最佳化領域及計算機科學領域近二十年來的熱門課題。本項目研究圖的剖分問題中的NP-完全問...
《最小權三角剖分的計算複雜性和近似算法》是依託西安交通大學，由徐寅峰擔任項目負責人的面上項目。中文摘要 求一個給定平面有限點集的最小權三角剖分是一個具有幾何結構的組合最最佳化問題。至今求解最小權三角剖分還沒有找到一個多項式算法，也不知道該問題是否為NP-難題。這一問題的計算複雜性、有效近似算法設計和...
在二維場問題中，涉及的區域是以Γ為邊界的平面區域Ω，三角剖分是常用的形式，它適用於各種幾何形狀的區域和非均勻介質的情況。其剖分原則是：1.將Ω劃分為若干三角形單元，三角形的頂點稱為節點，用相鄰邊界節點連成的折線及其圍成的區域近似代替曲線邊界Γ和區域Ω，如圖1。2.每個單元的頂點只能是相鄰單元的頂點...
本項目提出了最優Voronoi剖分（Optimal Voronoi Tessellation，簡稱OVT）的全新概念，並研究OVT的完整理論系統，在很大程度上推廣了重心Voronoi剖分（CVT）方法，為圖形學領域的多個套用問題提供功能強大的統一解決方案。首先從任意給定函式的任意階分片多項式逼近角度定義OVT的目標函式，通過研究OVT函式的光滑性和梯度計算公式...
11.2.1 對圓弧冪級數展開的有理逼近 11.2.2 利用基圓有理逼近對有理Bézier曲線作等距有理逼近 11.3 基於基圓重新參數化的等距曲線逼近 11.3.1 參數變換新公式的導出與等距逼近的實施 11.3.2 基圓重新參數化的等距逼近的精密誤差界 11.4 基於圓域Bézier曲線的等距逼近 11.4.1 套用Remez算法構造圓域...
《算法設計與分析》是2016年清華大學出版社 出版的圖書，作者是徐義春、萬書振、解德祥。內容簡介 本書涵蓋了常見計算機算法設計和分析的思路和方法，內容包括算法概論、遞推與遞歸、分治法、動態規劃法、搜尋方法、近似算法、隨機算法等，最後提供一些高級數據結構的介紹，以幫助實現效率更高的算法。本書重視算法思路的...
書中涵蓋的算法設計策略全面，包括用於問題精確求解的遞歸與分治策略、動態規划算法貪心策略、回溯算法和分支限界算法，用於求解NP難題的近似算法、串與序列的算法、隨機化算法等。以問題驅動的方式組織內容，先介紹一種算法設計策略的基本思想，然後從解決計算機科學與套用中出現的實際問題入手，由簡到繁地描述幾個經典的...
計算數學中最重要的是對於函式的插值(Interpolation)的構造方法的問題泛函和運算元的插值在構造計算方法中也已得到廣泛的套用。函式的近似表示和計算，函式的插值視為逼近該函式的方法之一。有限元素法 有限元素法是近代才發展起來的，它是以變分原理和剖分差值作為基礎的方法。在解決橢圓形方程邊值問題上得到了廣泛的套用...
該教材修正了第3版中發現的一些錯誤，並將各章的習題分為算法分析題和算法實現題兩部分，增加了算法實踐性內容，以期加強教學實踐環節。具體修改如下：增加了1.3 節NP完全性理論；刪除了理論性較強的3.12節動態規劃加速原理、4.8節貪心算法的理論基礎、第9章NP完全性理論與近似算法。該教材在編寫過程中，得到了...
《算法設計指南（第2版）》是2017年7月清華大學出版社出版的圖書，作者是Steven S· Skiena。內容簡介 本書由算法領域的知名專家Steven Skiena教授編寫，其主要內容包括基本算法設計、算法分析、數據結構、排序與查找、圖算法、動態規劃以及難解問題與近似算法。“設計”是本書的核心，作者不但以生動有趣的語言講授了...
4.3.2Delaunay三角剖分與多邊形內部點集的三角剖分 4.3.3平麵點集三角剖分的算法 4.4平面線段集的三角剖分 4.5平麵點線集的三角剖分 4.6平麵點集的偽三角剖分 4.7三角剖分的表示 4.8套用 4.8.1最近鄰近 4.8.2最大化最小角的三角剖分 4.8.3最大空圓 4.8.4最小生成樹 4.8.5貨郎擔問題 4...
近代力學的基本理論和基本方程在19世紀末20世紀初已基本完備了，後來的力學家大多致力於尋求各種具體問題的解。但由於許多力學問題相當複雜，很難獲得解析解，用數值方法求解也遇到計算工作量過於龐大的困難。通常只能通過各種假設把問題簡化到可以處理的程度，以得到某種近似的解答，或是藉助於實驗手段來謀求問題的解決。
9.1.2算法設計中的最最佳化問題 9.2分治法 9.2.1分治策略的思想 9.2.2高精度計算 9.2.3矩陣相乘的Strassen算法 9.2.4選擇問題的分治算法 9.2.5分治法求最近點對問題 9.2.6分治法的套用 9.3貪心法 9.3.1貪心算法的思想 9.3.2活動安排問題 9.3.3背包問題 9.3.4多機調度問題的近似算法 9.3...
第8章介紹NP完全性理論。首先介紹計算模型、確定性和非確定性圖靈機，然後進一步介紹NP完全性理論。第9章介紹了解NP難問題的近似算法，這是計算機算法領域的熱門研究課題，具有較高的實用價值。第10章通過實例介紹算法設計中常用的算法最佳化策略。最後，在第11章介紹算法設計中較新的研究領域——線上算法設計。教材目錄 ...
基於QAP問題理論和實際的重要性，過去幾十年已激發了許多學者對其理論、套用和最佳化技術的研究。1976年Sahni和Gonzales證明了QAP不僅屬於NP-hard問題而且不存在近似度的多項式時間近似算法。QAP是很難求解的最最佳化問題，其主要原因是所謂的“組合爆炸”現象，求解時間隨問題規模呈指數增長。一般而言，當問題規模n>20時，很...
《算法設計與分析》是2021年清華大學出版社出版的圖書，作者是王秋芬。內容簡介 本書主講貪心算法、分治算法、動態規划算法、回溯算法、網路流、隨機化算法、近似算法，側重用具體實例圖解演示算法運行過程及python語言實現。本書特色：深入淺出地從問題分析，到數據結構選擇、算法設計、Python實戰，提供問題解決的全程式...
4.3.2Delaunay三角剖分與多邊形內部點集的三角剖分 4.3.3平麵點集三角剖分的算法 4.4平面線段集的三角剖分 4.5平麵點線集的三角剖分 4.6平麵點集的偽三角剖分 4.7三角剖分的表示 4.8套用 4.8.1最近鄰近 4.8.2最大化最小角的三角剖分 4.8.3最大空圓 4.8.4最小生成樹 4.8.5貨郎擔問題 4...
4.6.2Prim算法 4.6.3Kruskal算法 4.7多機調度問題 4.8貪心算法的理論基礎 4.8.1擬陣 4.8.2帶權擬陣的貪心算法 4.8.3任務時間表問題 小結 習題 第5章回溯法 第6章分支限界法 第7章機率算法 第8章NP完全性理論 第9章近似算法 第10章算法最佳化策略 第11章線上算法設計 辭彙索引 參考文獻 ...
主要內容包括：算法概述、遞歸與分治策略、動態規劃、貪心算法、回溯法、分支限界法、隨機化算法、線性規劃與網路流、NP完全性理論與近似算法等。書中既涉及經典與實用算法及實例分析，又包括算法熱點領域追蹤。為突出教材的可讀性和可用性，章首增加了學習要點提示；章末配有難易適度的習題，分為算法分析題和算法實現...
3.4 曲面剖分算法 3.4.1 bézier曲線的遞歸細分 3.4.2 bézier曲面的遞歸細分 3.4.3 bézier曲面片的法向量 3.4.4 裂縫問題的處理 3.5 a緩衝器算法 3.6 陰影 3.6.1 陰影細節多邊形算法 3.6.2 影域多面體算法 3.7 圖像合成 3.7.1 rgbα方法 3.7.2 rgbαz方法 3.7.3 基於多重掃描線的...
積分方程數值解法(numerical methods for in-tegral equations)研究求積分方程近似解的數值方法.積分方程數值解的主要求解對象為第一、二類弗雷德霍姆型和伏爾泰拉型積分方程以及相應的特徵值問題.主要求解方法有伽遼金法，配置法和求積法.下面以第二類弗雷德霍姆型積分方程 (其中右端項g (t)，積分核KCt,s)為已知函式...
通過數值計算方法，在計算機上對偏微分方程的近似求解。科學和工程中的大多數實際問題都歸結為偏微分方程的定解問題，由於很難求得這些定解問題的解析解（在經典意義下甚至沒有解），人們轉向求解它們的數值近似解。通常先對問題的求解區域進行格線剖分，然後基於有限元法、有限差分法和有限體積法等數值方法，對原定...
8.3 離散近似 8.4 局部運算元和噪聲 8.5 邊緣的檢測和定位 8.6 結論和例子 8.7 本章參考文獻 8.8 習題 第 9 章 光照與顏色 9.1 物體表面的反射率以及 Land 實驗 9.2 Mondrian 圖 9.3 復原光照 9.4 求解逆問題 9.5 光照的歸一化 9.6 選擇閾值 9.7 離散情況下計算光照 9.8 一個物理模型 9...
它將求解域看成是由許多稱為有限元的小的互連子域組成，對每一單元假定一個合適的（較簡單的）近似解，然後推導求解這個域總的滿足條件（如結構的平衡條件），從而得到問題的解。這個解不是準確解，而是近似解，因為實際問題被較簡單的問題所代替。由於大多數實際問題難以得到準確解，而有限元不僅計算精度高，而且能...
在以上幾個方面的研究中，EIT 的研究歷史較長，MIT 和 MEEIT 均處於起步階段。套用現狀 EIT研究 在EIT中，有限元模型的剖分可以將特殊邊界條件的場域做近似線性化處理，目的是為了解決外加電場在人體內引起的電流分布的非線性和非均勻性，實質上是利用數值方法求解具有特殊定解的一組偏微分方程。因為逆問題的病態...
但是有些實際計算問題的計算區域是無界的，用有界區域來近似無界區域時，為達到所需的精度，會使計算量大大增加，邊界元方法是解決此問題的一種有效途徑。關於對微分方程作邊界歸化的思想，早在上一世紀就已出現，但套用於數值計算卻是本世紀60年代才開始，這就是邊界元方法，即將微分方程歸化為邊界上的積分方程。由...
當原問題可行時，該模型可以收斂到原問題的最優解；當前約束或者控制變數越界導致原問題無解時，可以自動到更大的可行域內尋優，快速地得到近似解，並且可以明確指出是導致原問題無解的關鍵約束，從計算結果中可以方便地得到調整的措施。改進的算法在各種情況下都有很好的收斂性。電力市場運行中，隨機因素的影響越來越...
而CAE軟體可作靜態結構分析，動態分析；研究線性、非線性問題；分析結構（固體）、流體、電磁等。發展歷程 CAE(Computer Aided Engineering）是用計算機輔助求解複雜工程和產品結構強度、剛度、屈曲穩定性、動力回響、熱傳導、三維多體接觸、彈塑性等力學性能的分析計算以及結構性能的最佳化設計等問題的一種近似數值分析方法。
但是射線理論只適用於波速在一個波長範圍內變化很小的場合，是波動方程的高頻近似，因此它有一定的局限性。而基於波動方程的層析成像方法由於需要超大規模的三維數值計算，還有許多問題沒有解決。但波動方程包含了地震波場的全部信息，比僅利用走時資料的射線追蹤層析成像更能客觀地反映地下結構的信息，因此是未來地震層析...
