No label defined (Q4933704)

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 1386739
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 1386739

      Statements

      0 references
      0 references
      0 references
      11 January 2000
      0 references
      heuristic search techniques
      0 references
      multiobjective state space search
      0 references
      multiobjective problem reduction search
      0 references
      search of multiobjective game trees
      0 references
      Heuristic search techniques have been developed for different problem representations, such as state space representation, problem reduction representation, or game trees. Classically there are two major objectives of heuristic search: The first has been to understand the relation between heuristic accuracy and search complexity, the second to develop efficient search algorithms for obtaining optimal and suboptimal solutions. Later different types of heuristic search have been investigated like admissible, inadmissible, non-monotone or weighted heuristics. The performance of heuristic search strategies have been analyzed for worst case and average case behaviors and variants of the basic approach have been suggested to improve the performance of the search algorithms. In the book of Dasgupta, Chakrabarti and DeSarkar a search framework is studied where the assumption regarding the existence of a total order among the costs is relaxed. Since this model was originally proposed for extending heuristic search techniques to multicriteria optimization problems, the model has been named mulitobjective search model. The authors describe in detail there contributions to multiobjective state space search (searching under inadmissible heuristics, utility of pathmax, using an induced total order, and new multiobjective search strategies), multiobjective problem reduction search, and search of multiobjective game trees (non-inferior sets of outcomes, dominance algebra, pruning conditions, partial order \(\alpha-\beta\)). Applications of the newly developed techniques are presented, too. The book is organized as follows: Chapter 2 describes the multiobjective search model in detail and presents previous work. In Chapter 3 the contributions of the authors in multiobjective state space search is presented. Chapter 4 contains the modeling and implementation of three practical problems using the multiobjective model. Chapter 5 studies multiobjective problem reduction search. It is proved that the problem of identifying a non-dominated cost of a potential solution graph is NP-hard. Chapter 6 concerns multiobjective game tree search. The final Chapter 7 discusses several conclusions of the presented different approaches. The book is very clearly written and gives an excellent overview about ongoing research on multiobjective heuristic search.
      0 references

      Identifiers