LSVF: LEAST SUGGESTED VALUE FIRST - A New Search Heuristic to Reduce the Amount of Backtracking Calls in CSP

Cleyton Mário de Oliveira Rodrigues, Eric Rommel Dantas Galvão, Ryan Ribeiro de Azevedo, Marcos Aurélio Almeida da Silva

2010

Abstract

Along the years, many researches in the Artificial Intelligence (AI) field seek for new algorithms to reduce drastically the amount of memory and time consumed for general searches in the family of constraint satisfaction problems. Normally, these improvements are reached with the use of some heuristics which either prune useless tree search branches or even “indicate” the path to reach the solution (many times, the optimal solution) more easily. Many heuristics were proposed in the literature, like Static/ Dynamic Highest Degree heuristic (SHD/DHD), Most Constraint Variable (MCV), Least Constraining Value (LCV), and while some can be used at the pre-processing time, others just at running time. In this paper we propose a new pre-processing search heuristic to reduce the amount of backtracking calls, namely the Least Suggested Value First (LSVF). LSVF emerges as a practical solution whenever the LCV can not distinguish how much a value is constrained. We present a pedagogical example to introduce the heuristics, realized through the general Constraint Logic Programming CHRv, as well as the preliminary results.

Paper Citation

in Harvard Style

Mário de Oliveira Rodrigues C., Rommel Dantas Galvão E., Ribeiro de Azevedo R. and Aurélio Almeida da Silva M. (2010). LSVF: LEAST SUGGESTED VALUE FIRST - A New Search Heuristic to Reduce the Amount of Backtracking Calls in CSP . In Proceedings of the 2nd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART, ISBN 978-989-674-021-4, pages 416-421. DOI: 10.5220/0002761504160421

in Bibtex Style

@conference{icaart10,
author={Cleyton Mário de Oliveira Rodrigues and Eric Rommel Dantas Galvão and Ryan Ribeiro de Azevedo and Marcos Aurélio Almeida da Silva},
title={LSVF: LEAST SUGGESTED VALUE FIRST - A New Search Heuristic to Reduce the Amount of Backtracking Calls in CSP},
booktitle={Proceedings of the 2nd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,},
year={2010},
pages={416-421},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0002761504160421},
isbn={978-989-674-021-4},
}

in EndNote Style

TY - CONF
JO - Proceedings of the 2nd International Conference on Agents and Artificial Intelligence - Volume 1: ICAART,
TI - LSVF: LEAST SUGGESTED VALUE FIRST - A New Search Heuristic to Reduce the Amount of Backtracking Calls in CSP
SN - 978-989-674-021-4
AU - Mário de Oliveira Rodrigues C.
AU - Rommel Dantas Galvão E.
AU - Ribeiro de Azevedo R.
AU - Aurélio Almeida da Silva M.
PY - 2010
SP - 416
EP - 421
DO - 10.5220/0002761504160421