ºÝºÝߣ

ºÝºÝߣShare a Scribd company logo
A* Search Algorithm
ï‚´ A* Search Algorithm solved with numeric example
A* Search Algorithm solved with numeric example
A* Search Algorithm solved with numeric example
A* Search Algorithm solved with numeric example
A* Search Algorithm solved with numeric example
A* Search Algorithm solved with numeric example
A* Search Algorithm solved with numeric example
A* Search Algorithm solved with numeric example
A* Search Algorithm solved with numeric example
Heuristic Function h(n) and how to make it
Heuristic Function h(n) and how to make it
Optimality of A* Search Algorithm
ï‚´ Heuristic may be:
ï‚´ h(n) > actual cost
ï‚´ h(n) = actual cost
ï‚´ h(n) < actual cost
ï‚´ (1) h(n) > actual cost [Optimum solution can be overlooked, optimum solution is not
possible]
ï‚´ (2) h(n) = actual cost [Best case scenario, if h(n) approximates actual cost, searching
uses minimum of node to the goal]
ï‚´ (3) h(n) < actual cost [ Admissible, Consistent Heuristics]
Optimality of A* Search Algorithm
h(n) > actual cost [Optimum solution can be overlooked, optimum solution is not
possible]
Optimality of A* Search Algorithm
h(n) > actual cost [Optimum solution can be overlooked, optimum solution is not
possible]
Optimality of A* Search Algorithm
h(n) > actual cost [Optimum solution can be overlooked, optimum solution is not
possible]
b………….> dest and cost (7+2+0=9) , or ……….>a and cost (2+9=11)
Optimality of A* Search Algorithm
h(n) > actual cost [Optimum solution can be overlooked, optimum solution is not
possible]
b………….> dest and cost (7+2+0=9) , or ……….>a and cost (2+9=11)
Actual cost from Sabdest =2+3+2=7
h(n)=10 > actual cost = 7
Optimality of A* Search Algorithm
ï‚´ h(n) < actual cost, if this relation maintains for every node, then we say this
this Admissible Heuristics.
Optimality of A* Search Algorithm
Optimality of A* Search Algorithm
Optimality of A* Search Algorithm
Optimality of A* Search Algorithm
Optimality of A* Search Algorithm
If Heuristic admissible but not consistent, it may not be provided optimum solution.
For optimum solution, heuristic must be consistent. If it consistent, it must be admissible.
Optimality of A* Search Algorithm
Random Variable
ï‚´ The domain

More Related Content

Similar to A Star search algorithm with example (num) (13)

