csc421_tzanetakis_beyond_classical_search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# CSC 421 - Beyond classical search \n",
    "\n",
    "### Instructor: George Tzanetakis \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Summary \n",
    "\n",
    "This a chapter not typically covered in CSC421 so only a summary of what is covered is provided. The techniques described in this chapter are frequently useful when there is not a single desired optimal solution but many solutions that are all **good enough**. \n",
    "\n",
    "* Local search methods such as **hill climbing** operate on complete-state formulations, keeping only a small number of nodes in memory. Several stochastic algorithms have been developed, including **simualted annealing** which returns optimal solutions when given an a appropriate cooling schedule.\n",
    "* Many local search methods also apply to problems in continuous spaces. **Linear programming** and **convex optimization** problems obey certain restrictions on the space of the state space and the nature of the objective function, and admit polynomial-time algorithms that are often extremely efficient in practice.\n",
    "* A **genetic algorithm** is a stochastic hill-climbing search in which a large population of states is maintained. New states are generated by **mutation** and by **cross-over**, which combines pairs of states from the population.\n",
    "* In **non-deterministic** environments agents can apply *AND-OR* search to generate **contigent** plans that reach the goal regardless of which outcomes occur during execution.\n",
    "* Standard search algorithms can be applied directly to belief-state space to solve **sensor-less problems**, and belief-state *AND-OR* search can solve general partially observable problems. Incremental algorithms that construct solutions state-by-state within a belief state are often more efficient.\n",
    "* **Exploration problems** arise when the agent has no idea about the states and actions of its environment. For safely explorable environments, **online search** agents can build a map and find a goal if one exists. Updating heuristic estimates from experience provides an effective method to escape from local minima.\n",
    "* \n",
    "\n",
    "**Note on inspiration:** \n",
    "\n",
    "* metallurgy (simulated annealing)\n",
    "* biology (genetic algorithms)\n",
    "* economics (market-based algorithms)\n",
    "* entomology (ant colony optimization)\n",
    "* neurology (neural networks)\n",
    "* animal behavior (reinforcement learning)\n",
    "* mountaineering (hill climbing)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}