8.1.12
A* Algorithm
A* algorithm
A* algorithm
An improved version of Dijkstra’s algorithm. A finds the shortest path from a starting point to a goal on a graph. A combines actual travel costs and estimated costs to prioritize promising paths.
Step-by-Step Overview
Step-by-Step Overview
- Steps include:
- 1 Initialization
- 2 Cost Calculation
- 3 Explore
- 4 Expand Neighbors
- 5 Close Node
- 6 Repeat
- 7 Reconstruct Path
Initialization
Initialization
- Step 1 Initialization
- Start with an open list (to explore) and a closed list (evaluated).
- Add the starting point to the open list with an initial cost of 0.
Cost calculation
Cost calculation
- Step 2: Cost Calculation
- For each node, calculate:
- g(n): Cost from the start to the node.
- h(n): Estimated cost from the node to the goal.
- Total cost: f(n) = g(n) + h(n).
Explore
Explore
- Step 3: Explore
- While the open list isn’t empty:
- Select the node with the lowest f(n) (current node).
- If it’s the goal, reconstruct the path and finish.
Expand neighbors
Expand neighbors
- Step 4: Expand Neighbors
- For each neighbor of the current node:
- Calculate new g(n). If it’s lower than before, update costs and set the current node as the neighbor’s parent.
- Add the neighbor to the open list if not already present.
Close node, repeat, reconstruct path
Close node, repeat, reconstruct path
- Step 5: Close Node
- Move the current node to the closed list.
- Step 6: Repeat
- Go back to step 3 until the goal is found or no paths remain.
- Step 7: Reconstruct Path
- If the goal is reached, trace back from the goal to the start using parent pointers to get the path.
1Components of a Computer
1.1Structure & Function of the Processor
1.2Types of Processors
1.3Input, Output & Storage
1.3.1Elements of Computer Systems
1.3.2Types of Computer Systems
1.3.3How Magnetic Storage Works
1.3.4Properties of Magnetic Storage
1.3.5Examples of Magnetic Storage
1.3.6How Optical Storage Works
1.3.7Properties of Optical Storage
1.3.8Examples of Optical Storage
1.3.9Types of Optical Disc
1.3.10Random Access Memory
1.3.11Read Only Memory
1.3.12Uses of Flash Memory
1.3.13Properties of Flash Memory
1.3.14What to do When We Run Out of Memory
1.3.15How Virtual Memory Works
2Software & Software Development
2.1Systems Software
2.2Applications Generation
2.2.1Applications Software
2.2.2Utilities
2.2.3Encryption Software
2.2.4Defragmentation Software
2.2.5Data Compression Software
2.2.6Backup Software
2.2.7Open Source Software
2.2.8Proprietary Software
2.2.9Licensing Issues
2.2.10Compilers
2.2.11Interpreters
2.2.12Assemblers
2.2.13Compiling a Program
2.2.14Lexical Analysis
2.2.15Compilation Stages
2.2.16Linkers, Loaders & Libraries
2.3Software Development
2.3.1Algorithmic Thinking
2.3.2Waterfall Lifecycle
2.3.3Waterfall Lifecycle - Strengths & Weaknesses
2.3.4Agile Methodology
2.3.5Agile Methodology - Strengths & Weaknesses
2.3.6Extreme Programming
2.3.7Extreme Programming - Strengths & Weaknesses
2.3.8Spiral Methodology
2.3.9Spiral Methodology - Strengths & Weaknesses
2.3.10Rapid Application Development
2.3.11RAD - Strengths & Weaknesse
2.4Types of Programming Language
3Exchanging Data
3.1Compression, Encryption & Hashing
3.2Databases
3.3Networks
3.3.1The Benefits of Networks
3.3.2Network Performance
3.3.3Types of Networks
3.3.4Network Protocols
3.3.5Transmission Protocols
3.3.6What is the Internet?
3.3.7Uniform Resource Locators
3.3.8Domain Name Service
3.3.9Web Hosting
3.3.10Layering Concepts
3.3.11TCP &. OSI Models
3.3.12The Advantages of Layering
3.3.13What's in a Packet?
3.3.14How do Packets get Routed?
3.3.15Did my Data Arrive Safely?
3.3.16Network Hardware
3.3.17Transmission Media
3.3.18Firewalls
3.3.19Proxies
3.3.20Client-Server Model
3.3.21Advantages of the Client Server Model
3.3.22Disadvantages of the Client Server Model
3.3.23Peer-to-Peer Model
3.3.24Advantages of the Peer-to-Peer Model
3.3.25Disadvantages of the Peer-to-Peer Model
4Data Types, Data Structures & Algorithms
4.1Data Types
4.1.1Data Types
4.1.2Casting
4.1.3Arrays
4.1.42D Arrays
4.1.5Strings
4.1.6Binary
4.1.7Sign & Magnitude
4.1.8Binary Addition
4.1.9Binary Shifts
4.1.10Hexadecimal
4.1.11Using Hexadecimal
4.1.12Converting Binary & Hexadecimal
4.1.13Converting Denary & Hexadecimal
4.1.14Floating Points in Binary
4.1.15Normalisation of Floating Points
4.1.16Floating Point Addition
4.1.17Floating Point Subtraction
4.1.18Bitwise Manipulation - Shifts
4.1.19Bitwise Manipulation - Masks
4.1.20Character Sets
4.1.21ASCII
4.1.22Unicode
4.2Data Structures
5Legal, Moral, Cultural & Ethical Issues
5.1Computing Related Legislation
5.2Moral & Ethical Issues
5.2.1Online Activity Tracking
5.2.2Censorship
5.2.3Positive Cultural Impacts
5.2.4Negative Cultural Impacts
5.2.5E-Waste
5.2.6Energy Consumption
5.2.7Positive Environmental Impact
5.2.8Layout, Colour Paradigms & Character Sets
5.2.9Computers in the Workplace
5.2.10Automated Decision-Making
5.2.11Artificial Intelligence
5.2.12Monitoring Behaviour
5.2.13Analysing Personal Information
5.2.14Piracy & Offensive Communication
6Elements of Computational Thinking
6.1Thinking Abstractly
6.2Thinking Ahead
6.3Thinking Procedurally
6.4Thinking Logically
6.5Thinking Concurrently
7Problem Solving & Programming
7.1Programming Techniques
7.2Programming Construction
Jump to other topics
1Components of a Computer
1.1Structure & Function of the Processor
1.2Types of Processors
1.3Input, Output & Storage
1.3.1Elements of Computer Systems
1.3.2Types of Computer Systems
1.3.3How Magnetic Storage Works
1.3.4Properties of Magnetic Storage
1.3.5Examples of Magnetic Storage
1.3.6How Optical Storage Works
1.3.7Properties of Optical Storage
1.3.8Examples of Optical Storage
1.3.9Types of Optical Disc
1.3.10Random Access Memory
1.3.11Read Only Memory
1.3.12Uses of Flash Memory
1.3.13Properties of Flash Memory
1.3.14What to do When We Run Out of Memory
1.3.15How Virtual Memory Works
2Software & Software Development
2.1Systems Software
2.2Applications Generation
2.2.1Applications Software
2.2.2Utilities
2.2.3Encryption Software
2.2.4Defragmentation Software
2.2.5Data Compression Software
2.2.6Backup Software
2.2.7Open Source Software
2.2.8Proprietary Software
2.2.9Licensing Issues
2.2.10Compilers
2.2.11Interpreters
2.2.12Assemblers
2.2.13Compiling a Program
2.2.14Lexical Analysis
2.2.15Compilation Stages
2.2.16Linkers, Loaders & Libraries
2.3Software Development
2.3.1Algorithmic Thinking
2.3.2Waterfall Lifecycle
2.3.3Waterfall Lifecycle - Strengths & Weaknesses
2.3.4Agile Methodology
2.3.5Agile Methodology - Strengths & Weaknesses
2.3.6Extreme Programming
2.3.7Extreme Programming - Strengths & Weaknesses
2.3.8Spiral Methodology
2.3.9Spiral Methodology - Strengths & Weaknesses
2.3.10Rapid Application Development
2.3.11RAD - Strengths & Weaknesse
2.4Types of Programming Language
3Exchanging Data
3.1Compression, Encryption & Hashing
3.2Databases
3.3Networks
3.3.1The Benefits of Networks
3.3.2Network Performance
3.3.3Types of Networks
3.3.4Network Protocols
3.3.5Transmission Protocols
3.3.6What is the Internet?
3.3.7Uniform Resource Locators
3.3.8Domain Name Service
3.3.9Web Hosting
3.3.10Layering Concepts
3.3.11TCP &. OSI Models
3.3.12The Advantages of Layering
3.3.13What's in a Packet?
3.3.14How do Packets get Routed?
3.3.15Did my Data Arrive Safely?
3.3.16Network Hardware
3.3.17Transmission Media
3.3.18Firewalls
3.3.19Proxies
3.3.20Client-Server Model
3.3.21Advantages of the Client Server Model
3.3.22Disadvantages of the Client Server Model
3.3.23Peer-to-Peer Model
3.3.24Advantages of the Peer-to-Peer Model
3.3.25Disadvantages of the Peer-to-Peer Model
4Data Types, Data Structures & Algorithms
4.1Data Types
4.1.1Data Types
4.1.2Casting
4.1.3Arrays
4.1.42D Arrays
4.1.5Strings
4.1.6Binary
4.1.7Sign & Magnitude
4.1.8Binary Addition
4.1.9Binary Shifts
4.1.10Hexadecimal
4.1.11Using Hexadecimal
4.1.12Converting Binary & Hexadecimal
4.1.13Converting Denary & Hexadecimal
4.1.14Floating Points in Binary
4.1.15Normalisation of Floating Points
4.1.16Floating Point Addition
4.1.17Floating Point Subtraction
4.1.18Bitwise Manipulation - Shifts
4.1.19Bitwise Manipulation - Masks
4.1.20Character Sets
4.1.21ASCII
4.1.22Unicode
4.2Data Structures
5Legal, Moral, Cultural & Ethical Issues
5.1Computing Related Legislation
5.2Moral & Ethical Issues
5.2.1Online Activity Tracking
5.2.2Censorship
5.2.3Positive Cultural Impacts
5.2.4Negative Cultural Impacts
5.2.5E-Waste
5.2.6Energy Consumption
5.2.7Positive Environmental Impact
5.2.8Layout, Colour Paradigms & Character Sets
5.2.9Computers in the Workplace
5.2.10Automated Decision-Making
5.2.11Artificial Intelligence
5.2.12Monitoring Behaviour
5.2.13Analysing Personal Information
5.2.14Piracy & Offensive Communication
6Elements of Computational Thinking
6.1Thinking Abstractly
6.2Thinking Ahead
6.3Thinking Procedurally
6.4Thinking Logically
6.5Thinking Concurrently
7Problem Solving & Programming
7.1Programming Techniques
7.2Programming Construction
Unlock your full potential with Seneca Premium
Unlimited access to 10,000+ open-ended exam questions
Mini-mock exams based on your study history
Unlock 800+ premium courses & e-books