计算机问题求解一论题4.10 优化问题的近似解 陶先平 2019年5月22日
计算机问题求解—论题4.10 优化问题的近似解 陶先平 2019年5月22日
近似算法为什么有用？ "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时 算法级别 上的误差 近似算法的若干基本概念
近似算法的若干基本概念 For every xe LI,the approximation ratio Ra(x)of A on x is defined as ∫cost(A(x)Optu(c)) RA()=max Optu()cost(A() For any n E N,we define the approximation ratio of A as RA(n)=max {RA(x)ELI(I)
近似算法的若干基本概念