大规模微流控生物芯片快速布线方法及设备

摘要

本发明实施例提供一种大规模微流控生物芯片快速布线方法及设备。所述方法包括：读入待布线生物芯片的连线端点位置信息、布线设计规则和芯片尺寸；根据芯片尺寸利用分治策略将待布线区域进行划分，获得多个布线子区域；获取待布线子区域利用基于规则的布线方法或半规则的A*搜索算法对待布线区域中的连线起点进行布线；利用坐标变换对未完成布线的布线子区域进行布线。所述设备用于执行所述方法，本发明实施例通过分治策略对待布线区域进行划分，并对划分后的一个待布线子区域利用基于规则的布线方法或半规则的A*搜索算法对待布线区域中的连线起点进行布线，再利用坐标变换实现对未完成布线的布线子区域进行布线，从而提高了布线的效率。

说明书

技术领域

本发明实施例涉及微流控生物芯片设计自动化技术领域，尤其涉及一种大规模微流控生物芯片快速布线方法及设备。

背景技术

微流体生物芯片，又称为芯片实验室，是指把生物、化学、医学分析过程的样品制备、反应、分离、检测等基本操作单元集成到一块微纳米尺度的芯片上，由微通道形成网络，以可控流体贯穿整个系统，自动完成分析全过程的技术。微流体生物芯片是微小型化的必然产物，可以有效减少试剂用量，提高灵敏度，带来巨大的经济效益。微流体生物芯片将在食品安全、生态环境监测与保护、疾病诊断等许多领域得到广泛应用，是下一代分析产品的主流技术。与传统试验设备相比，微流控生物芯片具有许多优点。

首先，考虑化学反应速率的影响条件，小巧便携的芯片实验室能更轻易地在设计阶段解决反应物的接触面积控制问题，解决试验阶段的温度控制问题，大大缩短样品的反应时间，提高试验效率。

其次，考虑试验成本问题。从试验器材成本角度来看，微流控芯片的制作材料大多是并不昂贵的单晶硅片、石英、玻璃和有机聚合物，只要解决芯片在设计阶段和在研究制作工艺时的成本消耗，正式投入使用之后，每一片芯片都将节约大量科研成本。从试验试剂成本角度看，生物、化学、医学试验采用的许多样品和试剂或成本高昂，或来源稀少，微米级别的微流控芯片可以比传统试验方式节约大量的珍贵样品。

最后，微流控生物芯片可以极为有效地平衡地区医疗资源或科研资源不均衡的问题，使得无法拥有先进仪器的地方能方便有效地完成疾病的检测、预防和治疗方案的研究，使得经费有限的实验室能进行原本复杂昂贵的实验，甚至使得普通家庭能拥有较为成熟有效的疾病控制方式，改善生存质量。

目前，微流控生物芯片的设计主要采用手工设计，采用AutoCAD甚至Photoshop等软件，由经过培训的设计人员，手工通过软件绘制芯片上的连线。这样的设计方式需要大量的时间消耗，一般需要几周甚至几个月的时间完成。针对用于药物传送的微流控生物芯片，尽管可以将其模型化为最小费用网络流问题，用计算机程序进行求解，但是由于其规模巨大，求解时间需要几十个小时，仍然难以接受。因此，如何提高对大规模微流控生物芯片的自动化布线效率，是现如今亟待解决的课题。

发明内容

针对现有技术存在的问题，本发明实施例提供一种大规模微流控生物芯片布线方法及设备。

一方面，本发明实施例提供一种大规模微流控生物芯片快速布线方法，包括：

读入待布线微流控生物芯片的待布线信息，所述待布线信息包括连线端点位置信息、布线设计规则和芯片尺寸，所述布线设计规则包括基于规则的布线方法或基于半规则的A*算法布线方法；

根据所述芯片尺寸，利用分治策略将待布线区域进行划分，获得多个布线子区域；

获取一个所述布线子区域作为待布线子区域，利用基于规则的布线方法或半规则的A*搜索算法对所述待布线区域中的连线起点进行布线；

根据已完成布线的所述待布线子区域，利用坐标变换对未完成布线的所述布线子区域进行布线。

