Use incremental belief-state search to find only the initial possibilities needed to constrain a successful plan. Choose one possible initial state, or a small subset of the full initial belief state . Find an action sequence solving this restricted problem, then simulate it from every state in .
If validation succeeds, return the candidate. Otherwise choose a state that makes some action inapplicable or ends outside the goal, add it to , and search again for a plan that works for every selected state. Replanning can revise the earlier sequence; merely appending a repair to one arbitrary candidate can miss solutions. For a finite initial belief state, there are at most additions before every initial possibility has been included. If a complete restricted solver proves that even the selected subset is unsolvable, part (g) shows that the full problem is unsolvable.
The benefits are smaller intermediate belief states, fewer states propagated through candidate actions, and avoidance of unnecessary portions of the full power set search space. One physical-state counterexample can eliminate many invalid candidates. The worst case can still require all initial states; the method exploits instances where a few representative possibilities already force a plan that passes universal validation.
For an action sequence , let be the set of all physical states obtainable by applying it to the initial belief state . Under a deterministic model this is an image; for nondeterministic outcomes it is the union of all permitted images. For ,
If each action is applicable to every current possibility from , it is also applicable to every possibility from . If the final belief state for is contained in the physical goal set , then . Thus the same plan solves every subset of .
Nothing comparable follows for an arbitrary superset. For example, let an action take to a goal and leave at a non-goal. It solves but not . A larger belief state is solved by this particular sequence exactly when all added states also permit it and end in . It may succeed on some supersets and fail on others; it cannot be guaranteed merely from success on .
For the three-colourability problem, represent a candidate by a complete colour assignment , initially chosen at random. Give it the conflict objective function
A neighbor changes the colour of one vertex to either other colour. For hill climbing, maximize , or equivalently repeatedly choose a recolouring that reduces . One can inspect all neighbors, or focus on conflicted vertices and evaluate their alternative colours using only incident edges. Stop successfully as soon as , which is exactly a proper graph colouring with three colours.
If no improving move exists at positive , the method is stuck in a local minimum. Random restarts, limited sideways moves or other exploratory local search choices can reduce this failure mode, but do not turn a finite unsuccessful run into a proof of impossibility. On a graph with no proper graph colouring using three colours, every complete colouring has , so this procedure cannot return a valid colouring. Conversely, a positive-conflict stopping point also occurs on some graphs admitting a proper graph colouring with three colours. Failure of hill climbing alone does not certify non-colourability. For a concrete trap, use a bipartite graph with three vertices on each side and every cross-edge, and give each side one vertex of each colour. There are three conflicts. Recolouring any single vertex leaves it with exactly one same-colour neighbor, so no single change improves , even though colouring each whole side differently solves the instance.
A lower bound on individual step costs does not bound the difference between consecutive path cost thresholds. Two different paths can have costs differing by an arbitrarily small amount, even though every edge costs at least .
Let be the optimal solution cost. Every unsuccessful threshold is the path cost of some search node below . Such a node has depth strictly less than . For a uniform branching factor , the number of passes is therefore bounded by
If a solution of depth exists, each of its edges costs at most one, so and an associated bound is passes. If denotes the optimal solution's depth, the same inequality applies. With no solution-cost or solution-depth bound, and alone give no finite uniform iteration bound.
The exponential behavior is possible. Put a depth- goal on a branch with unit costs and let a large competing subtree use costs just above . Choose tiny distinct perturbations so that its many search nodes below cost have distinct path costs. The threshold can advance through those costs one at a time. Thus a bound such as on the number of passes is unjustified: it bounds admitted depth, not the number of distinct costs. For there is only one path, so the corresponding count is linear in the admitted depth rather than exponential.
With initial threshold zero and unit step costs, the thresholds are , so there are passes. Starting the first pass at one instead omits the zero-threshold pass when the root is not a goal.
At depth , at most search nodes are admitted in each pass with threshold at least . Across all passes, the full-to-cutoff visit bound is
This is attained when the only depth- goal is visited last. If a goal test occurs before expansion, the goal is visited but not expanded, giving the corresponding worst-case expansion count
For , the visit bound is , hence the worst-case number expanded is for fixed . For , it is . An earlier goal reduces the final pass, so its exact count cannot be inferred from alone. Children generated and immediately rejected above a threshold are not counted as expanded; counting those generated nodes adds the corresponding branching overhead.
Start the threshold at zero and let be the least solution cost. Suppose an unsuccessful pass has threshold . Along an optimal action sequence, take the first prefix whose path cost exceeds . Its preceding prefix is explored, so that rejected prefix contributes to the next-threshold calculation. Positive step costs imply that its cost is at most . Therefore the next threshold is also at most .
By induction, no threshold used before the first solution exceeds . A returned goal state therefore has cost at most ; by the definition of it cannot cost less. The first returned solution is optimal.
The termination qualification matters. In a finitely branching problem with step costs at least , a threshold admits only depths up to , so each pass is finite and only finitely many path costs precede . These conditions establish completeness as well. Strict positivity alone on an arbitrary infinite tree is insufficient: an infinite branch with costs can remain below a finite threshold and trap depth-first search. The optimality argument above is valid whenever the required passes terminate; a finite graph with finitely many strictly positive action costs supplies a uniform positive lower bound.
Iterative deepening depth-first search increases a bound on the number of actions, usually through . Iterative lengthening search instead bounds accumulated path cost; after an unsuccessful pass, its next bound is the least path cost among the rejected search nodes. Thus it can distinguish shallow expensive paths from deeper cheap ones.
Both repeatedly perform depth-first search and retain its small active-path storage, trading repeated work for avoiding a large search frontier. With unit step costs their bounds coincide. With unequal positive step costs, iterative deepening depth-first search finds a solution with the fewest actions, while iterative lengthening search, under the termination conditions discussed next, finds one of least total cost. Real-valued path costs can make iterative lengthening search perform many more passes than the depth-bounded method.
The first assertion is false. Give the root a first child that is a goal state of cost ten and another child leading to many cheaper non-goal search nodes. Depth-first search can take the first child and stop immediately. A-star search with the admissible heuristic behaves as uniform-cost search and expands the cheaper non-goal search nodes before selecting that goal. Thus an admissible heuristic does not make A-star search expand fewer nodes than every possible depth-first search ordering. The latter need not return an optimal solution.
The second assertion is true under the usual finite-branching factor assumption. Breadth-first search orders by search depth, not path cost. Every finite depth contains finitely many search nodes, so a goal at finite depth is eventually reached even if some steps cost zero. Zero-cost steps can affect cost optimality, but do not obstruct this completeness argument. An infinite branching factor would invalidate the argument irrespective of step costs.
The third assertion is true as a worst-case black-box requirement, with a finite optimum assumed. If outgoing actions are known only by expanding a state, an unexamined reachable branch can conceal a sufficiently negative-cost action followed by a route to a goal. Its total cost can beat the current solution by an arbitrarily large amount. Without additional lower bounds or structural information, finding one cheap solution cannot justify stopping; exhaustive examination can be necessary. This does not assert that every already-described irrelevant state must be visited on every input. Moreover, a reachable negative-cost cycle in a graph that can still reach a goal can make costs unbounded below, in which case no finite-cost optimal solution exists at all.
The vertex cover decision problem takes a finite simple graph and a nonnegative integer , and asks whether there is a vertex cover of cardinality at most . The optimization problem asks for a minimum vertex cover, with cost equal to its cardinality.
For the decision problem, if there are no edges, accept; if there is an edge but , reject. Otherwise choose an edge and branch: either include and recurse on with budget , or include and recurse on with budget . Accept if either branch accepts. Every vertex cover contains at least one endpoint of , so every possible solution is retained by at least one branch. Conversely, adding the selected endpoint to a vertex cover returned by the smaller instance covers all original edges. This proves correctness by induction on the remaining budget.
The search tree has depth at most and at most leaves. Processing each node in time gives running time, establishing fixed-parameter tractability.
For optimization, greedily build a maximal matching : repeatedly select an edge and discard every edge touching either endpoint. Return the set of all endpoints of . Any edge with neither endpoint in could be added to , contradicting maximality; thus is a vertex cover. Since the edges of a matching in a graph have pairwise disjoint endpoint sets, every vertex cover must contain at least one different vertex for each of them. Therefore
The greedy construction takes polynomial time, and can be implemented in with adjacency lists. It needs only a maximal matching, not a maximum matching.
A parameterized decision problem is fixed-parameter tractable if there is an algorithm deciding inputs of encoded length and parameter in running time at most , where is a computable function and is a constant independent of . Arbitrarily expensive dependence on the parameter is permitted; putting in the exponent of does not by itself establish fixed-parameter tractability.
For a minimization problem with nonnegative costs, a factor-two approximation algorithm runs in polynomial time, always returns a feasible solution, and satisfies on every feasible input. A feasible solution also satisfies . If the optimum is zero, the guarantee requires an answer of zero cost.
Let and choose any column probability vector , for example the first coordinate unit vector. Because has nonnegative entries and each row sums to one, maps the probability simplex
into itself: and .
The iterates need not converge, so take their arithmetic averages,
A telescoping sum gives
Both vectors on the right before subtraction have L1 norm one, so .
The probability simplex is closed and bounded in finite-dimensional Euclidean space, hence compact by the Heine-Borel theorem. It follows that a subsequence converges to some . Passing to the limit in the displayed identity, using continuity of the linear map , gives , with and .
This proves stationary distribution existence for a finite Markov chain without any Markov chain irreducibility or aperiodicity assumption. Those stronger hypotheses concern uniqueness and convergence, not the existence required here.
First suppose the stated nonnegative vectors exist. If , multiply by and by . Since and , this gives the contradiction
Thus the certificate implies .
For the converse, put
A common feasible point exists exactly when , . Introducing a nonnegative vector of slack variables makes this equivalent to
If this system is infeasible, the nonnegative-equations version of Farkas' lemma supplies an unrestricted vector such that
Split according to the original two blocks of inequalities. The three conditions become , and , exactly the desired certificate. Both directions are proved. The role of is essential: it is why the combined normal need only be nonnegative rather than zero.[ref]

