Archive for the ‘algorithm’ Category

algorithm: A* search and IDA* search

August 8, 2017

The post discusses some search methods.

problem

  • Given: a graph, a source node, and a destination node
  • Objective: find a minimum cost path from source to destination.
  • greedy search

    • bfs style
    • cost function = h(x): estimated cost of path to destination

    A search

    • bfs style
    • cost function = f(x) = h(x) + g(x). g(x): cost of path from source

    A* search

    • bfs style
    • cost function = f(x) = h(x) + g(x)
    • h(x) is admissive, i.e., h(x) <= h*(x). It never overestimates the cost to the destination.
    • the solution is optimal

    IDDFS: iterative deepening dfs

    • dfs style
    • cost function = g(x): length of the path from source
    • the search has many iterations of dfs
    • in each iteration, the dfs stops while path length is above threshold
    • the stop threshold is increased by one in each iteration

    IDA*: iterative deepening dfs

    • dfs style
    • cost function = f(x) = h(x) + g(x)
    • h(x) is admissive, i.e., h(x) <= h*(x). It never overestimates the cost to the destination.
    • the stop threshold is increased by one in each iteration
    • the search has many iterations of dfs
    • in each iteration, the dfs stops while path length is above threshold
    • the stop threshold’s default value is h(source)
    • if destination is not found in last iteration, the stop threshold is updated as the minimum f(x) above threshold in last iteration
    • the solution is optimal

    conclusion
    IDA* search improves the space usage of A* search. This could improve performance since all operations are executed in stack directly which is already created by kernel(main thread) or pthread library(other threads). However, since stack size is fixed, if the problem size is large, than A* search might be the better option.

    Advertisements

    algorithm: SAT problem

    December 11, 2016

    This post discusses what is SAT, Boolean satisfiability problem, and its complexity.

    what is SAT problem

    • Input: A boolean formula
    • Output: Return true if there exists an assignment of variables such that the boolean formula is true. Otherwise, return false.
    • This problem is NP-Complete

    what is CNF form

    • A boolean formula in CNF form is a boolean formula of conjunctions of clauses.
    • A clause is disjunction of literals.
    • A literal is positive or negative of a boolean variable

    what is CNF SAT problem

    • Input: A boolean formula in CNF form
    • Output: Return true if there exists an assignment of variables such that the boolean formula is true.
      Otherwise, return false.
    • This problem is NP-Complete

    what is 3-SAT problem

    • Input: A boolean formula in CNF form. Each clause has at most 3 literals.
    • Output: Return true if there exists an assignment of variables such that the boolean formula is true.
      Otherwise, return false.
    • This problem is NP-Complete

    2-SAT problem

    • Input: A boolean formula in CNF form. Each clause has at most 2 literals.
    • Output: Return true if there exists an assignment of variables such that the boolean formula is true.
      Otherwise, return false.
    • There exist polynomial time algorithms to solve this problem

    conclusion
    This post discusses SAT problem.

    algorithm: membership problem of a language

    December 10, 2016

    This post discusses membership problem of a language.

    what is membership problem of a language

    • Input: A string and a language
    • Output: True if the string belongs to the language. False if the string doesn’t belong to the language.

    membership of recursively enumerable language

    • The problem is semi-decidable. It is only decidable when the answer is true.
    • Let a program enumerate all strings in the language one by one. If the enumerated string so far matches the input string, then return true. This program will run forever and not return if the input string is not in the language.

    membership of recursive language

    • The problem is decidable.

    membership of context-sensitive language

    • A language is context-sensitive if the left hand side of production rules could have terminal or non-terminal symbols.
    • The problem is decidable.
    • The problem is in pspace-complete. There exists no polynomial time algorithm for this problem.

    membership of context-free language

    • A language is context-free if the left hand of production rules could only be non-terminal symbols. It implies that all production rules are context-free since it is deterministic for a non-terminal symbols no mater what is preceding or succeeding of it.
    • The problem is decidable.
    • There exist polynomial time algorithms to solve this problem. The time complexity is O(n^3).
    • Reference: CYK algorithm and Earley parser

    membership of regular language

    • A language is regular if the all its production rules is left-linear or right linear.
    • The problem is decidable.
    • There exist polynomial time algorithms to solve this problem. The time complexity is O(n).
    • Reference: Thompson’s construction

    conclusion
    This post discusses membership problem of a language, in terms of decidable and time complexity.


    %d bloggers like this: