# Questions tagged [local-search]

For questions related to local search algorithms used in AI (e.g. 2-opt or hill climbing).

10 questions
Filter by
Sorted by
Tagged with
1 vote
31 views

### CSP heuristic to simultaneously reduce conflicts and find near optimal assignment

I am trying to design a good heuristic to solve a constraint satisfaction problem (CSP). I think that a possible heuristic to use is $$h_1(\text{state}) = \text{number of conflicts in state}$$ However,...
3k views

### What is the difference between Stochastic Hill Climbing and Simulated Annealing?

I am reading about local search: hill climbing, and its types, and simulated annealing One of the hill climbing versions is "stochastic hill climbing", which has the following definition: ...
• 217
1 vote
425 views

### Can we solve an $8 \times 8$ sliding puzzle using hill climbing?

Can we solve an $8 \times 8$ sliding puzzle using a random-restart hill climbing technique (steepest-ascent)? If yes, how much computing power will this need? And what is the maximum $n \times n$ that ...
• 11
461 views

### How can I solve the zero subset sum problem with hill climbing?

I want to solve the zero subset sum problem with the hill-climbing algorithm, but I am not sure I found a good state space for this. Here is the problem: consider we have a set of numbers and we want ...
• 181
396 views

### Why is a mix of greedy and random usually "best" for stochastic local search?

I read that a mix of "greedy" and "random" are ideal for stochastic local search (SLS), but I'm not sure why. It mentioned that the greedy finds the local minima and the randomness avoids getting ...
• 351
1k views

### Why does the hill climbing algorithm only produce a local maximum?

Apparently, the hill climbing algorithm just produces a local maximum, and not necessarily a global optimum. It's stuck on a local maximum. Why does hill climbing algorithm only produce a local ...
249 views

### What is the basic purpose of local search methods?

I read about the hill climbing algorithms, the simulating annealing algorithm, but I am confused. What is the basic purpose of local search methods?
• 315
16k views

### What is an objective function?

Local search algorithms are useful for solving pure optimization problems, in which the aim is to find the best state according to an objective function. My question is what is the objective function?
• 566