Pinned article: Introduction to the OurBigBook Project

Welcome to the OurBigBook Project! Our goal is to create the perfect publishing platform for STEM subjects, and get university-level students to write the best free STEM tutorials ever.
Everyone is welcome to create an account and play with the site: ourbigbook.com/go/register. We belive that students themselves can write amazing tutorials, but teachers are welcome too. You can write about anything you want, it doesn't have to be STEM or even educational. Silly test content is very welcome and you won't be penalized in any way. Just keep it legal!
We have two killer features:
  1. topics: topics group articles by different users with the same title, e.g. here is the topic for the "Fundamental Theorem of Calculus" ourbigbook.com/go/topic/fundamental-theorem-of-calculus
    Articles of different users are sorted by upvote within each article page. This feature is a bit like:
    • a Wikipedia where each user can have their own version of each article
    • a Q&A website like Stack Overflow, where multiple people can give their views on a given topic, and the best ones are sorted by upvote. Except you don't need to wait for someone to ask first, and any topic goes, no matter how narrow or broad
    This feature makes it possible for readers to find better explanations of any topic created by other writers. And it allows writers to create an explanation in a place that readers might actually find it.
    Figure 1.
    Screenshot of the "Derivative" topic page
    . View it live at: ourbigbook.com/go/topic/derivative
  2. local editing: you can store all your personal knowledge base content locally in a plaintext markup format that can be edited locally and published either:
    This way you can be sure that even if OurBigBook.com were to go down one day (which we have no plans to do as it is quite cheap to host!), your content will still be perfectly readable as a static site.
    Figure 5. . You can also edit articles on the Web editor without installing anything locally.
    Video 3.
    Edit locally and publish demo
    . Source. This shows editing OurBigBook Markup and publishing it using the Visual Studio Code extension.
  3. https://raw.githubusercontent.com/ourbigbook/ourbigbook-media/master/feature/x/hilbert-space-arrow.png
  4. Infinitely deep tables of contents:
    Figure 6.
    Dynamic article tree with infinitely deep table of contents
    .
    Descendant pages can also show up as toplevel e.g.: ourbigbook.com/cirosantilli/chordate-subclade
All our software is open source and hosted at: github.com/ourbigbook/ourbigbook
Further documentation can be found at: docs.ourbigbook.com
Feel free to reach our to us for any help or suggestions: docs.ourbigbook.com/#contact