python实现分支限界算法的案例

~ 分支限界法的基本思想：

求解目标：分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。

搜索方式：以广度优先或以最小耗费优先的方式搜索解空间树。分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。

此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。

分支限界法示例：

单源最短路径：

问题：给定一个带权 有向图 G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有各顶点的 最短路径 长度。这里的长度就是指路上各边权之和。

分析：

分支限界法的步骤如下：

1)按宽度优先策略遍历解空间树

2)在遍历过程中，对处理的每个结点i，根据界限函数，估计沿该结点向下搜索所可能达到的完全解的目标函数的可能取值范围—界限bound(i)=[dow(i), up(i)]

3) 从中选择使目标函数取的极小值的结点优先进行宽度优先搜索，从而不断调整搜索方向，尽快找到问题解。

在每次分支后，对凡是界限超出已知可行解值那些子集不再做进一步分支。这样，解的许多子集（即搜索树上的许多结点）就可以不予考虑了，从而缩小了搜索范围。

将这个图转化成树的形式，如下所示：

创建队列。 1．节点1入队列，Q＝｛1｝。

我们取出队头节点，作为扩散节点，更新他的后代的值。此题中更新节点2，3，4　的距离，并将他们加入队列，Q＝｛1，2，3，4｝。 完成后节点1出队。Q＝｛2，3，4｝。

2.同样，重复1的步骤，Q＝｛3，4，5，6｝；

3.当我们取到节点3时，我们发现源点－＞节点3－＞节点6的距离为11，大于1－2－6这条路径的权重，所以1－3－6这条路径之后我们不再考虑。 这就是“限界”（称为”剪枝“）的思想。

4.　重复步骤，直到Q为空。优先队列法方法和FIFO方法类似，区别在于优先队列每次取队列元素中到源点距离最短的点。

# -*- coding: utf-8 -*-

"""

Created on Sun Mar  7 19:03:09 2021

@author: iron

"""

# Author:Iron

# 初始化图参数 用字典初始初始化这个图

G = {1: { 2: 4, 3: 2,4:5},

    2: { 5: 7, 6: 5},

    3: {6: 9},

    4: {5: 2, 7: 7},

    5: {8: 4},

    6: {10:6},

    7: {9: 3},

    8: {10:7},

    9: {10:8},

    10:{}

    }

inf=9999

#保存源点到各点的距离，为了让顶点和下标一致，前面多了一个inf不用在意。

length=[inf,0,inf,inf,inf,inf,inf,inf,inf,inf,inf]

Q=[]

#FIFO队列实现

def branch(G,v0):

    Q.append(v0)

    dict=G[1]

    while len(Q)!=0:

          #队列头元素出队

          head=Q[0]

          #松弛操作，并且满足条件的后代入队

          for key in dict:

              if length[head]+G[head][key]<=length[key]:

                    length[key]=length[head]+G[head][key]

                    Q.append(key)

        #松弛完毕，队头出列

          del Q[0]

          if len(Q)!=0:

              dict=G[Q[0]]

'''

#优先队列法实现

def branch(G, v0):

    Q.append(v0)

    while len(Q) != 0:

          min=99999

          flag=0

          #找到队列中距离源点最近的点

          for v in Q:

              if min > length[v]:

                    min=length[v]

                    flag = v

          head = flag

          dict=G[head]

          #找到扩散点后进行松弛操作

          for key in dict:

              if length[head] + G[head][key] <= length[key]:

                    length[key] = length[head] + G[head][key]

                    Q.append(key)

          #松弛完毕后，该扩散点出队

          Q.remove(head)

'''

branch(G,1)

print(length)

运行结果：[9999, 0, 4, 2, 5, 7, 9, 12, 11, 15, 15]。

---

农安县18368351449： 如何用python实现巴斯卡三角形算法 - ？
苏敬乳癖： #coding=utf-8#usingpython2.7a=[[(i+1)*(j+1)ifi>=jelse''foriinrange(9)]forjinrange(9)]#1.for循环foriinrange(9):forjinrange(9):printa[i][j],'\t',print'\n'#2.while循环i,j=0,0whilei<9:whilej<9:printa[i][j],'\t',j+=1print'\n'i+=1j=0结果如图:

农安县18368351449： 算法分析与设计常见的分支限界法有哪些 - ？
苏敬乳癖： (1)队列式(FIFO)分支限界法 按照队列先进先出(FIFO)原则选取下一个节点为扩展节点. (2)优先队列式分支限界法 按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点.

农安县18368351449： 如何用python代码实现1 12 123 1234 12345 - ？
苏敬乳癖： def test(n):res=[]for i in range(1,n+1):val=''for j in range(1,i+1):val+=str(j)res.append(val)return res print test(5)

农安县18368351449： 请用Python实现CMAR算法 - ？
苏敬乳癖： 1.将开始节点放入开放列表(开始节点的F和G值都视为0);2.重复一下步骤:i.在开放列表中查找具有最小F值的节点,并把查找到的节点作为当前节点; ii.把当前节点从开放列表删除, 加入到封闭列表; iii.对当前节点相邻的每一个节点依次执...

农安县18368351449： python多线程几种方法实现 - ？
苏敬乳癖： Python进阶(二十六)-多线程实现同步的四种方式 临界资源即那些一次只能被一个线程访问的资源,典型例子就是打印机,它一次只能被一个程序用来执行打印功能,因为不能多个线程同时操作,而访问这部分资源的代码通常称之为临界区. ...

农安县18368351449： python计算每两个向量之间的距离并保持到矩阵中 - ？
苏敬乳癖： 在很多算法中都会涉及到求向量欧式距离,例如机器学习中的KNN算法,就需要对由训练集A和测试集B中的向量组成的所有有序对(Ai,Bi),求出Ai和Bi的欧式距离.这样的话就会带来一个二重的嵌套循环,在向量集很大时效率不高. 这里介...

农安县18368351449： 用python 将fastq to fasta 实现 最好详细代码 有例子 谢谢 - ？
苏敬乳癖： #! /usr/bin/perl -w #启用perluse strict; #启用严格的语法提示open (IN,＂1.fastq＂)||die ＂open error!\n＂; #打开数据源文件1.fastq,如果打开失败则终止并输出提示open (OUT,＂>1.fasta＂)||die ＂open error!\n＂; #打开输出文件1.fasta

农安县18368351449： Python里怎么实现switch case - ？
苏敬乳癖： python没有swich语句,可以使用if语句替代:if a == 1: pass elif a==2: pass else: pass

农安县18368351449： python apriori算法代码怎么实现 - ？
苏敬乳癖： class Apriori(object): def __init__(self, filename, min_support, item_start, item_end): self.filename = filename self.min_support = min_support # 最小支持度 self.min_confidence = 50 self.line_num = 0 # item的行数 self.item_start = item_start # 取哪...

农安县18368351449： 如何利用python语言实现机器学习算法 - ？
苏敬乳癖： 基于以下三个原因,我们选择Python作为实现机器学习算法的编程语言:(一) Python的语法清晰;(二) 易于操作纯文本文件;(三) 使用广泛,存在大量的开发文档. 可执行伪代码 Python具有清晰的语法结构,大家也把它称作可执行伪...