另一方面，本发明实施例提供一种电子设备，包括：处理器、存储器和总线，其中，

所述处理器和所述存储器通过所述总线完成相互间的通信；

所述存储器存储有可被所述处理器执行的程序指令，所述处理器调用所述程序指令能够执行上述的方法步骤。

又一方面，本发明实施例提供一种非暂态计算机可读存储介质，包括：

所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令使所述计算机执行上述的方法步骤。

本发明实施例提供的一种大规模微流控生物芯片快速布线方法及设备，通过分治策略对待布线区域进行划分，并对一个待布线子区域利用基于规则的布线方法或半规则的A*搜索算法对待布线子区域中的连线起点进行布线，再利用坐标变换实现对未完成布线的布线子区域进行布线，从而提高了布线的效率。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为本发明实施例提供的一种大规模微流控生物芯片快速布线方法流程示意图；

图2为本发明实施例提供的坐标变换方法示意图；

图3为本发明实施例提供的基于规则的布线方法示意图；

图4为本发明实施例提供的一种A*搜索算法布线示意图；

图5为本发明实施例提供的A*搜索算法布线流程示意图；

图6为本发明另一实施例提供的利用A*搜索算法布线示意图；

图7为本发明实施例提供的电子设备实体结构示意图。

具体实施方式

为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

图1为本发明实施例提供的一种大规模微流控生物芯片快速布线方法流程示意图，如图1所示，所述方法，包括：

步骤101：读入待布线区域微流控生物芯片的待布线信息，所述待布线信息包括连线起点位置信息、布线设计规则和芯片尺寸，所述布线设计规则包括基于规则的布线方法或基于半规则的A*算法布线方法；具体的，获取待布线微流控生物芯片的待布线信息，其中，待布线信息包括连线起点位置信息、布线设计规则和芯片尺寸，应当说明的是，连线起点信息指待布线区域上的连线起点信息和连线终点信息，所谓连线起点就是待布线区域中的内部起点，连线终点就是待布线区域边缘的控制引脚，本发明实施例的目的是实现连线起点和连线终点的快速连接。连线起点信息可以包括待布线区域中连线起点的数量，以及各个连线起点的位置；连线终点信息可以包括待布线区域中的控制引脚的数量以及各个控制引脚的位置。布线设计规则包括基于规则的布线方法或基于半规则的A*算法布线方法。可以理解的是，待布线信息还可以包括其他信息，例如两连线起点之间的间距等，本发明实施例对此不做具体限定。

步骤102：根据所述芯片尺寸，利用分治策略将待布线区域进行划分，获得多个布线子区域；

具体的，在获取到待布线区域的待布线区域大小后，根据待布线区域大小将待布线区域进行划分，其划分所采用的是分治策略，分治策略就是将大规模的问题进行划分成多个规模较小的子问题，多个子问题互相独立且与原来的大规模问题形式一致，通过对小规模的子问题的解决，然后将各个子问题的解合并来获得大规模问题的解。例如：待布线区域在横方向上的宽为w，在纵方向上的高为h，可以通过对角线将待布线区域划分为4个布线子区域，其划分的具体公式为：

应当说明的是，可以将待布线区域根据实际情况进行划分为多个布线子区域，本发明实施例对此不做具体限定。

步骤103：获取一个所述布线子区域作为待布线子区域，利用基于规则的布线方法或半规则的A*搜索算法对所述待布线子区域中的连线起点进行布线；

具体的，取划分后获得的一个布线子区域作为待布线子区域，对该待布线子区域的连线起点进行布线，可以通过基于规则的布线方法，也可以通过基于半规则的A*搜索算法，其中，基于规则的布线方法是事先根据当前连线起点在待布线子区域中的位置信息确定布线规则，布线规则确定好之后，根据布线规则即可完成布线。基于半规则的A*搜索算法是事先确定对布线区域中的连线起点的布线顺序，根据布线顺序，利用A*搜索算法进行布线，A*搜索算法是一种静态路网中求解最短路最有效的方法，通过A*搜索算法可以实现当前连线起点在布线过程中的最优路径。

步骤104：根据已完成布线的所述待布线子区域，利用坐标变换对未完成布线的所述布线子区域进行布线。

