电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛

标题: 在 PyGTK 中管理部件几何结构（4）需求解决 [打印本页]

作者: look_w 时间: 2018-5-23 16:08 标题: 在 PyGTK 中管理部件几何结构（4）需求解决

需求解决列区间 [b,e) 中的列的每个大小需求 — 即符合 b <= c < e 的所有 c— 将得到其总和至少为某个值的一组大小。需求 r 用以下公式表示：
图 7. 列大小需求

我想找到满足需求不等式的 “最小” 大小（Si）。这实际上是一个线性编程问题。这种情况比一般的问题更特殊，因为：

所有因子就是 0 或 1。
所有为 1 的因子在一个连续的变量范围中。
我们只对整数解感兴趣。

由于这些特殊情况，最小解可能不是惟一的，所以我还要直观地衡量这个解。
我将简要描述可以提供合理解决方法的 req.Manager 类功能。由于这不是本文的重点，而且它的解决方法是次优的，这里不作详述。
这个类在一个单独的 req.py 模块中，该模块独立于 GTK+。该模块有一个内部测试，该测试使用 Python 的 if __name__ == '__main__': 结构。
下面是解决方法测试的一些例子。每个例子有一个给定的三元组 (Bi, Ei, Si)，这意味着要寻找一组大小，并应满足 [Bi, Ei) 的每个子区间加起来至少为 Si。
清单 16. req.Manager 解决方法示例

1
2
3
4
5
6
7
8
9
10
11

python req.py 0 1 20 1 2 30
Solution: [20, 30]

python req.py 0 2 10 1 3 5
Solution: [5, 5, 1]

python req.py 0 2 100 1 3 50
Solution: [46, 54, 6]

python req.py 0 2 100 1 3 50 2 3 20
Solution: [49, 51, 21]

向 req.Manager 添加需求下面是 req.Manager 类的构造函数，其中包含添加需求的方法。
清单 17. req.ManageraddRangeReq 方法

1
2
3
4
5
6
7

class Manager:
def __init__(self):
      self.rangeReqs = []
      self.reqs = None

def addRangeReq(self, rangeReq):
      self.rangeReqs += [rangeReq]

在这里，rangeReq 是以下类的一个对象：
清单 18. req.RangeSize

1
2
3
4
5

class RangeSize:
def __init__(self, be=(0,1), sz=1):
      self.begin = be[0]
      self.end = be[1]
      self.size = sz

通过启发式方法解决最佳解决方案需要线性编程技术，而且所需的代码更少。
清单 19. req.Manager.solve

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

def solve(self):
n = self.nSegments()
m = len(self.rangeReqs)
self.reqs = n * [0]
self.rangeReqs.sort()

# Satisfy single segment requirements
dumSingle = RangeSize((n, n+1), 1)
endSingleIndex = bisect.bisect_right(self.rangeReqs, dumSingle)
for rr in self.rangeReqs[ : endSingleIndex]:
      curr = self.reqs[rr.begin]
      needMore = rr.size - curr
      self.reqs[rr.begin] += needMore
bigRangeReqs = self.rangeReqs[endSingleIndex:] # non-single ranges

self.partialSatisfy(bigRangeReqs, 1, 2) # half
self.partialSatisfy(bigRangeReqs, 1, 2) # half
self.partialSatisfy(bigRangeReqs, 1, 1) # complete
return self.reqs

上面的清单 19 包括一个 solve() 方法，并采用一种启发式方法，该方法由以下步骤组成：

对需求排序。
满足 [b,e) 区间内 b+1=e 条件的单个元素需求。
对于每个未被满足的需求 r，加上 r 的未满足大小的一半（在 r 区间元素中平均分布）。这是通过调用 req.Manager.partialSatisfy 方法来完成的。这一步要做两次。
和前面的步骤一样，现在加上完整的 未满足的大小。

清单 20. req.Manager.partialSatisfy

1
2
3
4
5
6
7
8
9
10
11
12

def partialSatisfy(self, bigRangeReqs, rationN, ratioD):
# Thru reqs, add to satisfy  rationN/ratioD of requirement
for rr in bigRangeReqs:
      curr = sum(self.reqs[rr.begin: rr.end])
      needMore = rr.size - curr
      if needMore > 0:
         give = (rationN * (needMore + ratioD - 1)) / ratioD
         q, r = divmod(give, rr.end - rr.begin)
         for si in range(rr.begin, rr.end):
            self.reqs[si] += q
         for si in range(rr.begin, rr.begin + r):
            self.reqs[si] += 1

可以将它与 GTK+ 的 gtk_table_size_request C 代码作比较，后者具有：
清单 21. gtk_table_size_request 片段

1
2
3
4

GTK_table_size_request_pass1 (table);
GTK_table_size_request_pass2 (table);
GTK_table_size_request_pass3 (table);
GTK_table_size_request_pass2 (table);

和这些 gtk_table_size_request_pass {1,2,3} 函数的实现。

欢迎光临电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)