Extensions of Dynamic Programming for Combinatorial Optimization and Data Mining

✍ Scribed by Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov

• Publisher: Springer International Publishing
• Year: 2019
• Tongue: English
• Leaves: 277
• Series: Intelligent Systems Reference Library 146
• Edition: 1st ed.
• Category: Library

✦ Synopsis

Dynamic programming is an efficient technique for solving optimization problems. It is based on breaking the initial problem down into simpler ones and solving these sub-problems, beginning with the simplest ones. A conventional dynamic programming algorithm returns an optimal object from a given set of objects. This book develops extensions of dynamic programming, enabling us to (i) describe the set of objects under consideration; (ii) perform a multi-stage optimization of objects relative to different criteria; (iii) count the number of optimal objects; (iv) find the set of Pareto optimal points for bi-criteria optimization problems; and (v) to study relationships between two criteria. It considers various applications, including optimization of decision trees and decision rule systems as algorithms for problem solving, as ways for knowledge representation, and as classifiers; optimization of element partition trees for rectangular meshes, which are used in finite element methods for solving PDEs; and multi-stage optimization for such classic combinatorial optimization problems as matrix chain multiplication, binary search trees, global sequence alignment, and shortest paths. The results presented are useful for researchers in combinatorial optimization, data mining, knowledge discovery, machine learning, and finite element methods, especially those working in rough set theory, test theory, logical analysis of data, and PDE solvers. This book can be used as the basis for graduate courses.

✦ Table of Contents

Front Matter ....Pages i-xvi
Introduction (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 1-12
Front Matter ....Pages 13-13
Tools for Study of Pareto Optimal Points (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 15-21
Some Tools for Decision Tables (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 23-31
Front Matter ....Pages 33-33
Different Kinds of Decision Trees (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 35-48
Multi-stage Optimization of Decision Trees with Some Applications (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 49-71
More Applications of Multi-stage Optimization of Decision Trees (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 73-84
Bi-criteria Optimization Problem for Decision Trees: Cost Versus Cost (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 85-104
Bi-criteria Optimization Problem for Decision Trees: Cost Versus Uncertainty (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 105-122
Front Matter ....Pages 123-123
Different Kinds of Rules and Systems of Rules (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 125-129
Multi-stage Optimization of Decision Rules (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 131-149
Bi-criteria Optimization Problem for Decision Rules and Systems of Rules: Cost Versus Cost (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 151-172
Bi-criteria Optimization Problem for Decision Rules and Systems of Rules: Cost Versus Uncertainty (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 173-188
Front Matter ....Pages 189-189
Element Partition Trees: Main Notions (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 191-205
Multi-stage Optimization of Element Partition Trees (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 207-223
Bi-criteria Optimization of Element Partition Trees (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 225-233
Front Matter ....Pages 235-235
Matrix Chain Multiplication (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 237-243
Binary Search Trees (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 245-252
Global Sequence Alignment (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 253-259
Optimal Paths in Directed Graphs (Hassan AbouEisha, Talha Amin, Igor Chikalov, Shahid Hussain, Mikhail Moshkov)....Pages 261-268
Back Matter ....Pages 269-280

✦ Subjects

Engineering; Computational Intelligence; Artificial Intelligence (incl. Robotics)