具体的，对待布线子区域完成布线后，利用坐标变换，对待布线区域中的未完成布线的布线子区域进行布线。假设，将待布线区域划分为了8个布线子区域，图2为本发明实施例提供的坐标变换方法示意图，如图2所示，获取标号为1的布线子区域作为待布线区域，将1号布线子区域完成布线后，通过公式(1)进行坐标变换，完成对2号布线子区域的布线；通过公式(2)完成对3号布线子区域的布线；通过公式(3)完成4号布线子区域的布线；通过公式(4)完成5号布线子区域的布线；通过公式(5)完成6号布线子区域的布线；通过公式(6)完成7号布线子区域的布线；通过公式(7)完成8号布线子区域的布线，坐标变换的公式如下所示：

通过上述坐标变换即可实现对整个待布线区域的布线，应当说明的是，在从布线子区域中进行选择待布线区域时，可以选择一个，也可以选择两个或更多个，本发明实施例对此不做具体限定。

本发明实施例通过分治策略对待布线区域进行划分，并对待布线子区域利用基于规则的布线方法或半规则的A*搜索算法对待布线区域中的连线起点进行布线，再利用坐标变换实现对未完成布线的布线子区域进行布线，从而提高了布线的效率。

在上述实施例的基础上，所述利用分治策略将待布线子区域进行划分，包括：

采用水平中轴线和垂直中轴线将所述待布线区域划分为4个所述布线子区域，或采用水平中轴线、垂直中轴线和对角线将所述待布线区域划分成8个所述布线子区域。

具体的，利用微流控生物芯片的规则特性，即，微流控生物芯片一般都为长方形或正方形，且微流控生物芯片中的培养室都是均匀分布的，其中，每个培养室都是一个连线起点，因此可以通过水平中轴线和垂直中轴线将待布线区域进行划分为4个等分的布线子区域。或者可以采用水平中轴线、垂直中轴线和对角线将待布线区域划分为8个等分的布线子区域。划分的具体方法已经在上述实施例中描述，此处不再赘述。

在上述实施例的基础上，所述利用基于规则的布线方法对所述待布线子区域中的连线起点进行布线，包括：

根据预设规则计算得到当前连线起点的布线规则，根据所述布线规则对所述待布线子区域中的所述当前连线起点进行布线。

具体的，从待布线子区域中包括的所有的连线起点中获取当前连线起点，在布线过程中，需要一个连线起点一个连线起点进行布线，当前连线起点就是当前需要布线的连线起点。根据当前连线起点的位置信息以及待布线区域信息，利用预设规则计算该当前连线起点的布线规则，根据布线规则对当前连线起点进行布线，其中布线规则，就是规定当前连线起点的布线路径，使得当前节点沿着已经规划好的布线路径进行布线。

本发明实施例通过预设规则计算获得当前连线起点的布线规则，并根据布线规则对当前连线起点进行布线，实现了对待布线区域的自动布线。

在上述实施例的基础上，所述根据预设规则计算得到当前连线起点的布线规则，包括：

根据公式计算得到所述当前连线起点的布线规则；

其中，w为所述待布线区域在x轴方向上的宽度，h为所述待布线区域在y轴方向上的高度，n为在布线过程中需要重复次数，m为在布线过程中需要的移动步长，x_w为所述当前连线起点所在行对应的待布线点的个数，x_h所述当前连线起点所在列对应的待布线点的个数，i为所述当前连线起点对应的行数，y为在布线过程中所述当前连线起点对应的纵坐标值，pitch_w所述连线起点在横坐标方向上的间距，pitch_h为所述连线起点在y轴方向上的间距。

具体的，公式(8)就是预设规则中用到的一些参数计算公式，其中，公式(8)如下所示：

