Artificial Intelligence Stack Exchange
Artificial Intelligence Stack Exchange

Questions tagged [hill-climbing]

For questions related to the family of algorithms called "hill climbing" (in the context of AI).

For more info, see e.g. https://en.wikipedia.org/wiki/Hill_climbing.

22 questions
10
votes
2 answers

What are the limitations of the hill climbing algorithm and how to overcome them?

What are the limitations of the hill climbing algorithm? How can we overcome these limitations?
Abbas Ali
  • 576
  • 4
  • 10
  • 17
9
votes
4 answers

When to choose Stochastic Hill Climbing over Steepest Hill Climbing?

Stochastic Hill Climbing generally performs worse than Steepest Hill Climbing, but what are the cases in which the former performs better?
Rohan Sharma
  • 91
  • 1
  • 4
9
votes
2 answers

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 to find a subset of this set such that the sum of…
K.N
  • 191
  • 2
8
votes
2 answers

Are there local search algorithms that make use of memory to give better solutions?

I have been studying local search algorithms such as greedy hill-climbing, stochastic hill-climbing, simulated annealing, etc. I have noticed that most of these methods take up very little memory as compared to systematic search techniques. Are…
quantumcoder
  • 81
  • 4
6
votes
2 answers

How can I formulate the map colouring problem as a hill climbing search problem?

I have a map. I need to colour it with $k$ colours, such that two adjacent regions do not share a colour. How can I formulate the map colouring problem as a hill climbing search problem?
jrk
  • 105
  • 2
  • 5
6
votes
2 answers

Why is the larger value, as opposed to the smaller one, chosen, in the hill climbing algorithm?

In the hill climbing algorithm, the greater value, compared to the current value, is selected, but I cannot understand why it takes the larger value instead of the smaller one. Why is that? I greatly appreciate the inclusion of figures in your…
Khan
  • 61
  • 1
5
votes
1 answer

How is simulated annealing better than hill climbing methods?

In hill climbing methods, at each step, the current solution is replaced with the best neighbour (that is, the neighbour with highest/smallest value). In simulated annealing, "downhills" moves are allowed. What are the advantages of simulated…
Huma Qaseem
  • 199
  • 1
  • 3
  • 12
5
votes
1 answer

How do I solve the knapsack problem using the hill climbing algorithm?

I need to solve the knapsack problem using hill climbing algorithm (I need to write a program). But I'm clueless about how to do it. My code should contain a method called knapsack, the method takes two parameters, the first is a 2xN array of…
lujain
  • 51
  • 1
  • 2
4
votes
1 answer

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?
Iram Shah
  • 315
  • 2
  • 5
  • 14
3
votes
1 answer

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 maximum?
user29521
  • 61
  • 3
3
votes
1 answer

How does best-first search differ from hill-climbing?

How does best-first search differ from hill-climbing?
Ayesha Sajjad
  • 31
  • 1
  • 3
3
votes
1 answer

What is the difference between hill-climbing and greedy best-first search algorithms?

While watching MIT's lectures about search, 4. Search: Depth-First, Hill Climbing, Beam, the professor explains the hill-climbing search in a way that is similar to the best-first search. At around the 35 mins mark, the professor enqueues the paths…
calveeen
  • 1,311
  • 9
  • 18
2
votes
1 answer

What should I do when the new generated state has bigger distance to the goal than the parent state?

I have implemented the hill climbing algorithm, with side away steps, which can increase the rate of success, because, when you don't have new generated states, you can go back to previous level and choose from there another state. What should I do…
Darius Ionut
  • 31
  • 3
2
votes
0 answers

Which heuristic function should I use for the ColorShapeLinks game?

For learning purposes, I am trying to implement the minimax algorithm for the ColorShapeLinks game, which is similar to connect 4, except the fact that it combines both shape and color as the winning conditions, with a shape having priority over…
Errata
  • 21
  • 2
1
vote
1 answer

Should the mutation be applied with the hill climbing algorithm?

As far as I understand, the hill climbing algorithm is a local search algorithm that selects any random solution as an initial solution to start the search. Then, should we apply an operation (i.e., mutation) on the selected solution to get a new…
Nasser
  • 211
  • 2
  • 5
1
2