Korf,R.E:“多棋手的α—β剪枝”(学术研究短文).刊载在《人工智能》杂志1991年48卷的第99页至第111页上。我们考虑将带α——β剪枝的极小极大搜索推广列无合作的、有两名以上棋手的完备博奕。极小极大算法在[2]中推广为 max 算法,施...Korf,R.E:“多棋手的α—β剪枝”(学术研究短文).刊载在《人工智能》杂志1991年48卷的第99页至第111页上。我们考虑将带α——β剪枝的极小极大搜索推广列无合作的、有两名以上棋手的完备博奕。极小极大算法在[2]中推广为 max 算法,施用于 n 元组向量,这种 n 元组表示每一位棋手的估值。假设每位棋手的估值数总和存在一个上界,且对每一个别值存在一个下界,这样,浅层α——β剪枝就能进行,但不能进行深度剪枝。最好情况下,渐近分枝因数减少到(1+(4b-3)^(1/2))/2,而在平均情况下,剪枝不会减少渐近分枝因数,所以α——β剪枝的有效性只存在于两名棋手博奕的特殊情形。此外,我们证明了它是对两名选手的最佳定向算法。展开更多
We consider the problem of restoring images corrupted by Poisson noise. Under the framework of maximum a posteriori estimator, the problem can be converted into a minimization problem where the objective function is c...We consider the problem of restoring images corrupted by Poisson noise. Under the framework of maximum a posteriori estimator, the problem can be converted into a minimization problem where the objective function is composed of a Kullback-Leibler(KL)-divergence term for the Poisson noise and a total variation(TV) regularization term. Due to the logarithm function in the KL-divergence term, the non-differentiability of TV term and the positivity constraint on the images, it is not easy to design stable and efficiency algorithm for the problem. Recently, many researchers proposed to solve the problem by alternating direction method of multipliers(ADMM). Since the approach introduces some auxiliary variables and requires the solution of some linear systems, the iterative procedure can be complicated. Here we formulate the problem as two new constrained minimax problems and solve them by Chambolle-Pock's first order primal-dual approach. The convergence of our approach is guaranteed by their theory. Comparing with ADMM approaches, our approach requires about half of the auxiliary variables and is matrix-inversion free. Numerical results show that our proposed algorithms are efficient and outperform the ADMM approach.展开更多
文摘Korf,R.E:“多棋手的α—β剪枝”(学术研究短文).刊载在《人工智能》杂志1991年48卷的第99页至第111页上。我们考虑将带α——β剪枝的极小极大搜索推广列无合作的、有两名以上棋手的完备博奕。极小极大算法在[2]中推广为 max 算法,施用于 n 元组向量,这种 n 元组表示每一位棋手的估值。假设每位棋手的估值数总和存在一个上界,且对每一个别值存在一个下界,这样,浅层α——β剪枝就能进行,但不能进行深度剪枝。最好情况下,渐近分枝因数减少到(1+(4b-3)^(1/2))/2,而在平均情况下,剪枝不会减少渐近分枝因数,所以α——β剪枝的有效性只存在于两名棋手博奕的特殊情形。此外,我们证明了它是对两名选手的最佳定向算法。
基金supported by National Natural Science Foundation of China(Grant Nos.1136103011271049 and 11271049)+5 种基金the Project Sponsored by the Scientific Research Foundation for the Returned Overseas Chinese ScholarsState Education Ministry(Grant Nos.CUHK400412HKBU502814211911and 12302714)Hong Kong Research Grants Council(Grant No.Ao E/M-05/12)FRGs of Hong Kong Baptist University
文摘We consider the problem of restoring images corrupted by Poisson noise. Under the framework of maximum a posteriori estimator, the problem can be converted into a minimization problem where the objective function is composed of a Kullback-Leibler(KL)-divergence term for the Poisson noise and a total variation(TV) regularization term. Due to the logarithm function in the KL-divergence term, the non-differentiability of TV term and the positivity constraint on the images, it is not easy to design stable and efficiency algorithm for the problem. Recently, many researchers proposed to solve the problem by alternating direction method of multipliers(ADMM). Since the approach introduces some auxiliary variables and requires the solution of some linear systems, the iterative procedure can be complicated. Here we formulate the problem as two new constrained minimax problems and solve them by Chambolle-Pock's first order primal-dual approach. The convergence of our approach is guaranteed by their theory. Comparing with ADMM approaches, our approach requires about half of the auxiliary variables and is matrix-inversion free. Numerical results show that our proposed algorithms are efficient and outperform the ADMM approach.
