Book Report on “Fuzzy random minimum spanning tree problems through possibilistic programming and the expectation optimization model”
Part1: Theoretical basis
1.Fuzzy random variable 2.MST、Minimal Ratio Spanning Tree 3.Possibilistic Programming 4.Expectation Optimization Model
1.Fuzzy random variable
Definition and Usage : Fuzzy random variables generalize random variables, random vectors and random sets. The expected value of a fuzzy variable is a natural generalization of the integral of a set-valued function (Refer to Madan [1]). In short, the usage of fuzzy random variables is to simulate human decision or natural.
2.MST、Minimal Ratio Spanning Tree
Basic algorithm: Kruskal , Prim , Dinkelbach , Bisection Algorithm
New learning algorithm: Dinkelbach’s Method
Introduction of Dinkelbach’s Method:
This algorithm can solve the problems like find some point x0 which satisfies
This problem can convert to another form:
This problem can be solved with simple bisection algorithm. But Dinkelbach algorithm can solve this problem in O(log(nM)). This algorithm can be easily understood from graph.
As shown in the graph, we have to find θ0 that satisfied z(θ0) = 0, we try θ’ first, and we find z(θ’) > 0, and then , we can then assign next point θ = . This way is much quicker than Bisection algorithm. Besides, in MEGIDDO [2], that paper prove that the problem like ( , if problem like ( can be solvable within O[p(n)] comparisons and O[q(n)] additions, then B is solvable in time O[p(n)(q(n) + p(n))].
3.Possibilistic Programming ( Haven’t finished yet)
4.Expectation Optimization Model ( Haven’t finished yet)
Part2: The understanding of this thesis
Question 1: What?
In this paper, they deal with minimum spanning tree problems where each edge weight is a fuzzy random variable. After transform this problem into a more simple one , the problem to be solved is a minimum ratio spanning tree problem.
Question 2: How?
Fuzzy random variable, Possibilistic Programming , Expectation Optimization Model , Prim algorithm , Dinkelbach algorithm.
Question 3: Why better?
In this paper , the author just put forward a new way to solve the realistic problem . The algorithm he use is based on existing algorithm. So , I would like to say that the author is creative and good at knowledge application.
Part3: Unsolved Problem
Book Report( Fuzzy random variable , MST , Possibilistic programming)
原文：http://www.cnblogs.com/topW2W/p/5281913.html