(The below text version of the notes is for search purposes and convenience. See the PDF version for proper formatting such as bold, italics, etc., and graphics where applicable. Copyright: 2022 Retraice, Inc.)

Re84: A Node Instantiated (Best-First-Search Part 3, AIMA4e pp. 73-74)

retraice.com

Writing, as a class in Python, a data structure to represent a reached state in the environment's state space. State space and search tree; nodes and edges; nodes as representing unique paths; parent nodes, applied actions and total path-from-initial-state cost; init, repr, len and lt magic methods in Python.

Air date: Friday, 16th Dec. 2022, 10:00 PM Eastern/US.

The structure of a node

In search problems we first have a state space: a set of states and the actions that cause transitions from one to another state. One method of solving search problems is based on building a search tree in the state space to represent paths between the initial state and a goal state. The search tree is composed of nodes that represent unique paths from the initial to a given state, and edges that represent actions.^1

Nodes implemented in code need these attributes:^2 * State: node.State, the state to which the node corresponds; * Parent: node.Parent, the node that generated this node; * Action applied: node.Action, the action that was applied to the parent node; * Path-to cost: node.Path-Cost, the total cost of the path from initial to this node. In math it's g(node).

Nodes as class in Python ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

PIC Python code implementing an object class data structure to represent nodes of a search tree of a state space. Code at https://github.com/retraice/ReAIMA4e. ________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________________

___

References

Russell, S., & Norvig, P. (2020). Artificial Intelligence: A Modern Approach. Pearson, 4th ed. ISBN: 978-0134610993. Searches: https://www.amazon.com/s?k=978-0134610993 https://www.google.com/search?q=isbn+978-0134610993 https://lccn.loc.gov/2019047498

Footnotes

^1 Russell & Norvig (2020) p. 71.

^2 Russell & Norvig (2020) p. 73.