Artificial Intelligence and Machine Learning.pptx
Artificial Intelligence and Machine Learning.pptxArtificial Intelligence and Machine Learning.pptx
Artificial Intelligence and Machine Learning.pptx
bobertbaratheon74
Ìý
Heuristic Searching: A* Search
Heuristic Searching: A* SearchHeuristic Searching: A* Search
Heuristic Searching: A* Search
IOSR Journals
Ìý
A* and Min-Max Searching Algorithms in AI , DSA.pdf
A* and Min-Max Searching Algorithms in AI , DSA.pdfA* and Min-Max Searching Algorithms in AI , DSA.pdf
A* and Min-Max Searching Algorithms in AI , DSA.pdf
CS With Logic
Ìý
Apriori algorithm
Apriori algorithmApriori algorithm
Apriori algorithm
nouraalkhatib
Ìý
Heuristic Search Techniques in Artificial Intelligence
Heuristic Search Techniques in Artificial IntelligenceHeuristic Search Techniques in Artificial Intelligence
Heuristic Search Techniques in Artificial Intelligence
Mehak533057
Ìý
Search 2
Search 2Search 2
Search 2
Tribhuvan University
Ìý
Heuristic Searching Algorithms Artificial Intelligence.pptx
Heuristic Searching Algorithms Artificial Intelligence.pptxHeuristic Searching Algorithms Artificial Intelligence.pptx
Heuristic Searching Algorithms Artificial Intelligence.pptx
Swagat Praharaj
Ìý
Searchadditional2
Searchadditional2Searchadditional2
Searchadditional2
chandsek666
Ìý
Informed Search.pptx
Informed Search.pptxInformed Search.pptx
Informed Search.pptx
MohanKumarP34
Ìý
Game Paper
Game PaperGame Paper
Game Paper
Siddharth Gupta
Ìý
A* Algorithm
A* AlgorithmA* Algorithm
A* Algorithm
maharajdey
Ìý
Heuristic Search, Best First Search.pptx
Heuristic Search, Best First Search.pptxHeuristic Search, Best First Search.pptx
Heuristic Search, Best First Search.pptx
devhamnah
Ìý
Astar.ppt hjguyjgukyjgoyjgugukgulgoyulgyilglyi
Astar.ppt hjguyjgukyjgoyjgugukgulgoyulgyilglyiAstar.ppt hjguyjgukyjgoyjgugukgulgoyulgyilglyi
Astar.ppt hjguyjgukyjgoyjgugukgulgoyulgyilglyi
kamaleshs183
Ìý
Artificial Intelligence and Machine Learning.pptx
Artificial Intelligence and Machine Learning.pptxArtificial Intelligence and Machine Learning.pptx
Artificial Intelligence and Machine Learning.pptx
bobertbaratheon74
Ìý
Heuristic Searching: A* Search
Heuristic Searching: A* SearchHeuristic Searching: A* Search
Heuristic Searching: A* Search
IOSR Journals
Ìý
A* and Min-Max Searching Algorithms in AI , DSA.pdf
A* and Min-Max Searching Algorithms in AI , DSA.pdfA* and Min-Max Searching Algorithms in AI , DSA.pdf
A* and Min-Max Searching Algorithms in AI , DSA.pdf
CS With Logic
Ìý
Apriori algorithm
Apriori algorithmApriori algorithm
Apriori algorithm
nouraalkhatib
Ìý
Heuristic Search Techniques in Artificial Intelligence
Heuristic Search Techniques in Artificial IntelligenceHeuristic Search Techniques in Artificial Intelligence
Heuristic Search Techniques in Artificial Intelligence
Mehak533057
Ìý
Heuristic Searching Algorithms Artificial Intelligence.pptx
Heuristic Searching Algorithms Artificial Intelligence.pptxHeuristic Searching Algorithms Artificial Intelligence.pptx
Heuristic Searching Algorithms Artificial Intelligence.pptx
Swagat Praharaj
Ìý
Searchadditional2
Searchadditional2Searchadditional2
Searchadditional2
chandsek666
Ìý
Informed Search.pptx
Informed Search.pptxInformed Search.pptx
Informed Search.pptx
MohanKumarP34
Ìý
A* Algorithm
A* AlgorithmA* Algorithm
A* Algorithm
maharajdey
Ìý
Heuristic Search, Best First Search.pptx
Heuristic Search, Best First Search.pptxHeuristic Search, Best First Search.pptx
Heuristic Search, Best First Search.pptx
devhamnah
Ìý
Astar.ppt hjguyjgukyjgoyjgugukgulgoyulgyilglyi
Astar.ppt hjguyjgukyjgoyjgugukgulgoyulgyilglyiAstar.ppt hjguyjgukyjgoyjgugukgulgoyulgyilglyi
Astar.ppt hjguyjgukyjgoyjgugukgulgoyulgyilglyi
kamaleshs183
Ìý

More from MDTahsinAmin3 (6)

Computer Organization Introduction(basic)
Computer Organization Introduction(basic)Computer Organization Introduction(basic)
Computer Organization Introduction(basic)
MDTahsinAmin3
Ìý
3. Coprocessor.ppt
3. Coprocessor.ppt3. Coprocessor.ppt
3. Coprocessor.ppt
MDTahsinAmin3
Ìý
82C55 PPI (1).ppt
82C55 PPI (1).ppt82C55 PPI (1).ppt
82C55 PPI (1).ppt
MDTahsinAmin3
Ìý
7chap007_data modeling and analysis_14-7-19.ppt
7chap007_data modeling and analysis_14-7-19.ppt7chap007_data modeling and analysis_14-7-19.ppt
7chap007_data modeling and analysis_14-7-19.ppt
MDTahsinAmin3
Ìý
3.1measure of central tendency.pptx
3.1measure of central tendency.pptx3.1measure of central tendency.pptx
3.1measure of central tendency.pptx
MDTahsinAmin3
Ìý
Chapter-8_Multiplexing.pptx
Chapter-8_Multiplexing.pptxChapter-8_Multiplexing.pptx
Chapter-8_Multiplexing.pptx
MDTahsinAmin3
Ìý
Computer Organization Introduction(basic)
Computer Organization Introduction(basic)Computer Organization Introduction(basic)
Computer Organization Introduction(basic)
MDTahsinAmin3
Ìý
3. Coprocessor.ppt
3. Coprocessor.ppt3. Coprocessor.ppt
3. Coprocessor.ppt
MDTahsinAmin3
Ìý
82C55 PPI (1).ppt
82C55 PPI (1).ppt82C55 PPI (1).ppt
82C55 PPI (1).ppt
MDTahsinAmin3
Ìý
7chap007_data modeling and analysis_14-7-19.ppt
7chap007_data modeling and analysis_14-7-19.ppt7chap007_data modeling and analysis_14-7-19.ppt
7chap007_data modeling and analysis_14-7-19.ppt
MDTahsinAmin3
Ìý
3.1measure of central tendency.pptx
3.1measure of central tendency.pptx3.1measure of central tendency.pptx
3.1measure of central tendency.pptx
MDTahsinAmin3
Ìý
Chapter-8_Multiplexing.pptx
Chapter-8_Multiplexing.pptxChapter-8_Multiplexing.pptx
Chapter-8_Multiplexing.pptx
MDTahsinAmin3
Ìý

