<aside> 🧸 本文简单说明了如何用轮椅找到最有路径跑路。

</aside>

<aside>

Advanced Algorithm Design and Analysis

</aside>

样题.pdf

• Decision problem (with yes-no answers)判断问题

• Optimal Value/Optimal Solution 优化问题

  Optimization

• Numerical Calculation 数值计算

  Numerical Analysis

前两者的计算难易程度相似，计算理论暂只讨论判断问题。

<aside> 🥰

算法 vs 程序：

程序针对计算机语言，算法针对人类语言。

Program ⇒ Algorithm ⇒ Program ⇒ Computer(input, output)

</aside>

物以类聚：measuring the minimum resource required to solve the problem

(判断问题) Polynomial NP NPComplete PTAS

Heuristic algorithms 启发式 ⇒ modern : AI

Approximation algorithms

Fast exact algorithms: effective exponential-time algorithms

Parameterized algorithms : algorithm is effective when the parameter is small

Interval scheduling $n\log n$ greedy algorithm

weighted interval scheduling: $n\log n$ dynamic programming algorithm

Bipartite Matching 二图匹配 nm Hungarian algorithm 匈牙利算法

Independent Set 独立集 NPC

Competitive Facility Location 设施选择 PSPACE-complete