| 主权项 |
一种计算中心内部物理主机的选择方法，其特征在于包括如下步骤：1)输入树及相关参数给定一个三元组集合G＝(T,r,g)，其中，T代表树，r代表树的根节点，g代表计算中心需要提供的虚拟机数目；在树中有三个变量函数：weight()、height()和path()，其中，weight(r)表示以r为根节点的树能够提供的虚拟机数目，height(r)表示以r为根节点的树的高度，path(r)表示以r为根节点的树存在的最远路径；树的子树的根节点以r<sub>n</sub>表示，n为正整数，n的取值范围为[1,n]，子树中的变量：weight(r<sub>n</sub>)、height(r<sub>n</sub>)和path(r<sub>n</sub>)，其中，weight(r<sub>n</sub>)表示以r<sub>n</sub>为根节点的子树能够提供的虚拟机数目，height(r<sub>n</sub>)表示以r<sub>n</sub>为根节点的子树的高度，path(r<sub>n</sub>)表示以r<sub>n</sub>为根节点的子树存在的最远路径；给定变量minHeight、minTree、minPath、longestPath、h1和h2，其中，minHeight表示遍历过程中局部最优子树的高度，minTree表示遍历过程中局部最优的子树，minPath表示遍历过程中局部最优子树的路径长度，longestPath表示遍历过程中局部最优子树的最长路径长度，h1表示遍历过程中第一高子树高度，h2表示遍历过程中第二高子树高度；2)数值初始化初始化变量，即height(r)＝0，path(r)＝0，height(r<sub>n</sub>)＝0，path(r<sub>n</sub>)＝0，minHeight初始化为无穷大，minTree初始化为空，longestPath＝0，h1＝0，h2＝0；3)树的遍历采用后序遍历的方法，从根节点r开始遍历树的所有节点；4)记录最小子树判断weight(r<sub>n</sub>)≥g是否成立，若weight(r<sub>n</sub>)≥g不成立，则n＝n+1，转至步骤3)继续遍历；若weight(r<sub>n</sub>)≥g成立，执行步骤5)；若minHeight≥height(r<sub>n</sub>)，则minHeight＝height(r<sub>n</sub>)；若minPath≥path(r<sub>n</sub>)，则minPath＝path(r<sub>n</sub>)；并记录最小子树minTree＝r<sub>n</sub>；5)判断树的遍历是否结束判断height(r<sub>n</sub>)>h1是否成立，若height(r<sub>n</sub>)>h1成立，则h2＝h1，h1＝height(r<sub>n</sub>)；若height(r<sub>n</sub>)>h1不成立，再继续判断height(r<sub>n</sub>)>h2是否成立，若height(r<sub>n</sub>)>h2成立，则h2＝height(r<sub>n</sub>)；若longestPath>path(r<sub>n</sub>)，则longestPath＝path(r<sub>n</sub>)，即获取最短的最长路径长度；若树没有遍历结束，则n＝n+1，转至步骤3)继续遍历；判断h2+h1>longestPath是否成立，若h2+h1>longestPath成立，则path(r<sub>n</sub>)＝h2+h1；若h2+h1>longestPath不成立，则path(r<sub>n</sub>)＝longestPath；6)得出最优子树判断minTree是否存在，若minTree存在，weight(r)＝weight(minTree),height(r<sub>n</sub>)＝height(minTree)；若minTree不存在，必须判断树T的虚拟机数目是否大于g，如果是，minTree＝r,weight(r)＝weight(minTree),height(r)＝height(minTree)，否则没有最优子树。 |