Recently uploaded (20)

Optimization of Cumulative Energy, Exergy Consumption and Environmental Life ...
Optimization of Cumulative Energy, Exergy Consumption and Environmental Life ...Optimization of Cumulative Energy, Exergy Consumption and Environmental Life ...
Optimization of Cumulative Energy, Exergy Consumption and Environmental Life ...
J. Agricultural Machinery
Ìý
decarbonization steel industry rev1.pptx
decarbonization steel industry rev1.pptxdecarbonization steel industry rev1.pptx
decarbonization steel industry rev1.pptx
gonzalezolabarriaped
Ìý
CS3451-OPERATING-SYSTEM NOTES ALL123.pdf
CS3451-OPERATING-SYSTEM NOTES ALL123.pdfCS3451-OPERATING-SYSTEM NOTES ALL123.pdf
CS3451-OPERATING-SYSTEM NOTES ALL123.pdf
PonniS7
Ìý
Air pollution is contamination of the indoor or outdoor environment by any ch...
Air pollution is contamination of the indoor or outdoor environment by any ch...Air pollution is contamination of the indoor or outdoor environment by any ch...
Air pollution is contamination of the indoor or outdoor environment by any ch...
dhanashree78
Ìý
Mathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptx
Mathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptxMathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptx
Mathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptx
ppkmurthy2006
Ìý
GREEN BULIDING PPT FOR THE REFRENACE.PPT
GREEN BULIDING PPT FOR THE REFRENACE.PPTGREEN BULIDING PPT FOR THE REFRENACE.PPT
GREEN BULIDING PPT FOR THE REFRENACE.PPT
kamalkeerthan61
Ìý
Multi objective genetic approach with Ranking
Multi objective genetic approach with RankingMulti objective genetic approach with Ranking
Multi objective genetic approach with Ranking
namisha18
Ìý
Wireless-Charger presentation for seminar .pdf
Wireless-Charger presentation for seminar .pdfWireless-Charger presentation for seminar .pdf
Wireless-Charger presentation for seminar .pdf
AbhinandanMishra30
Ìý
TM-ASP-101-RF_Air Press manual crimping machine.pdf
TM-ASP-101-RF_Air Press manual crimping machine.pdfTM-ASP-101-RF_Air Press manual crimping machine.pdf
TM-ASP-101-RF_Air Press manual crimping machine.pdf
ChungLe60
Ìý
CONTRACTOR ALL RISK INSURANCESAR (1).ppt
CONTRACTOR ALL RISK INSURANCESAR (1).pptCONTRACTOR ALL RISK INSURANCESAR (1).ppt
CONTRACTOR ALL RISK INSURANCESAR (1).ppt
suaktonny
Ìý
CFOT Fiber Optics FOA CERTIFICATION.pptx
CFOT Fiber Optics FOA CERTIFICATION.pptxCFOT Fiber Optics FOA CERTIFICATION.pptx
CFOT Fiber Optics FOA CERTIFICATION.pptx
MohamedShabana37
Ìý
US Patented ReGenX Generator, ReGen-X Quatum Motor EV Regenerative Accelerati...
US Patented ReGenX Generator, ReGen-X Quatum Motor EV Regenerative Accelerati...US Patented ReGenX Generator, ReGen-X Quatum Motor EV Regenerative Accelerati...
US Patented ReGenX Generator, ReGen-X Quatum Motor EV Regenerative Accelerati...
Thane Heins NOBEL PRIZE WINNING ENERGY RESEARCHER
Ìý
Best KNow Hydrogen Fuel Production in the World The cost in USD kwh for H2
Best KNow  Hydrogen Fuel Production in the World The cost in USD kwh for H2Best KNow  Hydrogen Fuel Production in the World The cost in USD kwh for H2
Best KNow Hydrogen Fuel Production in the World The cost in USD kwh for H2
Daniel Donatelli
Ìý
Piping-and-pipeline-calculations-manual.pdf
Piping-and-pipeline-calculations-manual.pdfPiping-and-pipeline-calculations-manual.pdf
Piping-and-pipeline-calculations-manual.pdf
OMI0721
Ìý
G8 mini project for alcohol detection and engine lock system with GPS tracki...
G8 mini project for  alcohol detection and engine lock system with GPS tracki...G8 mini project for  alcohol detection and engine lock system with GPS tracki...
G8 mini project for alcohol detection and engine lock system with GPS tracki...
sahillanjewar294
Ìý
decarbonization steel industry rev1.pptx
decarbonization steel industry rev1.pptxdecarbonization steel industry rev1.pptx
decarbonization steel industry rev1.pptx
gonzalezolabarriaped
Ìý
Name.docxVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
Name.docxVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVName.docxVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
Name.docxVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
MerijimArsedelPalmad1
Ìý
Engineering at Lovely Professional University (LPU).pdf
Engineering at Lovely Professional University (LPU).pdfEngineering at Lovely Professional University (LPU).pdf
Engineering at Lovely Professional University (LPU).pdf
Sona
Ìý
Taykon-Kalite belgeleri
Taykon-Kalite belgeleriTaykon-Kalite belgeleri
Taykon-Kalite belgeleri
TAYKON
Ìý
Indian Soil Classification System in Geotechnical Engineering
Indian Soil Classification System in Geotechnical EngineeringIndian Soil Classification System in Geotechnical Engineering
Indian Soil Classification System in Geotechnical Engineering
Rajani Vyawahare
Ìý
Optimization of Cumulative Energy, Exergy Consumption and Environmental Life ...
Optimization of Cumulative Energy, Exergy Consumption and Environmental Life ...Optimization of Cumulative Energy, Exergy Consumption and Environmental Life ...
Optimization of Cumulative Energy, Exergy Consumption and Environmental Life ...
J. Agricultural Machinery
Ìý
decarbonization steel industry rev1.pptx
decarbonization steel industry rev1.pptxdecarbonization steel industry rev1.pptx
decarbonization steel industry rev1.pptx
gonzalezolabarriaped
Ìý
CS3451-OPERATING-SYSTEM NOTES ALL123.pdf
CS3451-OPERATING-SYSTEM NOTES ALL123.pdfCS3451-OPERATING-SYSTEM NOTES ALL123.pdf
CS3451-OPERATING-SYSTEM NOTES ALL123.pdf
PonniS7
Ìý
Air pollution is contamination of the indoor or outdoor environment by any ch...
Air pollution is contamination of the indoor or outdoor environment by any ch...Air pollution is contamination of the indoor or outdoor environment by any ch...
Air pollution is contamination of the indoor or outdoor environment by any ch...
dhanashree78
Ìý
Mathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptx
Mathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptxMathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptx
Mathematics behind machine learning INT255 INT255__Unit 3__PPT-1.pptx
ppkmurthy2006
Ìý
GREEN BULIDING PPT FOR THE REFRENACE.PPT
GREEN BULIDING PPT FOR THE REFRENACE.PPTGREEN BULIDING PPT FOR THE REFRENACE.PPT
GREEN BULIDING PPT FOR THE REFRENACE.PPT
kamalkeerthan61
Ìý
Multi objective genetic approach with Ranking
Multi objective genetic approach with RankingMulti objective genetic approach with Ranking
Multi objective genetic approach with Ranking
namisha18
Ìý
Wireless-Charger presentation for seminar .pdf
Wireless-Charger presentation for seminar .pdfWireless-Charger presentation for seminar .pdf
Wireless-Charger presentation for seminar .pdf
AbhinandanMishra30
Ìý
TM-ASP-101-RF_Air Press manual crimping machine.pdf
TM-ASP-101-RF_Air Press manual crimping machine.pdfTM-ASP-101-RF_Air Press manual crimping machine.pdf
TM-ASP-101-RF_Air Press manual crimping machine.pdf
ChungLe60
Ìý
CONTRACTOR ALL RISK INSURANCESAR (1).ppt
CONTRACTOR ALL RISK INSURANCESAR (1).pptCONTRACTOR ALL RISK INSURANCESAR (1).ppt
CONTRACTOR ALL RISK INSURANCESAR (1).ppt
suaktonny
Ìý
CFOT Fiber Optics FOA CERTIFICATION.pptx
CFOT Fiber Optics FOA CERTIFICATION.pptxCFOT Fiber Optics FOA CERTIFICATION.pptx
CFOT Fiber Optics FOA CERTIFICATION.pptx
MohamedShabana37
Ìý
Best KNow Hydrogen Fuel Production in the World The cost in USD kwh for H2
Best KNow  Hydrogen Fuel Production in the World The cost in USD kwh for H2Best KNow  Hydrogen Fuel Production in the World The cost in USD kwh for H2
Best KNow Hydrogen Fuel Production in the World The cost in USD kwh for H2
Daniel Donatelli
Ìý
Piping-and-pipeline-calculations-manual.pdf
Piping-and-pipeline-calculations-manual.pdfPiping-and-pipeline-calculations-manual.pdf
Piping-and-pipeline-calculations-manual.pdf
OMI0721
Ìý
G8 mini project for alcohol detection and engine lock system with GPS tracki...
G8 mini project for  alcohol detection and engine lock system with GPS tracki...G8 mini project for  alcohol detection and engine lock system with GPS tracki...
G8 mini project for alcohol detection and engine lock system with GPS tracki...
sahillanjewar294
Ìý
decarbonization steel industry rev1.pptx
decarbonization steel industry rev1.pptxdecarbonization steel industry rev1.pptx
decarbonization steel industry rev1.pptx
gonzalezolabarriaped
Ìý
Name.docxVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
Name.docxVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVName.docxVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
Name.docxVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVVV
MerijimArsedelPalmad1
Ìý
Engineering at Lovely Professional University (LPU).pdf
Engineering at Lovely Professional University (LPU).pdfEngineering at Lovely Professional University (LPU).pdf
Engineering at Lovely Professional University (LPU).pdf
Sona
Ìý
Taykon-Kalite belgeleri
Taykon-Kalite belgeleriTaykon-Kalite belgeleri
Taykon-Kalite belgeleri
TAYKON
Ìý
Indian Soil Classification System in Geotechnical Engineering
Indian Soil Classification System in Geotechnical EngineeringIndian Soil Classification System in Geotechnical Engineering
Indian Soil Classification System in Geotechnical Engineering
Rajani Vyawahare
Ìý

