Greedy search algorithm

.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}

Currently I am a new to the Artificial Intelligent. I have a problem on greedy search algorithm. One of the question I saw on tutorial but cant understand how to answer them. Please help me. Any help much appreciated.

Consider the given figure 1. The values in each node represent the heuristic cost from that node
to goal node (G) and the values within the arcs represent the path cost between two nodes.

[![1.If B is the starting node and G is the goal node,



(i) Find the traversal using Greedy Search Algorithm.



(ii) Find the traversal using A* Search Algorithm







2. Using the result of part(1) show that greedy search is not optimal.

enter image description here

asked Nov 25 '18 at 2:18

user9947358

1

Greedy algorithm won't take the heuristic value into consideration: at each node the algorithm will take the lowest cost possible. B -> C -> D -> H -> G = 5+6+4+3 = 18

– ihavenoidea
Nov 25 '18 at 2:30

1

The Greedy algorithm follows the path B -> C -> D -> H -> G which has the cost of 18, and the heuristic algorithm follows the path B -> E -> F -> H -> G which has the cost 25. This specific example shows that heuristic search is costlier. This example is not well crafted to show that solution of greedy search is not optimal.

– Lavish Kothari
Nov 25 '18 at 2:40

Thanks for the promptly response. However about that optimal solution. How to identifying? How to calculate? Your help much much appreciated.

– user9947358
Nov 25 '18 at 2:41

add a comment |

Consider the given figure 1. The values in each node represent the heuristic cost from that node
to goal node (G) and the values within the arcs represent the path cost between two nodes.

[![1.If B is the starting node and G is the goal node,



(i) Find the traversal using Greedy Search Algorithm.



(ii) Find the traversal using A* Search Algorithm







2. Using the result of part(1) show that greedy search is not optimal.

enter image description here

asked Nov 25 '18 at 2:18

user9947358

1

Greedy algorithm won't take the heuristic value into consideration: at each node the algorithm will take the lowest cost possible. B -> C -> D -> H -> G = 5+6+4+3 = 18

– ihavenoidea
Nov 25 '18 at 2:30

1

The Greedy algorithm follows the path B -> C -> D -> H -> G which has the cost of 18, and the heuristic algorithm follows the path B -> E -> F -> H -> G which has the cost 25. This specific example shows that heuristic search is costlier. This example is not well crafted to show that solution of greedy search is not optimal.

– Lavish Kothari
Nov 25 '18 at 2:40

Thanks for the promptly response. However about that optimal solution. How to identifying? How to calculate? Your help much much appreciated.

– user9947358
Nov 25 '18 at 2:41

add a comment |

Consider the given figure 1. The values in each node represent the heuristic cost from that node
to goal node (G) and the values within the arcs represent the path cost between two nodes.

[![1.If B is the starting node and G is the goal node,



(i) Find the traversal using Greedy Search Algorithm.



(ii) Find the traversal using A* Search Algorithm







2. Using the result of part(1) show that greedy search is not optimal.

enter image description here

asked Nov 25 '18 at 2:18

user9947358

Consider the given figure 1. The values in each node represent the heuristic cost from that node
to goal node (G) and the values within the arcs represent the path cost between two nodes.

[![1.If B is the starting node and G is the goal node,



(i) Find the traversal using Greedy Search Algorithm.



(ii) Find the traversal using A* Search Algorithm







2. Using the result of part(1) show that greedy search is not optimal.

enter image description here

artificial-intelligence

asked Nov 25 '18 at 2:18

user9947358

asked Nov 25 '18 at 2:18

user9947358

asked Nov 25 '18 at 2:18

user9947358

asked Nov 25 '18 at 2:18

user9947358

asked Nov 25 '18 at 2:18

user9947358

1

Greedy algorithm won't take the heuristic value into consideration: at each node the algorithm will take the lowest cost possible. B -> C -> D -> H -> G = 5+6+4+3 = 18

– ihavenoidea
Nov 25 '18 at 2:30

1

The Greedy algorithm follows the path B -> C -> D -> H -> G which has the cost of 18, and the heuristic algorithm follows the path B -> E -> F -> H -> G which has the cost 25. This specific example shows that heuristic search is costlier. This example is not well crafted to show that solution of greedy search is not optimal.

– Lavish Kothari
Nov 25 '18 at 2:40

Thanks for the promptly response. However about that optimal solution. How to identifying? How to calculate? Your help much much appreciated.

– user9947358
Nov 25 '18 at 2:41

add a comment |

1

Greedy algorithm won't take the heuristic value into consideration: at each node the algorithm will take the lowest cost possible. B -> C -> D -> H -> G = 5+6+4+3 = 18

– ihavenoidea
Nov 25 '18 at 2:30

1

The Greedy algorithm follows the path B -> C -> D -> H -> G which has the cost of 18, and the heuristic algorithm follows the path B -> E -> F -> H -> G which has the cost 25. This specific example shows that heuristic search is costlier. This example is not well crafted to show that solution of greedy search is not optimal.

– Lavish Kothari
Nov 25 '18 at 2:40

Thanks for the promptly response. However about that optimal solution. How to identifying? How to calculate? Your help much much appreciated.

– user9947358
Nov 25 '18 at 2:41

Greedy algorithm won't take the heuristic value into consideration: at each node the algorithm will take the lowest cost possible. B -> C -> D -> H -> G = 5+6+4+3 = 18

– ihavenoidea
Nov 25 '18 at 2:30

The Greedy algorithm follows the path B -> C -> D -> H -> G which has the cost of 18, and the heuristic algorithm follows the path B -> E -> F -> H -> G which has the cost 25. This specific example shows that heuristic search is costlier. This example is not well crafted to show that solution of greedy search is not optimal.

– Lavish Kothari
Nov 25 '18 at 2:40

Thanks for the promptly response. However about that optimal solution. How to identifying? How to calculate? Your help much much appreciated.

– user9947358
Nov 25 '18 at 2:41

add a comment |

1 Answer
1

active

oldest

votes

I assume that the greedy search algorithm that you refer to is having the greedy selection strategy as follows: Select the next node which is adjacent to the current node and has the least cost/distance from the current node. Note that the greedy solution don't use heuristic costs at all.

Consider the following figure well crafted such that it proves that greedy solution is not optimal.
enter image description here

The path highlighted with red shows the path taken by Greedy Algorithm and the path highlighted with green shows the path taken by Heuristic A* algorithm.

Explanation:

Greedy algorithm

Starting from Node B, the greedy algorithm sees the path costs (for A it's 6, for C it's 6 and for E it's 5)

We greedily move to node E because it is having least path value.

From E we have only one option to move to F

From F we again have only one option to move to H and from H we move to G (Goal state/node)

Cost for the path by Greedy Algorithm (highlighted in red): B -> E -> F -> H -> G = 5+6+6+3 = 20

A* algorithm (before going forward have a look at the wiki page for A* algorithm and understand what g(n) and h(n) are if you haven't already understood this concept):

Starting from node B, we have three options A, C and E. For each node we calculate f(n) = g(n) + h(n). Here g(n) is the immediate cost on the arc and h(n) is the heuristic value on the node
- For node A, f(n) = 6 + 12 = 18
- For node B, f(n) = 6 + 10 = 16
- For node C, f(n) = 5 + 14 = 19

We choose to proceed with the node that has least f(n). So we move to node B.

We proceed in the similar fashion and find the path highlighted in green.

The path by A* algorithm is B -> C -> D -> H -> G and it's cost is 6+6+4+3 = 19

By the above example we can see that the cost of heuristic path is less than greedy algorithm. Hence greedy algorithm is not always optimal.

answered Nov 25 '18 at 3:05

Lavish Kothari

974816

@MohamedNasik I've already explained in the answer how I've chosen the paths for both Greedy and A* algorithm. If you are asking me how I'm choosing my strategy for Greedy, it's just one of the strategy. You can go with Dijkstra algorithm which is also greedy (and always gives optimal solution for single source non-negative weight edges). But for here I think the strategy I described will suffice.

– Lavish Kothari
Nov 25 '18 at 3:27

Another question i want to ask from you my dear, In the example (top original) which I mentioned above, difficult to find the optimal solution. It takes higher value. How to proof which can be a not an optimal solution

– user9947358
Nov 25 '18 at 3:39

For a general graph, you can do an exhaustive search and find the optimal solution, but most of the times (as it is in your case) you can find the optimal solution using Dijkstra Algorithm. Note that, neither greedy not A* assures that it will give you an optimal solution. HTH :)

– Lavish Kothari
Nov 25 '18 at 3:49

add a comment |

Your Answer

StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});

}
});

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53464125%2fgreedy-search-algorithm%23new-answer', 'question_page');
}
);

Post as a guest

Name

Required, but never shown

1 Answer
1

active

oldest

votes

1 Answer
1

active

oldest

votes

Consider the following figure well crafted such that it proves that greedy solution is not optimal.
enter image description here

The path highlighted with red shows the path taken by Greedy Algorithm and the path highlighted with green shows the path taken by Heuristic A* algorithm.

Explanation:

Greedy algorithm

Starting from Node B, the greedy algorithm sees the path costs (for A it's 6, for C it's 6 and for E it's 5)

We greedily move to node E because it is having least path value.

From E we have only one option to move to F

From F we again have only one option to move to H and from H we move to G (Goal state/node)

Cost for the path by Greedy Algorithm (highlighted in red): B -> E -> F -> H -> G = 5+6+6+3 = 20

A* algorithm (before going forward have a look at the wiki page for A* algorithm and understand what g(n) and h(n) are if you haven't already understood this concept):

Starting from node B, we have three options A, C and E. For each node we calculate f(n) = g(n) + h(n). Here g(n) is the immediate cost on the arc and h(n) is the heuristic value on the node
- For node A, f(n) = 6 + 12 = 18
- For node B, f(n) = 6 + 10 = 16
- For node C, f(n) = 5 + 14 = 19

We choose to proceed with the node that has least f(n). So we move to node B.

We proceed in the similar fashion and find the path highlighted in green.

The path by A* algorithm is B -> C -> D -> H -> G and it's cost is 6+6+4+3 = 19

By the above example we can see that the cost of heuristic path is less than greedy algorithm. Hence greedy algorithm is not always optimal.

answered Nov 25 '18 at 3:05

Lavish Kothari

974816

@MohamedNasik I've already explained in the answer how I've chosen the paths for both Greedy and A* algorithm. If you are asking me how I'm choosing my strategy for Greedy, it's just one of the strategy. You can go with Dijkstra algorithm which is also greedy (and always gives optimal solution for single source non-negative weight edges). But for here I think the strategy I described will suffice.

– Lavish Kothari
Nov 25 '18 at 3:27

Another question i want to ask from you my dear, In the example (top original) which I mentioned above, difficult to find the optimal solution. It takes higher value. How to proof which can be a not an optimal solution

– user9947358
Nov 25 '18 at 3:39

For a general graph, you can do an exhaustive search and find the optimal solution, but most of the times (as it is in your case) you can find the optimal solution using Dijkstra Algorithm. Note that, neither greedy not A* assures that it will give you an optimal solution. HTH :)

– Lavish Kothari
Nov 25 '18 at 3:49

add a comment |

Consider the following figure well crafted such that it proves that greedy solution is not optimal.
enter image description here

The path highlighted with red shows the path taken by Greedy Algorithm and the path highlighted with green shows the path taken by Heuristic A* algorithm.

Explanation:

Greedy algorithm

Starting from Node B, the greedy algorithm sees the path costs (for A it's 6, for C it's 6 and for E it's 5)

We greedily move to node E because it is having least path value.

From E we have only one option to move to F

From F we again have only one option to move to H and from H we move to G (Goal state/node)

Cost for the path by Greedy Algorithm (highlighted in red): B -> E -> F -> H -> G = 5+6+6+3 = 20

A* algorithm (before going forward have a look at the wiki page for A* algorithm and understand what g(n) and h(n) are if you haven't already understood this concept):

Starting from node B, we have three options A, C and E. For each node we calculate f(n) = g(n) + h(n). Here g(n) is the immediate cost on the arc and h(n) is the heuristic value on the node
- For node A, f(n) = 6 + 12 = 18
- For node B, f(n) = 6 + 10 = 16
- For node C, f(n) = 5 + 14 = 19

We choose to proceed with the node that has least f(n). So we move to node B.

We proceed in the similar fashion and find the path highlighted in green.

The path by A* algorithm is B -> C -> D -> H -> G and it's cost is 6+6+4+3 = 19

By the above example we can see that the cost of heuristic path is less than greedy algorithm. Hence greedy algorithm is not always optimal.

answered Nov 25 '18 at 3:05

Lavish Kothari

974816

@MohamedNasik I've already explained in the answer how I've chosen the paths for both Greedy and A* algorithm. If you are asking me how I'm choosing my strategy for Greedy, it's just one of the strategy. You can go with Dijkstra algorithm which is also greedy (and always gives optimal solution for single source non-negative weight edges). But for here I think the strategy I described will suffice.

– Lavish Kothari
Nov 25 '18 at 3:27

Another question i want to ask from you my dear, In the example (top original) which I mentioned above, difficult to find the optimal solution. It takes higher value. How to proof which can be a not an optimal solution

– user9947358
Nov 25 '18 at 3:39

For a general graph, you can do an exhaustive search and find the optimal solution, but most of the times (as it is in your case) you can find the optimal solution using Dijkstra Algorithm. Note that, neither greedy not A* assures that it will give you an optimal solution. HTH :)

– Lavish Kothari
Nov 25 '18 at 3:49

add a comment |

Consider the following figure well crafted such that it proves that greedy solution is not optimal.
enter image description here

The path highlighted with red shows the path taken by Greedy Algorithm and the path highlighted with green shows the path taken by Heuristic A* algorithm.

Explanation:

Greedy algorithm

Starting from Node B, the greedy algorithm sees the path costs (for A it's 6, for C it's 6 and for E it's 5)

We greedily move to node E because it is having least path value.

From E we have only one option to move to F

From F we again have only one option to move to H and from H we move to G (Goal state/node)

Cost for the path by Greedy Algorithm (highlighted in red): B -> E -> F -> H -> G = 5+6+6+3 = 20

A* algorithm (before going forward have a look at the wiki page for A* algorithm and understand what g(n) and h(n) are if you haven't already understood this concept):

Starting from node B, we have three options A, C and E. For each node we calculate f(n) = g(n) + h(n). Here g(n) is the immediate cost on the arc and h(n) is the heuristic value on the node
- For node A, f(n) = 6 + 12 = 18
- For node B, f(n) = 6 + 10 = 16
- For node C, f(n) = 5 + 14 = 19

We choose to proceed with the node that has least f(n). So we move to node B.

We proceed in the similar fashion and find the path highlighted in green.

The path by A* algorithm is B -> C -> D -> H -> G and it's cost is 6+6+4+3 = 19

By the above example we can see that the cost of heuristic path is less than greedy algorithm. Hence greedy algorithm is not always optimal.

answered Nov 25 '18 at 3:05

Lavish Kothari

974816

Consider the following figure well crafted such that it proves that greedy solution is not optimal.
enter image description here

The path highlighted with red shows the path taken by Greedy Algorithm and the path highlighted with green shows the path taken by Heuristic A* algorithm.

Explanation:

Greedy algorithm

Starting from Node B, the greedy algorithm sees the path costs (for A it's 6, for C it's 6 and for E it's 5)

We greedily move to node E because it is having least path value.

From E we have only one option to move to F

From F we again have only one option to move to H and from H we move to G (Goal state/node)

Cost for the path by Greedy Algorithm (highlighted in red): B -> E -> F -> H -> G = 5+6+6+3 = 20

A* algorithm (before going forward have a look at the wiki page for A* algorithm and understand what g(n) and h(n) are if you haven't already understood this concept):

Starting from node B, we have three options A, C and E. For each node we calculate f(n) = g(n) + h(n). Here g(n) is the immediate cost on the arc and h(n) is the heuristic value on the node
- For node A, f(n) = 6 + 12 = 18
- For node B, f(n) = 6 + 10 = 16
- For node C, f(n) = 5 + 14 = 19

We choose to proceed with the node that has least f(n). So we move to node B.

We proceed in the similar fashion and find the path highlighted in green.

The path by A* algorithm is B -> C -> D -> H -> G and it's cost is 6+6+4+3 = 19

By the above example we can see that the cost of heuristic path is less than greedy algorithm. Hence greedy algorithm is not always optimal.

answered Nov 25 '18 at 3:05

Lavish Kothari

974816

answered Nov 25 '18 at 3:05

Lavish Kothari

974816

answered Nov 25 '18 at 3:05

Lavish Kothari

974816

answered Nov 25 '18 at 3:05

Lavish Kothari

974816

@MohamedNasik I've already explained in the answer how I've chosen the paths for both Greedy and A* algorithm. If you are asking me how I'm choosing my strategy for Greedy, it's just one of the strategy. You can go with Dijkstra algorithm which is also greedy (and always gives optimal solution for single source non-negative weight edges). But for here I think the strategy I described will suffice.

– Lavish Kothari
Nov 25 '18 at 3:27

Another question i want to ask from you my dear, In the example (top original) which I mentioned above, difficult to find the optimal solution. It takes higher value. How to proof which can be a not an optimal solution

– user9947358
Nov 25 '18 at 3:39

For a general graph, you can do an exhaustive search and find the optimal solution, but most of the times (as it is in your case) you can find the optimal solution using Dijkstra Algorithm. Note that, neither greedy not A* assures that it will give you an optimal solution. HTH :)

– Lavish Kothari
Nov 25 '18 at 3:49

add a comment |

@MohamedNasik I've already explained in the answer how I've chosen the paths for both Greedy and A* algorithm. If you are asking me how I'm choosing my strategy for Greedy, it's just one of the strategy. You can go with Dijkstra algorithm which is also greedy (and always gives optimal solution for single source non-negative weight edges). But for here I think the strategy I described will suffice.

– Lavish Kothari
Nov 25 '18 at 3:27

Another question i want to ask from you my dear, In the example (top original) which I mentioned above, difficult to find the optimal solution. It takes higher value. How to proof which can be a not an optimal solution

– user9947358
Nov 25 '18 at 3:39

For a general graph, you can do an exhaustive search and find the optimal solution, but most of the times (as it is in your case) you can find the optimal solution using Dijkstra Algorithm. Note that, neither greedy not A* assures that it will give you an optimal solution. HTH :)

– Lavish Kothari
Nov 25 '18 at 3:49

@MohamedNasik I've already explained in the answer how I've chosen the paths for both Greedy and A* algorithm. If you are asking me how I'm choosing my strategy for Greedy, it's just one of the strategy. You can go with Dijkstra algorithm which is also greedy (and always gives optimal solution for single source non-negative weight edges). But for here I think the strategy I described will suffice.

– Lavish Kothari
Nov 25 '18 at 3:27

Another question i want to ask from you my dear, In the example (top original) which I mentioned above, difficult to find the optimal solution. It takes higher value. How to proof which can be a not an optimal solution

– user9947358
Nov 25 '18 at 3:39

For a general graph, you can do an exhaustive search and find the optimal solution, but most of the times (as it is in your case) you can find the optimal solution using Dijkstra Algorithm. Note that, neither greedy not A* assures that it will give you an optimal solution. HTH :)

– Lavish Kothari
Nov 25 '18 at 3:49

add a comment |

draft saved

draft discarded

Thanks for contributing an answer to Stack Overflow!

Please be sure to answer the question. Provide details and share your research!

But avoid …

Asking for help, clarification, or responding to other answers.

Making statements based on opinion; back them up with references or personal experience.

To learn more, see our tips on writing great answers.

draft saved

draft discarded

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Sign up or log in

StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});

Post as a guest

Name

Required, but never shown

Name

Required, but never shown

Name

Required, but never shown

This page is only for reference, If you need detailed information, please check here

搜尋此網誌

Wsrtjtyk