根据待布线区域建立直角坐标系，公式(8)中的w为待布线区域在x轴方向上的宽度，h为待布线区域在y轴方向上的高度，n为当前连线起点在布线过程中需要重复次数，m为在当前连线起点布线过程中需要的移动步长，x_w为当前连线起点所在行对应的待布线点的个数，x_h当前连线起点所在列对应的待布线点的个数，i为当前连线起点对应的行数，y为在布线过程中当前连线起点对应的纵坐标值，pitch_w连线起点在横坐标方向上的间距，pitch_h为连线起点在y轴方向上的间距，若连线起点在待布线子区域上均匀分布，则pitch_h＝pitch_w。应当说明的是，上述公式计算出的pitch_w为连线起点在待布线子区域中的最小间距，最终确定连线起点的间距的方法为，获取连线起点在待布线子区域中的最大间距，根据最小间距和最大间距，利用二分法获得最终的连线起点的间距。pitch_w的计算方法与上述类似，此处不再赘述。

本发明实施例通过公式计算得到布线规则中的一些参数，根据这些参数获得当前连线起点的布线规则，实现了对待布线子区域的自动布线。

在上述实施例的基础上，所述布线规则包括：

S501、获取当前连线起点坐标，并根据所述当前连线起点坐标和所述连线终点所在的边确定第一布线方向，所述布线方向与x轴平行或与y轴平行；

具体的，获取待布线子区域中当前连线起点坐标，根据当前连线起点坐标和连线终点所在的边来确定第一布线方向，如图2中的1号布线子区域的所有连线起点都在连线终点所在的边的右边，因此，第一布线方向为左，也可为x轴的负方向，如图2中的2号布线子区域，所有的连线起点都在连线终点的上边，因此，第一布线方向为下，也可为y轴的负方向。

S502、沿着所述第一布线方向移动一次；

具体的，从当前连线起点开始，沿着第一布线方向移动一次，应当说明的是，沿着第一布线方向移动一次所移动的距离为当前连线起点在第一布线方向上的间距，以图2中的2号布线子区域为例，从当前连线起点开始，向下移动一次，移动的距离为pitch_h。

S503、交替沿着与所述布线方向垂直的第二布线方向和所述第一布线方向移动n次；

具体的，在沿着第一布线方向移动一次以后，接着交替沿着第二布线方向和第一布线方向移动n次，即，先沿着第二布线方向移动一次，再沿着第一布线方向移动一次，共重复执行n次，其中第二布线方向与第一布线方向垂直，且在第二布线方向上移动的距离为当前连线起点在所述第二布线方向上的间距。仍然以图2中的2号布线子区域为例，先向左或向右移动pitch_w距离，再向下移动pitch_h距离。应当说明的是，第二布线方向是向左还是向右，可以根据实际情况确定。

S504、沿着所述第二布线方向移动，移动的距离为m；

具体的，执行完S403后，再沿着第二方向移动，且移动的距离为m，通过m＝i-y+2*pitch_h可以计算得出m的具体数值。

S505、沿着所述第一布线方向移动，直到移动至所述连线终点为止；

具体的，继续沿着第一布线方向移动，当布线至连线终点即完成了对当前连线起点的布线。

本发明实施例通过基于规则的布线方法来对待布线区域中的连线起点进行布线，通过该算法能够较快速的完成布线，提高布线的效率。

在上述实施例的基础上，所述布线规则包括：

S601、获取当前连线起点坐标，并根据所述当前连线起点坐标和所述连线终点所在的边确定第一布线方向，所述布线方向与x轴平行或与y轴平行；

具体的，获取待布线区域中当前连线起点坐标，根据当前连线起点坐标和连线终点所在的边来确定第一布线方向，如图2中的1号布线子区域的所有连线起点都在连线终点所在的边的右边，因此，第一布线方向为左，即x轴的负方向，如图2中的2号布线子区域，所有的连线起点都在连线终点的上边，因此，第一布线方向为下，即y轴的负方向。

S602、沿着所述第一布线方向移动距离为P-(a-a_i)，其中，P为所述当前连线起点在所述第一布线方向上的间距，a为所述当前连线起点在所述第一布线方向上对应的需要布线的连线起点个数，a_i为所述当前连线起点在所述第一布线方向上对应的序号；

具体的，从当前连线起点开始，沿着第一布线方向移动，其中，移动的距离为P-(a-a_i)，以图2中2号布线子区域中的一个连线起点为例，如果当前连线起点所在列一共有6个连线起点需要布线，且当前连线起点位于该列第4个，即当前连线起点在该列上对应的序号为4，是从连线终点构成的边开始数，两个连线起点在纵方向上的间距为P＝4，那么当前连线起点需要移动的距离为4-(6-4)＝2。