A Star search algorithm with example (num)

  • 1. A* Search Algorithm ï‚´ A* Search Algorithm solved with numeric example
  • 2. A* Search Algorithm solved with numeric example
  • 3. A* Search Algorithm solved with numeric example
  • 4. A* Search Algorithm solved with numeric example
  • 5. A* Search Algorithm solved with numeric example
  • 6. A* Search Algorithm solved with numeric example
  • 7. A* Search Algorithm solved with numeric example
  • 8. A* Search Algorithm solved with numeric example
  • 9. A* Search Algorithm solved with numeric example
  • 10. Heuristic Function h(n) and how to make it
  • 11. Heuristic Function h(n) and how to make it
  • 12. Optimality of A* Search Algorithm ï‚´ Heuristic may be: ï‚´ h(n) > actual cost ï‚´ h(n) = actual cost ï‚´ h(n) < actual cost ï‚´ (1) h(n) > actual cost [Optimum solution can be overlooked, optimum solution is not possible] ï‚´ (2) h(n) = actual cost [Best case scenario, if h(n) approximates actual cost, searching uses minimum of node to the goal] ï‚´ (3) h(n) < actual cost [ Admissible, Consistent Heuristics]
  • 13. Optimality of A* Search Algorithm h(n) > actual cost [Optimum solution can be overlooked, optimum solution is not possible]
  • 14. Optimality of A* Search Algorithm h(n) > actual cost [Optimum solution can be overlooked, optimum solution is not possible]
  • 15. Optimality of A* Search Algorithm h(n) > actual cost [Optimum solution can be overlooked, optimum solution is not possible] b………….> dest and cost (7+2+0=9) , or ……….>a and cost (2+9=11)
  • 16. Optimality of A* Search Algorithm h(n) > actual cost [Optimum solution can be overlooked, optimum solution is not possible] b………….> dest and cost (7+2+0=9) , or ……….>a and cost (2+9=11) Actual cost from Sabdest =2+3+2=7 h(n)=10 > actual cost = 7
  • 17. Optimality of A* Search Algorithm ï‚´ h(n) < actual cost, if this relation maintains for every node, then we say this this Admissible Heuristics.
  • 18. Optimality of A* Search Algorithm
  • 19. Optimality of A* Search Algorithm
  • 20. Optimality of A* Search Algorithm
  • 21. Optimality of A* Search Algorithm
  • 22. Optimality of A* Search Algorithm If Heuristic admissible but not consistent, it may not be provided optimum solution. For optimum solution, heuristic must be consistent. If it consistent, it must be admissible.
  • 23. Optimality of A* Search Algorithm