计算机问题求解一论题4.10 优化问题的近似解 陶先平 2021年5月10日
计算机问题求解—论题4.10 优化问题的近似解 陶先平 2021年5月10日
问题1.1：你能给出最短哈密尔顿回路的一 种“近似”解法吗？ 随便找一条？ 贪心找一条？ 问题1.2：你能找到一个方法学（价值观和 方法)，去评估这些算法吗？
问题1.1：你能给出最短哈密尔顿回路的一 种“近似”解法吗？ 随便找一条？ 贪心找一条？ 问题1.2：你能找到一个方法学(价值观和 方法)，去评估这些算法吗？
近似算法为什么有用？ "If an optimization problem does not admit any efficient algorithm computing an optimal solution,is there a possibility to efficiently com- pute at least an approzimation of the optimal solution?" •牺牲可以容忍的一点点误差 ·得到一个可实运行的求解斧生 何谓一点点？ 何谓误差？
近似算法为什么有用？ •牺牲可以容忍的一点点误差 •得到一个可现实运行的求解算法 何谓一点点？ 何谓误差？
近似算法的若干基本概念 an approximation algorithm for an optimization problem is an algorithm that provides a feasible solution whose quality does not differ too much from the quality of an optimal solution. 这段文字中的quality是什么意思？ 这个公式中的cost是什么意思？ 针对实例x EA(x)= cost(A(x)）-Optu(xr川 的相对误差 Optu()
这个公式中的cost是什么意思？ 近似算法的若干基本概念 这段文字中的quality是什么意思？ 针对实例x 的相对误差
近似算法的若干基本概念 For any n e N,we define the relative error of A as 问题规模为n时 eA(n)=max{eA(x)lx∈Lr∩（∑r)"}. 算法级别 上的误差 到底定义了什么误 差？
到底定义了什么误 差？ 问题规模为n时 算法级别 上的误差 近似算法的若干基本概念