算法-分支限界法

算法设计与分析

Posted by MetaNetworks on December 3, 2019
本页面总访问量

二者比较

分支限界法 回溯
尽快找到一个解 找到所有解
广度优先搜索 深度优先搜索
根据要求之外还有限界函数(算每一个活结点的限界函数值,选取最有意义的一个扩展) 根据要求找解

分支限界法的分类

  • 队列式

  • 优先队列式

    • Python优先队列代码示例

      注意:类的比较在Python3中不是__cmp__,而是__eq____lt____ne____gt__

    • 1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      
        '''
        @Author: MetaNetworks
        @Date: 2019-12-03 08:08:55
        @LastEditors: MetaNetworks
        @LastEditTime: 2019-12-03 08:25:02
        @Description: MetaNetworks' Code
        '''
        from queue import PriorityQueue as PQueue
              
        class Job(object):
              
            def __init__(self, name,grade):
                self.name = name
                self.grade = grade
            def __eq__(self,other):
                return self.grade-other.grade == 0
            def __lt__(self,other):
                return self.grade<other.grade
              
        if __name__ == "__main__":
            p = PQueue()
            p.put(Job("MetaNetworks",100))
            p.put(Job("Kigtous",60))
            p.put(Job("Kingtos",80))
            while not p.empty():
                a =  p.get()
                print(a.name,a.grade)
                  
      

例题

链接