Skip to content

Latest commit

 

History

History
56 lines (49 loc) · 3.95 KB

README.md

File metadata and controls

56 lines (49 loc) · 3.95 KB

Search Algorithm Trainer

The purpose of this program is to train for the execution of the provided Search Algorithms by hand in order to be well prepared for the Exam of IN2062 (Grundlagen der Künstlichen Intelligenz).

Seach Algorithms taken from this repository:

Algorithm Function name Notes
Breadth First Search breadth_first_graph_search [unused] also without explored set: breadth_first_tree_search
Depth First Search depth_first_tree_search [unused] also with explored set: depth_first_graph_search
Uniform Cost Search aka Dijkstra uniform_cost_search
Depth Limited Search depth_limited_search
Iterative Deepening Search iterative_deepening_search
Greedy Best First Search greedy_best_first_graph_search
$A^*$ Search astar_search

Additionally, some util functions for these algorithms and the romania example were taken from the same repository.

Useful overview of properties of these Search Algorithms:

  • Branching factor (max number of successors of any node) $b$
  • Maximum length of any path (in state space) $m$
  • Depth of shallowest goal node $d$
  • Cost of optimal solution $C^*$
  • Minimum Step cost $\epsilon$
  • Depth limit $l$ (For depth limited search)
  • Estimated and cost from the root to the goal $h$
  • Actual cost from the root to the goal $h^*$
  • Relative error $\epsilon^* = \frac{(h^* − h)}{h^*}$
Algorithm Informed/Uninformed Complete Optimal Time complexity Space Complexity
BFS Uninformed Yes (for finite $b$ and $d$) No (but Yes if equal cost per stel) $O(b^d)$ Nodes in frontier: $O(b^d)$; Explored nodes: $O(b^{d-1})$
DFS Uninformed No (but Yes when checking for cycles in finite state spaces) No $O(b^m)$ $O(bm)$
Uniform Cost Search (Dijkstra) - Best First Search mit $f(n) = g(n)$ Uninformed Yes (if all costs are $> 0$) Yes (If cost $\geq \epsilon$ for positive $\epsilon$) $O(b^{1+\lfloor{\frac{C^*}{\epsilon}}\rfloor})$ $O(b^{1+\lfloor{\frac{C^*}{\epsilon}}\rfloor})$ (since all nodes are stored)
Depth Limited Search Uninformed No (if $l < d$ ) No (if $l > d$) $O(b^l)$ $O(bl)$
Iterative Deepening Uninformed Yes (if $b$ is finite) Yes, if all step costs are the same $O(b^d)$ $O(bd)$
Greedy Best First Search Informed Yes (if graph search is used) No $O(bm)$ (Worst case: heuristic is misleading the search such that the solution is found last) $O(bm)$ (Worst case: heuristic is misleading the search such that the solution is found last) (since all nodes are stored)
$A^*$-Search Informed Yes (if all costs are $> 0$) Yes (if costs are positive and heuristic is admissible) $O(b^{\epsilon^* d})$ (If the state space has a single goal and all actions are reversible) $O(b^{\epsilon^* d})$ (If the state space has a single goal and all actions are reversible) (since all nodes are stored)

Note: DFS and BFS conduct a goal check on nodes that are added to the frontier, while the other algorithms do so when nodes are taken out of the frontier

Explanations:

  • Optimal: Does the strategy find the optimal solution (minimum costs)?
  • Complete: Is it guaranteed that the algorithm finds a solution if one exists?

Properties of heuristics $h(n)$:

  • Consistency: $h(n)$ is consistent, iff $h(n) \leq c(n, a, n') + h(n')$ for all nodes $n$, action $a$ and all direct successors $n'$ gilt.
  • Admissible: An admissible heuristic is an underestimation, i.e., it has to be less than or equal to the actual cost.
  • $h_2$ dominates $h_1$ iff $\forall n: h_2(n) \geq h_1(n)$
  • Every consistent heuristic is also admissible
  • In $A^*$:
    • If the heuristic is consistent, any node is only expanded if it is located on an optimal path to its state.
    • A dominating heuristic will never expand more nodes than the heuristic it dominates

Required libraries

  • matplotlib
  • networkX