Nested Search versus Limited Discrepancy Search Tristan Cazenave LAMSADE Université Paris Dauphine - PSL CNRS Paris France

2025-05-02 0 0 355.72KB 15 页 10玖币

侵权投诉

Nested Search versus Limited Discrepancy Search

Tristan Cazenave

LAMSADE, Université Paris Dauphine - PSL, CNRS, Paris, France

Abstract. 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.

Keywords: Search ·Combinatorial Optimization ·Constraint Satisfac-

tion.

1 Introduction

Combinatorial Optimization has many applications in numerous ﬁelds. Heuris-

tic algorithms aim at solving Combinatorial Optimization problems using do-

main dependent knowledge without proving the optimality of the solution found.

When the possible decisions can be sorted according to a heuristic, algorithms

such as LDS [26] and NS [41] can leverage the heuristic and ﬁnd good solutions

to diﬃcult problems much faster than other more complete search algorithms.

Decision problems are a special kind of problems since ﬁnding a solution to

a problem is equivalent to ﬁnding an optimal solution. Many Constraint Pro-

gramming problems fall into this category. For this kind of problems LDS and

NS can be particularly eﬀective compared to complete search algorithms.

LDS is a popular search algorithm. There have been many papers using LDS

to eﬀectively search diﬃcult problems including very recent ones. The base level

performs playouts with a move ordering heuristic. A nice property of LDS is that

it is guaranteed to improve on the previous levels with increasing levels of search.

It has been applied to many diﬃcult problems and it is currently commonly used

for Combinatorial Optimization and Constraint Programming problems.

For example, LDS has been recently used as a search algorithm to combine

Deep Reinforcement Learning and Constraint Programming in order to solve

Combinatorial Optimization problems such as the Traveling Salesman Problem

with Time Windows (TSPTW), 4-Moments Portfolio Optimization or the 0-1

Knapsack Problem [9].

It has also been recently used in combination with bandits in the Bandit

Limited Discrepancy Search algorithm that was used for optimized algorithm

selection in a ﬁxed Machine Learning pipeline structure [28].

arXiv:2210.00216v1 [cs.AI] 1 Oct 2022

2 Tristan Cazenave

NS is close to LDS but it diﬀers in the choice of the decision that will be

searched more. LDS follows the heuristic prior in order to decide which decision

will be searched more. NS chooses to search more the decision that scores best

according to the lower level playouts.

The paper is organized as follows. The second section recalls LDS. The third

section deals with NS. The fourth section theoretically compares NS and LDS.

The ﬁfth section experimentally compares the two algorithms on four diﬃcult

Combinatorial Optimization problems.

Algorithm 1 The LDS algorithm.

1: LDS (state,level)

2: if terminal (state)then

3: return score (state)

4: end if

5: best =−∞

6: sort the possible moves

7: for min possible moves for state do

8: s←play (state,m)

9: if m is the ﬁrst move then

10: score =LDS (s,level)

11: else if level > 0then

12: score =LDS (s,level −1)

13: else

14: continue

15: end if

16: best =max(best, score)

17: end for

18: return best

2 Limited Discrepancy Search

LDS [26] is given in Algorithm 1. It has applications in Constraint Programming

and Combinatorial Optimization [9]. It is a search strategy commonly used when

a good heuristic on the possible actions is available for driving the search. The

principle is to restrict the number of decisions deviating from the heuristic choices

(i.e. a discrepancy) by a threshold. This will explore the subset of solutions that

are likely to be good according to the heuristic, but it will also explore solutions

where the heuristic has been reconsidered a given number of times (i.e. the

number of discrepancies).

Figure 1 gives an example of a binary search tree requiring a LDS of level 2

to be solved.

Nested Search versus Limited Discrepancy Search 3

Fig. 1. A binary search tree. The heuristic is to choose the left move. The black squares

are the solutions. LDS does not ﬁnd one of the two solutions using only one discrepancy

since the path to the two solutions requires two discrepancies. A level 2 LDS solves the

problem.

-2 -2 -1 0

-3 -2 0 -1

Fig. 2. The same tree as in Figure 1 with scores of the playouts at the leaves. A score

of 0 means the problem is solved. A NS of level 1 ﬁnds a solution as it uses the scores

of the playouts to direct its search.

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

NestedSearchversusLimitedDiscrepancySearchTristanCazenaveLAMSADE,UniversitéParisDauphine-PSL,CNRS,Paris,FranceAbstract.LimitedDiscrepancySearch(LDS)isapopularalgorithmtosearchastatespacewithaheuristictoorderthepossibleactions.NestedSearch(NS)isanotheralgorithmtosearchastatespacewiththesameheuristic....

展开>> 收起<<

Nested Search versus Limited Discrepancy Search Tristan Cazenave LAMSADE Université Paris Dauphine - PSL CNRS Paris France.pdf

共15页,预览3页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

Nested Search versus Limited Discrepancy Search Tristan Cazenave LAMSADE Université Paris Dauphine - PSL CNRS Paris France

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: