The impact of problem structure on search is a relevant issue in artificial intelligence and related areas. Among the possible approaches to analyze problem structure, the one referring to constraint graph enables to relate graph parameters and characteristics with search algorithm behavior. In this work, we investigate the behavior of local search applied to SAT instances associated to graphs with small-world topology. Small-world graphs, such as friendship networks, have low characteristic path length and high clustering. In this work, we first present a procedure to generate SAT instances characterized by an interaction graph with a small-world topology. Then we show experimental results concerning the behavior of local search algorithms applied to this benchmark.
On the impact of small-world on local search / Roli, Andrea. - STAMPA. - 3673:(2005), pp. 13-24. (Intervento presentato al convegno 9th Congress of the Italian Association for Artificial Intelligence tenutosi a Milano nel Sept. 2005).
On the impact of small-world on local search
ROLI, ANDREA
2005
Abstract
The impact of problem structure on search is a relevant issue in artificial intelligence and related areas. Among the possible approaches to analyze problem structure, the one referring to constraint graph enables to relate graph parameters and characteristics with search algorithm behavior. In this work, we investigate the behavior of local search applied to SAT instances associated to graphs with small-world topology. Small-world graphs, such as friendship networks, have low characteristic path length and high clustering. In this work, we first present a procedure to generate SAT instances characterized by an interaction graph with a small-world topology. Then we show experimental results concerning the behavior of local search algorithms applied to this benchmark.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
