No label defined (Q4140923)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3570374
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 3570374

      Statements

      0 references
      1977
      0 references
      Consider an automated problem solver. If it has data enough at its disposal, it is able to derive a linear plan for solving a given problem, i.e., it offers a sequence of operators such that the execution of each operator assures the applicability of the next one, the first operator is applicable immediately and the last one realizes the desired goal. If the problem solver has not data enough, it is forced to take into consideration, at least in some cases, several possible continuations of an operator execution and to postpone the decision, which possibility will be actually follow, to the execution stage. In this way branching plans result, however, they are often too large to be applicable in practice. We propose a method how to reduce the extent of branching plans by omitting their ``less important'' parts. When a branching plan is actually applied, just one of its branches is followed, so we can ascribe to each node of this plan the probability that this node will be applied when the branching plan in question is used. Given an \(\varepsilon>0\), we can erase all the nodes for which this probability does not exceed \(\varepsilon\). The extent of the branching plan reduced in this way can be majorized by \(\varepsilon^{-1}\log_2(\varepsilon^{-1})\) when the conditional probabilities of all successors of each node under the condition that this node has been reached belong to the interval \((\varepsilon,1 - \varepsilon)\); this estimate depends only on \(\varepsilon\). In general, the extent of the reduced branching plan can be majorized by \(\varepsilon^{-1}\cdot\ell\), where \(\ell\) is the length (number of nodes) of the longest branch of the original branching plan. Some consequences of these estimates are also discussed. [For the entire collection see Zbl 0351.00017.]
      0 references

      Identifiers