S603、交替沿着与所述布线方向垂直的第二布线方向和所述第一布线方向移动n次，若判断获知在沿着所述第二布线方向移动时遇到障碍，则沿着所述第一布线方向移动，直至避开所述障碍为止；

具体的，在沿着第一布线方向移动一次以后，接着交替沿着第二布线方向和第一布线方向移动n次，即，先沿着第二布线方向移动一次，再沿着第一布线方向移动一次，共重复执行n次，其中第二布线方向与第一布线方向垂直，且在第二布线方向上移动的距离为当前连线起点在所述第二布线方向上的间距。在沿着第二布线方向布线的时候如果遇到了障碍，那么就沿着第一布线方向移动，直到避开障碍为止，避开障碍后接着沿着第二布线方向布线，因此，遇到障碍之前，在第二布线方向移动的距离，与避开障碍后在第二布线方向移动的距离之和应该等于当前连线起点在第二布线方向上的间距。例如，在第二布线方向需要移动的距离为5，在移动距离为2时遇到了障碍，那么在避开障碍之后，还需要沿着第二布线方向移动的距离为3。应当说明的是在第一布线方向上的避障的处理方法在原理上与第二布线方向上的避障一致，即，在沿着第一布线方向布线时，如果遇到障碍，则向第二布线方向移动，直到避开障碍为止，在避开障碍后继续沿着第一布线方向布线。应当说明的是，第二布线方向与第一布线方向垂直，但是与第一布线方向垂直的有两个方向，具体选择哪一个方向可以根据实际情况预先设定。

S604、沿着所述第二布线方向移动，若判断获知在沿着所述第二布线方向移动时遇到障碍，则沿着所述第一布线方向移动，直至避开所述障碍为止，且沿着所述第二布线方向移动的距离为m；

具体的，执行完S503后，再沿着第二布线方向移动，且移动的距离为m，通过m＝i-y+2*pitch_h可以计算得出m的具体数值。在移动布线的过程过，如果遇到障碍，则沿着第一布线方向移动，直到避开障碍为止，然后再继续沿着第二布线方向移动。

S605、沿着所述第一布线方向移动，直到移动至所述连线终点为止；

其中，沿着所述第一布线方向移动一次的距离为所述当前连线起点在所述第一布线方向上的间距；沿着所述第二布线方向移动一次的距离为所述当前连线起点在所述第二布线方向上的间距。

图3为本发明实施例提供的一种基于规则的布线方法示意图，如图3所示，原点表示当前连线起点，黑色实线为基于规则的布线方法的布线情况，黑色方块为障碍。

本发明实施例通过在基于规则的布线方法的基础上加入了避障算法，使得在布线过程中如果遇到障碍，可以绕过障碍布线，对于单层电路，可以满足其所布的线不交叉，并且提高了布线效率。

在上述实施例的基础上，所述利用基于半规则的A*搜索算法对所述待布线区域中的连线起点进行布线，包括：

获取所述待布线子区域中所有的连线起点，并将所述连线起点对应的第一编号存入第一数组中；

根据预设规则将所述第一数组中位置最中间的第一编号对应的所述连线起点作为中间连线起点，从所述中间连线起点开始，依次对邻近所述中间连线起点且未完成布线的所述连线起点利用所述A*搜索算法进行布线。

具体的，获取待布线子区域中的所有的连线起点，可以根据预设规则，预先对连线起点进行编号，具体为，可以将所有的连线起点都投影到连线终点构成的边上，然后从左往右，或者从上往下依次对连线起点进行编号，应当说明的是，如果有两个或者多个连线起点投影到了一个点上，那么先对离连线终点构成的边远的连线起点进行编号。将连线起点的第一编号按照大小顺序存入到第一数组中。可以理解的是，也可以对连线终点按顺序编号，并将连线终点对应的第二编号存入第二数组中。

