Detail Multigrid dynamic programming Bibliografi Author: Lawson, Linda Graynel ; Peterson, James K. (Advisor) Topik: MATHEMATICS|COMPUTER SCIENCE Bahasa: (EN )    ISBN: 0-599-82808-0     Penerbit: CLEMSON UNIVERSITY     Tahun Terbit: 2000     Jenis: Theses - Dissertation Fulltext: 9976931.pdf (0.0B; 1 download) Abstract This dissertation presents a unique combination of two well-known heuristics, Multigrid Methods and Dynamic Programming, each a proven mechanism for solving linear and non-linear problems, respectively. Multigrid Methods are commonly employed for the numerical solution of linear systems of the form Ax = b. Such systems arise in the numerical solution of a variety of differential, partial, and integral equations based on the discretization of derivatives using finite-difference formulae. As its name suggests, multiple “copies of varied resolution” of the discretized problem-known as grids, are used to obtain faster solutions. For each grid, the underlying n x n system of the form Ax = b can be solved iteratively by numerous methods such as Gauss-Seidel. Thus, for each grid representation of the discretized problem, there exists an Ax = b problem to solve, whose size or dimension coincides with the grid's resolution. Over the past decade, the desire for faster solutions and real-time results in all aspects of problem-solving has prompted the generalization of Multigrid Methods to cover a broad spectrum of problems, many of which have no association with any kind of physical grid. The focus of this dissertation is the performance of Multigrid Methods when used for finding the optimal solution of the Shortest Path Problem on large graphs. Indeed this is a non-classic use of Multigrid Methods, particularly when we consider the parameters of the Shortest Path Problem. Shortest Path Problems frequently occur in a variety of application settings due to the need to deliver a product from point A to point B in the most effective manner possible. Such problems are described over a graph or network domain wherein the different points or junctions along the delivery route are called states or nodes, and connections between junctions are known as edges. Each edge is associated with a non-negative numeric value known as its edge cost. The edge costs, together with edge connectivity of nodes, impose constraints which influence the goal to: “deliver from point A to point B, in the most effective manner”. Shortest Path Problems are nonlinear due to the resulting minimization operator that is required to determine and calculate “the most effective” delivery route. Finally, the solution strategy is an iterative computational method involving recurrent relations developed by Richard Bellman, and is known as Bellman's Dynamic Programming Equation. Dynamic Programming, though effective, is plagued by the Curse of Dimensionality, making it inefficient for solving large problems. (Abstract shortened by UMI.) Opini Anda Klik untuk menuliskan opini Anda tentang koleksi ini! Lihat Sejarah Pengadaan  Konversi Metadata   Kembali

Copyright © 2006, 2007 Unika Atma Jaya, all rights reserved