Greedy local search is a very important scarch algorithm. It has many names in t
ID: 674473 • Letter: G
Question
Greedy local search is a very important scarch algorithm. It has many names in the literature such as hill-climbing, gradient descent, and steepest descent. In this exercise, we would like to understand some fundamental properties of greedy local scarch. To do this, please answer the following questions If you haven't noticed already, we sometimes speak of finding a maximum, such as hill-climbing or greedy ascent, but we also sometimes speak of finding a minimum, such as greedy descent Explain why the two views arc equivalent. That is, explain why an algorithm that finds the maximum of a real-valued function f(x) can also be used to find its minimum, and vice versa.Explanation / Answer
It is true in fact it can be used to find minimum of a function as well. If a function is used to find a maximum we can use the same function to find the minimum as well. In the same running time it can be used to find the minimum also.
Just take a new variable called min and iterate over the given array. While you are iterating you can keep track of both minimum and maximum variable and can then find the same.
To give a small example:
for(i=0;i<size;i++)
{
int max=0;
if(arr[i]>max)
max=arr[i];
}
Now we can update the above code to get the minimum also.
for(i=0;i<size;i++)
{
int max=0;
int min=0;
if(arr[i]>max)
max=arr[i];
if(arr[i]<min)
min=arr[i];
}
If you look at the above running time will be same for both but we can get minimum value as well.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.