首先，从第一数组中获取位于最中间的第一编号，将最中间的第一编号对应的连线起点作为中间连线起点，同样的，从第二数组中获取位于最中间的第二编号，将最中间的第二编号对应的连线终点作为中间连线终点，对中间连线起点与中间连线终点利用A*搜索算法布线。例如：第一数组为[0，1，2，3，4，5，6]，此时，应选择第一编号为3对应的连线起点作为中间连线起点，又如第一数组为[0，1，2，3，4，5]，那么，第一数组中位于最中间的有两个，分别为2和3，对于这种情况，可以预先设定选择第一编号较小或者较大的作为中间连线起点。然后依次从中间连线起点往两边延伸布线，即依次选取第一数组中邻近中间连线起点对应的第一编号，对该邻近中间连线起点的第一编号对应的连线起点进行布线，同样的，从数组中选择邻近连线终点的第二编号对应的连线终点，再次利用A*搜索算法进行布线，依次类推。图4为本发明实施例提供的一种A*搜索算法布线示意图，如图4所示，先利用对角线将待布线区域划分为4部分，对最下面这个三角形区域进行布线，首先获取三角形区域中最位于第一数组最中间的第一编号对应的连线起点进行布线，即图4中的最上面的那个点，然后再对邻近最上面的那个点的两边延伸的点进行布线，图4给出的是已经完成布线的三个连线起点的示意图。

本发明实施例通过规定布线的顺序，并根据布线顺序利用A*搜索算法进行布线，能够快速的对待布线区域完成布线。

在上述实施例的基础上，图5为本发明实施例提供的A*搜索算法布线流程示意图，如图5所示，所述利用所述A*搜索算法对所述进行布线，包括：

步骤701、定义连线起点的扩展代价；通过A*算法的估价函数计算连线起点的扩展代价。

步骤702、创建待扩展节点的链表，按照扩展代价由小到大的顺序保存所有已访问而未扩展的节点，所述节点为所述待布线子区域的一个搜索到而未扩展的网格点；利用估价函数分别计算每个待扩展节点对应的扩展代价，应当说明的是，本发明实施例是在有网格的情况下进行布线的。

步骤703、判断待扩展节点链表中是否有待扩展节点，若判断结果为是，则执行步骤704，否则搜索结束并输出搜索失败；

步骤704、读取待扩展节点链表中扩展代价最小的节点，记为当前待扩展节点，并判断当前待扩展节点是否是连线终点，若判结果为是，则搜索结束，并输出搜索成功，否则执行步骤705；

步骤705、遍历当前待扩展节点允许的扩展方向，寻找出允许扩展方向上所有节点，并插入到相邻点列表中；

步骤706、遍历相邻点列表，针对当前待扩展节点生成多个新的扩展节点；

步骤707、计算新的扩展节点的扩展代价，并将其按照计算得到的扩展代价插入到待扩展节点链表的适当位置；

步骤708、重复步骤704至步骤707，直到搜索结束，获得所述连线起点到所述连线终点的目标布线路径；

步骤709、根据所述布线路径，获取到所述布线路径的曼哈顿距离为1的待扩展节点，并存入待检测列表中，若判断获知通过所述待检测列表中的待扩展节点，能够使得任意一个未完成布线的所述连线起点有对应的布线路径，则将所述目标布线路径输出。如果待检测列表中的待扩展节点，没有能够使任意一个未完成布线的连线起点能够找到一条布线路径，则说明目标布线路径是不合法的，即当前连线起点不能布线，从第一数组中获取邻近当前连线起点的下一列的连线起点进行布线。

图6为本发明另一实施例提供的利用A*搜索算法布线示意图，如图6所示，通过A*搜索算法，完成了对待布线区域进行划分后的最下面的布线子区域的布线。

本发明实施例通过利用A*搜索算法对待布线区域的连线起点进行布线，并将完成布线的待布线区域利用坐标变换的方式完成待布线区域中其他布线子区域的布线，提高了布线的效率。

在上述实施例的基础上，所述定义连线起点的扩展代价，包括：

通过估价函数定义所述连线起点的扩展代价，其中，所述估价函数为：

f(n)＝g(n)+h(n)；

其中，f(n)为所述连线起点经由所述节点n到所述连线终点的估价函数，g(n)为所述连线起点到当前节点的已布线路径的距离，h(n)为所述当前节点到所述连线终点的曼哈顿距离。

