Seeding and Hill-Climbing

In the last blog I have talked a little bit of searching, in this blog I would like to share something about seeding and hill-climbing idea with you.

As I’ve concluded before, criteria are essential to simplify problems. It is always hard to find the optimal (the best) solution for a realistic problem, because the solution pool (the set of all possible solutions) is very large. For example, if you want to predict which dishes your partner want to have for dinner, the possible answer is so many! Even he or she would not know what the answer is. That is why I prefer Width-First Searching. In this particular problem, what for dinner, I prefer to ask the origin of dishes. “Would you like to have some Korean dishes like fried chicken or the seafood and tofu soup or should we try some burgers? We can also do some Chinese dished by ourselves.” This is a utilization of the concept of Width-First Searching. However, it is not the entire procedure of Width-First Searching. If I stick to the Width-First concept, I should have iterated every possible type of dishes, which will definitely ruin the plan for the dinner. So I randomly pick some types, or to be honest, I picked some types that I think my partner would like to choose from. This is an example of seeding.

The concept of seeding is to set starting points for a searching method, mostly Depth-First Searching. From my point of view, Depth-First Searching with seeding is a combination of Depth-First and Width-First concepts.

Why we need seeding? Does it have a visible meaning?

Yes, it does.

As it shows in the image above, the starting point can influence the efficiency of finding the optimal solution. If the starting point is near the global maxima, it is great. But if the starting point is the small circle shown in the image, it will probably find the local maxima because it might be good enough according to the criteria. Since we don’t know what the best performance is, we tend to think that a best performance within a range can somehow represent the overall performance. This is the local maxima dilemma. To solve this problem well, a new kind of algorithm is proposed, it is called hill climbing algorithm. It is a great algorithm used in many areas, but good seeding method can sometimes replace the hill climbing for satisfying outcomes. I will talk about it in details in the hill climbing blog.