Algorithms/Search Types - Revision history

Brodriguez: Correct more typos

2021-10-13T01:07:51Z

Correct more typos

← Older revision		Revision as of 01:07, 13 October 2021
Line 38:		Line 38:
	* Is complete when b is finite.		* Is complete when b is finite.
	* Is optimal if cost is uniform for every possible action. Otherwise, generally not optimal.		* Is optimal if cost is uniform for every possible action. Otherwise, generally not optimal.
	* Time is O(<math>b^d</math>		* Time is O(<math>b^d</math>).
	* Space is O(<math>b^d</math>		* Space is O(<math>b^d</math>).

Brodriguez: Correct typo

2021-10-13T01:07:17Z

Correct typo

← Older revision		Revision as of 01:07, 13 October 2021
Line 36:		Line 36:

	Evaluation:		Evaluation:
	* Is complete when b is ~~infinite~~.		* Is complete when b is finite.
	* Is optimal if cost is uniform for every possible action. Otherwise, generally not optimal.		* Is optimal if cost is uniform for every possible action. Otherwise, generally not optimal.
	* Time is O(<math>b^d</math>		* Time is O(<math>b^d</math>

Brodriguez: Update formatting

2021-10-12T21:26:33Z

Update formatting

Brodriguez: Update page

2021-10-05T23:50:49Z

Update page

← Older revision		Revision as of 23:50, 5 October 2021
Line 94:		Line 94:
	* Time is O(<math>b^d</math>) (same as BFS).		* Time is O(<math>b^d</math>) (same as BFS).
	* Space is O(b * d) (same as DFS).		* Space is O(b * d) (same as DFS).


			== Informed Search Algorithms ==
			Algorithms which make use of some form of "outside" or "domain-specific" knowledge, in addition to base problem description.

Brodriguez: Create page

2021-10-05T23:44:22Z

Create page

New page

The following describes various types of searches using tree data structures.

== Terminology ==
* State - A possible configuration in attempting to solve the problem.
* Initial State - The problem starting state. Represented by the tree root.
* Successor State - Any state reachable by a single action, from the current state.
* Tree Node - A data structure that contains information for a single state, as well as any additional relevant data.
* Expanded Node - A node that has been checked.
* Unexpanded Node - A node that has not been checked.
* Frontier - The set of all "unexpanded nodes" in the tree which can be accessed by a single action from a given expanded node.

== Search Evaluation ==
The following can be used to evaluate a given search algorithm:
* Completeness - Ability to always find a complete solution, if one exists.
* Optimality - Ability to always find the lowest-cost/most-efficient solution, when it does find a solution.
* Time Complexity - Number of nodes generated or expanded. For our purposes, we assume each node takes 1 unit of time to evaluate.
* Space Complexity - The maximum nodes in memory at any given point.

Time/space complexity are often evaluated in terms of:
* Branching Factor (b) - Max number of successors of any node in the tree.
* Depth (d) - The shallowest goal node in the tree.
* Maximum Depth (m) - The deepest branch in the tree. May be ∞.

== Uninformed Search Algorithms ==
Algorithms which only directly use information supplied in the problem definition.

=== Breadth First Search (BFS) ===
* Always expands the shallowest unexpanded node first.
* The frontier acts as a "First-In, First-Out" (FIFO) queue.

Evaluation:
* Is complete when b is infinite.
* Is optimal if cost is uniform for every possible action. Otherwise, generally not optimal.
* Time is O(<math>b^d</math>
* Space is O(<math>b^d</math>

=== Uniform Cost Search (UCS) ===
* Similar to BFS, except instead of expanding the shallowest node, it always expands the node with the lowest path-cost factor.
* Stores frontier as a priority queue.
* To avoid infinite loops, all costs should be a positive, non-zero integer.

Evaluation:
* Is complete if the minimum step cost for all nodes is greater than 0.
* Is always optimal.
* If all step costs are equal, then has identical space/time complexity to BFS.
** Otherwise, has slightly worse space/time complexity than BFS.

=== Depth First Search (DFS) ===
* Expands deepest unexpanded node first.
* Stores frontier as a "Last-In, First-Out" (LIFO) stack.

Evaluation:
* Is complete when depth space is finite.
* Often is not optimal.
* Time is O(<math>b^m</math>).
* Space is O(b * m).

=== Depth-Limited Search (DLS) ===
* Similar to DFS, but puts an artificial limit on how deep it searches.
** This allows bypassing issues with infinite-depth trees, such as when there are loops or repeating states.
* Requires setting a predetermined limit (<math>\ell</math>).
* Technically, DFS can be considered a DLS problem, but with <math>\ell</math>=∞.

Evaluation:
* Complete only if goal is within <math>\ell</math> depth.
* Similar to DFS, is often not optimal.
* Time is O(<math>b^\ell</math>).
* Space is O(b * <math>\ell</math>).

=== Iterative Deepening Search (IDS) ===
* Combines the benefits of BFS and DFS.
* Finds the "best depth limit" by gradually increasing depth.
** Ex: <math>\ell</math>=1, then <math>\ell</math>=2, etc.
* Generally, this is the preferred uninformed search space method, if search space is large and depth of solution is unknown.

Evaluation:
* Complete when branching factor (b) is finite.
* Optimal when all step costs are positive, non-zero integers.
* Time is O(<math>b^d</math>) (same as BFS).
* Space is O(b * d) (same as DFS).

← Older revision		Revision as of 21:26, 12 October 2021
Line 3:		Line 3:

	== Terminology ==		== Terminology ==
	* State - A possible configuration in attempting to solve the problem.		* '''State''' - A possible configuration in attempting to solve the problem.
	* Initial State - The problem starting state. Represented by the tree root.		* '''Initial State''' - The problem starting state. Represented by the tree root.
	* Successor State - Any state reachable by a single action, from the current state.		* '''Successor State''' - Any state reachable by a single action, from the current state.
	* Tree Node - A data structure that contains information for a single state, as well as any additional relevant data.		* '''Tree Node''' - A data structure that contains information for a single state, as well as any additional relevant data.
	* Expanded Node - A node that has been checked.		* '''Expanded Node''' - A node that has been checked.
	* Unexpanded Node - A node that has not been checked.		* '''Unexpanded Node''' - A node that has not been checked.
	* Frontier - The set of all "unexpanded nodes" in the tree which can be accessed by a single action from a given expanded node.		* '''Frontier''' - The set of all "unexpanded nodes" in the tree which can be accessed by a single action from a given expanded node.


	== Search Evaluation ==		== Search Evaluation ==
	The following can be used to evaluate a given search algorithm:		The following can be used to evaluate a given search algorithm:
	* Completeness - Ability to always find a complete solution, if one exists.		* '''Completeness''' - Ability to always find a complete solution, if one exists.
	* Optimality - Ability to always find the lowest-cost/most-efficient solution, when it does find a solution.		* '''Optimality''' - Ability to always find the lowest-cost/most-efficient solution, when it does find a solution.
	* Time Complexity - Number of nodes generated or expanded. For our purposes, we assume each node takes 1 unit of time to evaluate.		* '''Time Complexity''' - Number of nodes generated or expanded. For our purposes, we assume each node takes 1 unit of time to evaluate.
	* Space Complexity - The maximum nodes in memory at any given point.		* '''Space Complexity''' - The maximum nodes in memory at any given point.


	Time/space complexity are often evaluated in terms of:		Time/space complexity are often evaluated in terms of:
	* Branching Factor (b) - Max number of successors of any node in the tree.		* '''Branching Factor''' ('''b''') - Max number of successors of any node in the tree.
	* Depth (d) - The shallowest goal node in the tree.		* '''Depth''' ('''d''') - The shallowest goal node in the tree.
	* Maximum Depth (m) - The deepest branch in the tree. May be ∞.		* '''Maximum Depth''' ('''m''') - The deepest branch in the tree. May be ∞.