具体的，通过公式f(n)＝g(n)+h(n)可以计算出连线起点的扩展代价，其中，g(n)为连线起点到当前节点的已布线路径的距离，h(n)为当前节点到所述连线终点的曼哈顿距离。应当说明的是，通过上述公式也可以对待扩展节点进行估价。

本发明实施例通过分治策略对待布线区域进行划分，并对一个待布线区域利用半规则的A*搜索算法对待布线子区域中的连线起点进行布线，再利用坐标变换实现对未完成布线的布线子区域进行布线，从而提高了布线的效率。

图7为本发明实施例提供的电子设备实体结构示意图，如图7所示，所述电子设备，包括：处理器(processor)801、存储器(memory)802和总线803；其中，

所述处理器801和存储器802通过所述总线803完成相互间的通信；

所述处理器801用于调用所述存储器802中的程序指令，以执行上述各方法实施例所提供的方法，例如包括：读入待布线微流控生物芯片的待布线信息，所述待布线信息包括连线起点位置信息、布线设计规则和芯片尺寸，所述布线设计规则包括基于规则的布线方法或基于半规则的A*搜索算法布线方法；根据所述芯片尺寸，利用分治策略将待布线区域进行划分，获得多个布线子区域；获取一个所述布线子区域作为待布线子区域，利用基于规则的布线方法或半规则的A*搜索算法对所述待布线子区域中的连线起点进行布线；根据已完成布线的所述待布线子区域，利用坐标变换对未完成布线的所述布线子区域进行布线。

本实施例公开一种计算机程序产品，所述计算机程序产品包括存储在非暂态计算机可读存储介质上的计算机程序，所述计算机程序包括程序指令，当所述程序指令被计算机执行时，计算机能够执行上述各方法实施例所提供的方法，例如包括：读入待布线微流控生物芯片的待布线信息，所述待布线信息包括连线起点位置信息、布线设计规则和芯片尺寸，所述布线设计规则包括基于规则的布线方法或基于半规则的A*搜索算法布线方法；根据所述芯片尺寸，利用分治策略将待布线区域进行划分，获得多个布线子区域；获取一个所述布线子区域作为待布线子区域，利用基于规则的布线方法或半规则的A*搜索算法对所述待布线子区域中的连线起点进行布线；根据已完成布线的所述待布线子区域，利用坐标变换对未完成布线的所述布线子区域进行布线。

本实施例提供一种非暂态计算机可读存储介质，所述非暂态计算机可读存储介质存储计算机指令，所述计算机指令使所述计算机执行上述各方法实施例所提供的方法，例如包括：读入待布线微流控生物芯片的待布线信息，所述待布线信息包括连线起点位置信息、布线设计规则和芯片尺寸，所述布线设计规则包括基于规则的布线方法或基于半规则的A*搜索算法布线方法；根据所述芯片尺寸，利用分治策略将待布线区域进行划分，获得多个布线子区域；获取一个所述布线子区域作为待布线子区域，利用基于规则的布线方法或半规则的A*搜索算法对所述待布线子区域中的连线起点进行布线；根据已完成布线的所述待布线子区域，利用坐标变换对未完成布线的所述布线子区域进行布线。

本领域普通技术人员可以理解：实现上述方法实施例的全部或部分步骤可以通过程序指令相关的硬件来完成，前述的程序可以存储于一计算机可读取存储介质中，该程序在执行时，执行包括上述方法实施例的步骤；而前述的存储介质包括：ROM、RAM、磁碟或者光盘等各种可以存储程序代码的介质。

以上所描述的设备等实施例仅仅是示意性的，其中所述作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部模块来实现本实施例方案的目的。本领域普通技术人员在不付出创造性的劳动的情况下，即可以理解并实施。

通过以上的实施方式的描述，本领域的技术人员可以清楚地了解到各实施方式可借助软件加必需的通用硬件平台的方式来实现，当然也可以通过硬件。基于这样的理解，上述技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中，如ROM/RAM、磁碟、光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行各个实施例或者实施例的某些部分所述的方法。

最后应说明的是：以上实施例仅用以说明本发明的技术方案，而非对其限制；尽管参照前述实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分技术特征进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技术方案的精神和范围。