Limited Discrepancy Search (LDS) is a popular algorithm to search a state
space with a heuristic to order the possible actions. Nested Search (NS) is
another algorithm to search a state space with the same heuristic. NS spends
more time on the move associated to the best heuristic playout while LDS spends
more time on the best heuristic move. They both use similar times for the same
level of search. We advocate in this paper that it is often better to follow
the best heuristic playout as in NS than to follow the heuristic as in LDS.

本文提出利用 Nested Search 算法最优启发式播放路径的思路，与 Limited Discrepancy Search 算法相比，其更为高效。

嵌套搜索与有限差异搜索

Nested Search versus Limited Discrepancy Search

In this paper, we present a novel model for entity disambiguation that
combines both local contextual information and global evidences through Limited
Discrepancy Search (LDS). Given an input document, we start from a complete
solution constructed by a local model and conduct a search in the space of
possible corrections to improve the local solution from a global view point.
Our search utilizes a heuristic function to focus more on the least confident
local decisions and a pruning function to score the global solutions based on
their local fitness and the global coherences among the predicted entities.
Experimental results on CoNLL 2003 and TAC 2010 benchmarks verify the
effectiveness of our model.

本文介绍了一种使用 Limited Discrepancy Search（LDS）同时结合了局部上下文信息和全局证据的实体消岐模型。在 CoNLL 2003 和 TAC 2010 基准测试中验证了该模型的有效性。

输出空间搜索的联合神经实体消歧

Joint Neural Entity Disambiguation with Output Space Search

We describe Dr.Fill, a program that solves American-style crossword puzzles.
From a technical perspective, Dr.Fill works by converting crosswords to
weighted CSPs, and then using a variety of novel techniques to find a solution.
These techniques include generally applicable heuristics for variable and value
selection, a variant of limited discrepancy search, and postprocessing and
partitioning ideas. Branch and bound is not used, as it was incompatible with
postprocessing and was determined experimentally to be of little practical
value. Dr.Fillls performance on crosswords from the American Crossword Puzzle
Tournament suggests that it ranks among the top fifty or so crossword solvers
in the world.

Dr.Fill 是一个解决美式纵横填字游戏的程序，它将这些游戏转换为加权 CSPs，然后使用各种创新技术来找到解决方案，该程序在美国纵横填字游戏大赛上的表现表明，它在世界范围内排名前五十的纵横字谜解决者之间。