血脑屏障体外模型研发

西安医学院基础医学部

沙保勇 刘洁 景晓红

西安交通大学第一附属医院麻醉科

高巍

血脑屏障(blood-brain barrier, BBB) 是存在于中枢神经系统(central nervous system, CNS) 和血液循环系统之间的一种动态界面,其通过严格准确调控神经元功能所需的各种物质的运输,维持CNS 内环境的稳定。BBB 通过紧密连接(tight junctions,TJs) 等结构为CNS 构建了完整的生理性屏障,在保护CNS 免受各种有害物质损伤的同时,也成为帕金森病、脑卒中等CNS 相关疾病治疗药物不得不面对的壁垒。CNS 疾病治疗药物要经过12~16年的时间才能走向市场,很多药物在研发过程中,因无法通过BBB 渗透入脑组织达到有效剂量,而被淘汰。随着对BBB 结构研究的不断深入,以及各种新型制造技术的涌现,BBB 体外模型的研发和应用越来越受到关注,低成本、高通量筛选、高仿真、高重现率的BBB 体外模型的制备,对探究BBB 的正常生理功能、解释疾病状态下BBB 功能紊乱的机制、缩短CNS 药物研发周期、保障药物效果等尤为重要。基于此,本文综述了现有BBB体外模型的发展及优缺点,以期为BBB 体外模型的应用提供一定理论依据。

1 BBB的组成及功能

BBB 主要由脑微脉管内皮细胞(brain microvascularendothelial cells, BMECs)、周细胞、星形胶质细胞终足、基膜等结构组成,从BBB 的结构上看,临近的BMECs 通过建立TJs 形成BBB 的雏形,星形胶质细胞环绕在BMECs 细胞的外侧,周细胞嵌在BMECs 和星形胶质细胞之间。BMECs 既有外周内皮细胞,又有上皮细胞的特性,相邻BMECs 间存在连续的TJs,细胞具有低胞吞及胞转活性等。周细胞对脑毛细血管壁的形成、脑微脉管和BBB结构的稳定、毛细血管直径和脑血流量的调控具有重要的作用。星形胶质细胞(astrocytes) 通过细胞终足几乎包裹覆盖整个脑毛细血管。BMECs、周细胞、星形胶质细胞连续分泌细胞外基质蛋白,构成厚40~50 nm 的基膜。

为了实现BBB 的功能,BMECs、周细胞和星形胶质细胞需相互作用。研究表明,周细胞与BMECs 共用基膜,通过神经钙黏素等跨膜连接蛋白彼此结合,实现离子、代谢物、第二信使等物质交换,如BMECs 分泌的血小板衍生生长因子通过基膜形成密度梯度,调控周细胞的增殖和迁移。此外,在脑血管内皮细胞分化的过程中,星形胶质细胞通过基膜与BMECs 相互作用,共同调控关键蛋白的表达。疾病状态下,星形胶质细胞分泌的载脂蛋白e 能与周细胞表面的低密度脂蛋白受体相关蛋白1 相互作用,激活促炎性信号通路,导致BMECs 间TJs 蛋白和基膜的降解,引发BBB 功能紊乱。

2 BBB体外模型的发展目标

BBB 能保证CNS 内环境的稳定,在严格控制进出脑组织物质的同时,也成为制约CNS 疾病药物发展的壁垒。动物模型( 如通过原位脑灌注) 常被用于CNS 药物的研发,但因为种属差异大、实验费用高和药效预测能力差等原因,无法实现真实模拟人类反应的目的。随着对维持、调控BBB和CNS 内环境稳定机制的深入研究,越来越多的科研人员转向了BBB 体外模型的研制和应用。高保真BBB 体外模型的发展,一方面能提高CNS候选药物早期药效( 向脑组织渗透的能力等) 筛查的准确性,加速神经治疗药物的研发过程,另一方面能减少,甚至替代动物实验,保障动物福利。

体外模型旨在离体可控环境下,评估特定实验药物的生理性和病理性反应。比较理想的BBB 体外模型应该能在各种条件下,准确再现脑血管所处的复杂微环境,包括:(1) 所用脑血管内皮细胞应能展现和形成成熟BBB 时的表型,如转运蛋白、代谢酶等表达和分布应该具有非对称性 ;(2) 相邻的脑血管内皮细胞间能形成TJs 等结构,对物质有极严格的选择通透性 ;(3) 能真实再现生理或病理状态下细胞间的相互作用 ;(4) 能外加调控BBB 功能的各种生物、机械等因素,如生长因子、剪切应力等 ;(5) 能比较方便地实现正常模型向阿尔茨海默症、癫痫等疾病模型的转化 ;(6) 具有易制备、高通量筛选、高重现率等优点。

3 BBB体外模型构成组分的来源

要制备比较理想的BBB 体外模型,首先应考虑制备BBB 体外模型所需材料来源的问题。磷脂类似物/ 脂质可用于构建固化人工膜色谱模型和平行人工膜渗透模型,实现对CNS 药物渗透性及药物-膜相互作用的研究,但它们无法再现BBB 功能中主动外排、代谢转化等特性。现在,主流研究多从组织和细胞层面上,寻求有效的材料用于制备BBB 体外模型。

3.1 组织层面

组织层面上,通过成熟的实验方法,可以从动物或患者手术切除的脑组织中分离得到具有功能且结构相对完整的脑微脉管,其包含脑血管内皮细胞、周细胞、基膜及星形胶质细胞等部分。基于微脉管制备BBB 体外模型,能维持BBB 的结构和功能,而且源于患者的微脉管能为研究BBB 的病理改变及药物药效评判提供独特的样本,拥有巨大的优势;但微脉管分离纯化涉及机械搅动、酶解、过滤和密度梯度离心等过程,样品容易污染,BBB 的活性和完整性得不到保障。在样品制备的过程中,新分离的脑微脉管代谢活性会逐步消减,严重影响脑血管内皮细胞的可用性。同时,在后续药物实验中,分离纯化后的脑微脉管的变化情况较难表征。加上人类脑组织样品较难获取,这些问题限制了基于脑微脉管的组织模型的应用。软脑膜微动脉也可用于体外模型的制备,但其与BBB在转运蛋白极性分布、物质的选择通透性、药物代谢等方面有很大差异,并不实用。

3.2 细胞层面

基于细胞的BBB 体外模型最早出现在20 世纪90 年代初,随着BBB 体外模型研发技术的进步,现在科研人员已经可以利用不同种属来源的原代细胞、细胞系或干细胞,进行细胞单独培养或不同类型细胞的共培养,以制备各种功能的BBB 体外模型。结合电子显微镜和酶标记法的研究结果显示,BMECs 是BBB 发挥屏障作用的关键组分。因为TJs 的存在,一方面,能让脑毛细血管形成一层紧密的扩散阻挡层,导致BBB 出现高跨内皮电阻(transendothelial electrical resistance, TEER),严格限制水溶性物质向脑组织的渗透( 低渗透率) ;另一方面,能保障BMECs 功能的高度极性,使细胞血管腔侧和基底外侧的膜上非对称分布转运蛋白等物质。所以,现在对于BMECs 的使用和研究较多,其来源主要是原代分离培养、成熟的细胞系和干细胞诱导分化,不同来源细胞的优缺点比较详见表1。

表1 不同来源的BMECs优缺点比较

来源优点缺点
原代细胞细胞具有良好的BBB特性,易于进行病理研究,实验准确性相对较高分离纯化过程复杂,费用昂贵,分离得到的细胞数量少、来源不均一、易掺杂其他类型细胞,细胞存在种属和批次间差异
细胞系细胞来源广泛,易于培养,实验结果再现性强,实验成本低细胞培养过程中会逐步丧失BBB屏障特性,较难实现脑疾病病理学研究
干细胞具有诱导分化的优势,可源源不断提供人源细胞并维持BBB屏障相关特性 实验成本高,诱导分化过程复杂,分化细胞纯度受限,诱导分化技术有待成熟

3.2.1 原代细胞

原代培养的BMECs 主要来源于新鲜的脑组织,对于人而言,主要是患者外科手术切除的脑组织。从患者脑组织中分离的BMECs 带有疾病特异性,这为研究BBB 的发病机制提供了便利 ;但如果进行大规模的药物递送及通透性研究,健康的人类原代BMECs 必不可少,但其来源受到很大的限制。同时,源自大脑皮层和小脑皮层的BMECs 特性截然不同,提示原代培养BMECs 时应注意细胞来源的均一性。作为替代,牛、猪、大鼠及小鼠可作为BMECs 原代培养的主要来源。从形成密闭性屏障的特性上看,猪的原代BMECs 较有优势,对其进行单层细胞单一培养,TEER 能达到700~800 Ω•cm²。牛源和鼠源的原代BMECs,与星形胶质细胞或周细胞共培养后,TEER 也能达到200~400( 甚至600~700)Ω•cm² ;但原代BMECs 的分离纯化过程复杂且费用昂贵,加上不同种属和批次细胞间的差异,在很大程度上限制了其在实际中的应用。

3.2.2 细胞系

近20 年间,人们一直试图从动物和人身上分离得到能用于BBB 体外模型构建的细胞系,但很多因形成的屏障特性差( 低TEER 和高渗透率) 而被淘汰。现在使用比较广泛的是人CMEC/D3 (hCMEC/D3) 细胞、大鼠RBE4 细胞和小鼠bEnd.3 细胞,尤其是基于hCMEC/D3 细胞的生物学与药理学研究报道超过100 篇。hCMEC/D3 与人源星形胶质细胞共培养,静态时TEER 值可以达到140 Ω•cm² ,在剪切应力存在的情况下可以达到1 000 Ω•cm² 以上。hCMEC/D3 细胞传到35 代依然能够保持TJs 蛋白、BBB 内皮转运蛋白及受体(GLUT-1、转铁蛋白受体等) 的表达和极性分布。细胞系在培养的过程中依然存在会逐步失去许多BBB 特有的表型和病理学特征的问题,但从实用和低成本的角度上讲,脑血管内皮细胞系,尤其是hCMEC/D3细胞是BBB 体外模型研发的优先选择。

3.2.3 干细胞

干细胞研究的巨大进步为BBB 模型的发展注入了新的活力,尤其是诱导多能干细胞(inducedpluripotent stem cells, iPS 细胞)、胚胎干细胞及神经祖细胞已经被用于制备人类BBB 体外模型。研究表明,利用人iPS 细胞能分化得到BMECs,若将其与周细胞共培养24 h,TEER 值可以达到3500 Ω•cm² 。诱导分化而来的BMECs 与星形胶质细胞共培养,能显著性增强屏障的完整性,TEER值可达1 450 Ω•cm² 。若将人iPS 来源的BMECs与星形胶质细胞共培养在微流控装置上,TEER 值可以达到4 000 Ω•cm²,并持续维持在2 000 Ω•cm²左右。从理论上讲,分离健康个体或患者的干细胞,诱导分化后可以得到神经血管单元组件,这就为解决BBB 体外模型人源细胞来源少、BBB 屏障相关特性差等问题,以及后续的CNS 药物筛选、高通量研究提供了现实的解决方案。

3.2.4 其他

BBB 体外模型中使用的星形胶质细胞,可以是原代培养的细胞,也可以是细胞系,但培养相对简单的细胞系使用更广泛。研究表明,猪脑BMECs分别与大鼠原代星形胶质细胞、C6 胶质瘤细胞共培养,两种组合间形成屏障的效果无显著性差异。而牛脑BMECs 与C6 胶质瘤细胞共培养后能提高TEER 值,但其增强效果弱于牛脑BMECs 与大鼠原代星形胶质细胞共培养的结果。

4 BBB体外模型装置

当前,主流的BBB 体外模型主要是基于细胞层面进行装置研发,利用不同种属、来源的细胞单独或共培养,在不同的培养条件下,尝试再现BBB的结构、功能和特性。

4.1 静态培养装置

Transwell 静态培养装置可用于构造简单的BBB 体外模型,在细胞迁移、药物渗透性、肿瘤药物毒性等实验中具有高通量的优点。Transwell 装置被微孔膜隔成上下两个平行的腔室,分别代表着BMECs 的腔面和基底面,因腔室容积固定,可利用米氏动力学方程对物质转运进行简化研究。微孔膜的孔径为0.4~8 μm,允许物质交换,但孔径越小对细胞迁移的限制越大。实验表明,利用Transwell接种单层猪脑BMECs 时,细胞间可以形成TJs 且TEER 值可以达到800~1300 Ω•cm² 。但是,仅在微孔膜上接种单层BMECs,会出现细胞加速去分化、细胞黏着不规则、细胞间形成TJs 不完整、边缘效应诱发的细胞旁扩散等问题。现有研究证实,星形胶质细胞对BMECs 极性分布、TJs 表达等有积极的影响,而且BMECs 与星形胶质细胞共培养的TEER 值远高于仅单层BMECs存在的情况。因此,利用Transwell 实验时,建议不同种属和来源的脑血管内皮细胞与胶质细胞等共培养,以维持BBB 特性。BMECs、胶质细胞与周细胞也可共培养于Transwell 装置中,更好地实现BBB 的特性。但对于Transwell 装置而言,三种细胞共培养增加了装置的复杂性,降低了实用性,这对于相对简单的药物渗透实验和机制研究是否必要,仍有争论。

4.2 动态(微环境调控)培养装置

现已证明,微环境对细胞功能的发挥极其重要,除了与星形胶质细胞、周细胞的细胞间相互作用,BMECs 细胞分化及BBB 特性维持还需要剪切应力等微环境因素。Transwell 等静态培养装置无法提供调控BMECs 所需的剪切应力,因此,平行板流室(parallel-plate flow chambers)、微流控系统(microfluidic systems) 等可调控微环境的BBB 体外模型应运而生。

4.2.1 单培养装置

典型的平行板流室装置由上层( 聚碳酸酯材质)、下层( 玻璃盖玻片) 以及硅垫( 填充于上下层之间) 组成。聚碳酸酯材质的上层分布有进样口、出样口和真空槽。玻璃盖玻片可用胶原蛋白、纤连蛋白等包被,是单层细胞培养的场所。而硅垫的厚度决定了装置上下层之间形成的真空流道的高度。平行板流室可用于转移性肿瘤细胞与脑血管内皮的黏附作用、肿瘤细胞跨内皮迁移、白细胞与BMECs相互作用、细胞趋药性、微环境调控细胞形态以及药物对脑血管内皮细胞功能影响方面的研究。平行板流室装置的优点包括:(1) 能再现机体生理状态下的剪切应力,范围从0.01~30 dyn/cm² ;(2) 装置设计简单,方便使用;(3) 细胞用量少;(4) 装置透明,便于实时长期显微观察;(5) 可扩展成类似Transwell 的装置。但平行板流室装置无法实现BMECs 与胶质细胞、周细胞的共培养,无法再现BBB 真实的功能特性。

4.2.2 微流控培养装置

过去几年中,为克服单培养动态模型的缺陷,更好地模拟BBB 结构和特性,微流控BBB 体外模型( 微流控系统) 走上舞台,且种类层出不穷。微流控系统在高通量药物筛选、实时动态监测TEER等方面进行了积极的尝试。

热塑性聚合物( 如聚丙烯) 可制备形成中空纤维结构,动态BBB 体外模型(dynamic in vitro BBBmodel, DIV-BBB) 就是利用这种中空纤维结构模拟脑微脉管。在DIV-BBB 中,BMECs 接种培养在人造微脉管的内表面( 腔面) 上并暴露于近生理脉动流中,星形胶质细胞并行培养于中空纤维的外表面( 基底面),两种细胞的空间分布及培养环境类似于在体微脉管的状态。DIV-BBB 装置连接有变速泵,能产生脉冲式流动,基于人造微脉管内径大小、腔内液体的黏度及流量等参数,可调控所产生的剪切应力的大小,并将其控制在5~23 dyn/cm² 的范围内,与在体CNS 的数据一致。此外,DIV-BBB装置允许共培养胶质细胞,使BMECs 表现出更加优异的BBB 特性,如低细胞旁通透性、高TEER、特异性转运蛋白极性分布等,这对于提高CNS 药物筛选的准确性和有效性非常重要;DIV-BBB 装置能长时间维持细胞活性和BBB 的特性,并模拟中风等疾病中流变环境的改变,使其具有扩展制备神经疾病模型的能力。DIV-BBB 装置同样存在缺陷,如破坏BBB 模型才能表征中空管内表面培养细胞的状况,聚丙烯等亲脂材料的使用会影响亲脂性药物运输结果的真实性,无法实现药物高通量筛选等。

合成微脉管BBB (synthetic microvasculature BBB,SyM-BBB) 装置是一种由玻璃和聚二甲基硅氧烷(PDMS) 构成的低成本、简易微流控芯片,由分布于同一水平面上的腔面和基底面通道组成,通道孔径为3 μm×3 μm,彼此间可以进行液体交换。BMECs 培养于腔面通道,与星形胶质细胞条件培养基等相互作用后,可形成TJs 并高表达紧密连接蛋白-1 和P-gp 蛋白。该装置便于光学观察并能实现液体的连续灌注,在神经系统疾病药物药效评价、正常生理状态下BBB 信号传导机制和BBB 功能紊乱致病机理研究中有潜在的应用,但也存在无法检测TEER 值、无法与星形胶质细胞等共培养、无法进行高通量筛选等缺陷。

微流体BBB (microfluidic BBB, μBBB) 装置由4 层PDMS 和2 个嵌入式电极构成,腔面和基底面通道均可实现液体流动,能清晰成像(PDMS 材质透明),并可轻松地实时监测TEER。流体灌流状态下,利用μBBB 装置共培养鼠源BMECs 和星形胶质细胞,TEER 值超过250 Ω•cm²,是该装置静态培养下TEER 值的10 倍。μBBB 装置是一种低成本、可再生的微流控平台,但其产生的剪切应力(2.3×10−2 dyn/cm²) 远低于正常机体的数值。作为发展,BBB 芯片(BBB-on-a-chip) 仅由两层PDMS 及中间10 μm 厚的聚碳酸酯膜构成,每一层均分布有细槽( 宽500 μm,高100 μm) 和铂电极。BBB 芯片虽然设计极简单,但实验过程中可提供正常生理范围内的剪切应力,具有扩展构建人类脑相关疾病模型的能力;易于显微观察和TEER 检测的特点,使此类装置便于监控BBB 对外界刺激物( 如各种药物) 的反应,在药物转运、药物筛选等方面有广泛的应用前景。

NVU 芯片(neurovascular unit-on-a-chip) 由神经模块( 神经元、星形胶质细胞和小胶质细胞) 和血管模块(BMECs) 组成,两个模块分别培养细胞后再组装在一起,用于研究神经血管间的相互作用。相关研究表明,加入肿瘤坏死因子α (tumor necrosisfactor α, TNF-α) 可使葡萄聚糖的通透性增加2 倍,表明NVU芯片形成的BBB模型具备正常的功能。在血管模块中添加TNF-α,可促进神经模块中小胶质细胞形态的变化并显著增强胶质纤维酸性蛋白的表达。NVU 芯片在神经元与脑脊液相互作用、脑组织中化学信号传递、神经系统疾病发生中炎症的作用机制、药物功效和毒性预测等方面广泛应用,表明了该装置的应用优势,但该装置并未考虑神经模块长期培养等问题,仍有改进的空间。

3D NVU 装置(three-dimensional neurovascular unitmodel) 是在PDMS 中间嵌合纳米多孔膜制备成的一种微流控NVU 装置,该装置可进行3D 细胞培养并提供5 dyn/cm² 左右的剪切应力。在3D NVU装置中,脑内皮细胞生长在透明的聚四氟乙烯纳米多孔膜上,脑内皮细胞的形态、蛋白表达情况可通过染色( 在不破坏装置的前提下) 直接用显微镜观察;与脑内皮细胞共培养的星形胶质细胞生长在3D 鼠尾胶原水凝胶中,3D 培养的星形胶质细胞在第4 天时活性仍高于90% ;脑内皮细胞和星形胶质细胞能形成良好的屏障并可共培养至少14 d 。3D基质和聚四氟乙烯纳米膜的使用,使该装置在构建细胞3D 培养环境和实时显微观察方面显现出了优势,为CNS 药物代谢动力学实验、药效分析、脑内皮细胞功能研究等提供了便利,但其依然存在无法实时监测TEER 值等问题。

NV 生物反应器(neurovascular bioreactor) 是通过3 层PDMS 和1 层聚碳酸酯膜构建形成的BBB体外模型,该生物反应器有2 条灌注通道,1 条用于流通原代脑内皮细胞所需的培养基,另外1 条用于流通原代星形胶质细胞、原代周细胞和神经元(hiPS 细胞诱导分化而来) 所需的培养基,实现了对BBB 腔面和基底面的物质( 如药物、营养) 运输的分别控制。基于I 型胶原的神经元3D 培养、全部4 种人源细胞及2 条微流控通道的应用,使NV生物反应器成功再现了BBB 的结构和功能。全人源细胞的使用,使得该装置能更真实地反映药物对神经元的效用,更准确地得到药物渗透性及毒性数据,更有效地揭示神经元对BBB 功能正常发挥的作用机制,但TEER 实时监控方面的缺陷以及相对复杂的装置制备过程限制了其应用空间。

类机体BBB 芯片(in vivo-like BBB chip) 由3D打印的盖板、腔室层、灌流层以及1 个细胞培养区构成,通过在多孔膜两侧共培养BMECs ( 人源iPS细胞诱导而来) 及大鼠原代星形胶质细胞,能长时间模拟并维持在体BBB 的特性。该微流控装置的最大特点是基于人脑中血液的滞留时间进行设计,可以在无泵驱动的前提下,利用管壁剪切应力调控细胞间TJs 的形成,同时实现细胞的长时间共培养(10 d 以上)。咖啡因、西咪替丁和阿霉素等药物实验表明,类机体BBB 芯片可利用循环灌注对药物渗透性进行研究,且获得的渗透系数等结果与体内数据有可比性。

基于以上微流控BBB 体外模型,血液流动产生的剪切应力对BBB 功能的影响被深入研究,但血液流动还伴有其他力学性质的改变,如血管的周期性收缩。微流控BBB 体外模型中,聚合物膜的使用在为脑内皮细胞提供支持的同时,也限制了其周期性收缩发生的可能 制备了一种基于PDMS 的新型3D BBB (3D blood-brainbarrier model) 装置,其首先将含有基质胶、I 型胶原、人源星形胶质细胞等组分的混合液加入PDMS 装置中的人源星形胶质细胞培养区,并插入直径180mm 的针灸针,待水凝胶形成后拔掉针灸针,形成带有通道的星形胶质细胞3D 培养的结构;然后,将hCMEC/D3 种植到通道中,旋转装置使细胞覆盖通道内壁。该装置在灌流的过程中,不仅能产生剪切应力,还能使通道搏动,这使得体外研究血管周期性收缩调控BBB 基膜中废物转运、脑内皮细胞药物渗透等问题成为可能。通过在通道两侧外接不同设备,可实现对液体流速和脑内皮细胞周期性收缩的控制,以及TEER 值的检测,这对于研究剪切应力、血管周期性收缩对BBB 物质运输及内皮细胞功能的影响非常重要,也有利于提高药效研究的真实性和准确性。该装置在TEER 值实时监测、药物高通量筛选等方面还需进一步改进。

5 展望

从低成本、易操作的单层BMECs 培养模型,到共培养、三培养的静态模型,再到细胞微环境可控的微流控系统,BBB 体外模型一直在向离体再现BBB 在体功能的方向发展。随着生物技术、材料工程等学科的发展,现有BBB 体外模型在简单细胞微环境再现、血液动力学调控、对刺激物进行病理/ 生理反应等方面实现了突破,但“类生理”状态再现不是对BBB 在体生理功能的完全再现。相对于结构复杂,多种细胞和组分相互紧密协作且多样微环境并存的在体BBB 而言,BBB 体外模型更多地是在离体且严格受控的环境下,评估特定刺激物的生理或病理反应,而这些反应往往很难直接利用人体进行重现、修改或描述。例如,将基于干细胞的BBB 体外模型作为CNS 药物筛选的平台,可以更准确地评估药物的治疗效果和副作用,在加速药物研发进程的同时,避免盲目临床试验的高昂费用。

BBB 体外模型虽然越来越接近于人类机体,但现在依然缺乏非常可靠的在体实验和BBB 体外模型的关联数据,基于BBB 体外模型的药物渗透性实验结果还无法直接用于体内实验。虽然BBB体外模型与在体BBB 仍存在较大差异,但现阶段CNS 相关疾病的研究和CNS 疾病治疗药物的研发,需要低成本、高通量筛选、高仿真、高重现率的BBB 体外模型,而且微流控装置的发展为仿真BBB 模型的制备指明了方向。利用新技术、新工艺、新方法和新材料,制备具有3D 组织构造、多种细胞相互作用、细胞微环境可准确调控以及高通量药物筛选的BBB 体外模型,最终会加速CNS 相关疾病研究、治疗药物研发等诸多变革。

改进回溯算法实现N皇后问题求解

中国电子科技集团公司第二十一研究所

原慧芳 于慧敏

引言

随着近期围棋人机大战的赛况播出,好多编程爱好者对于传统的计算机算法开始进一步的研究探索。要说的回溯算法是算法设计基本原理中最通用的技术之一,也是人工智能中问题求解的基本方法,如果要搜索一系列解,或者解决满足一定约束条件的最优解问题,可以应用回溯算法。在很多现实的问题中,合法的解可能要通过在一个大量的但有限的多种可能性中做穷尽的搜索才能获得,这样的问题称为组合问题。并且,有些组合问题,除了穷尽搜索外尚未找到其他的办法。所以,开发一种系统的、能减少搜索空间的搜索技术是有必要的,回溯的搜索技巧用在穷尽的搜索过程中,能避免搜索所有的可能情形。回溯算法普遍地适用于解决需要检测有限但却是大量的可能解的组合问题。对解决组合问题的回溯算法稍加修改,还可以用来解决组合优化问题:在所有的可能解中计算最优解。

回溯算法

回溯法是一种选优搜索法,按选优条件向前搜索,以达到目标,当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术称为回溯法。

状态空间树

解空间的树结构称为状态空间树。树中的每一个节点定义一种问题状态。从根节点到其他节点的所有路径定义整个问题的状态空间,解状态是一些解状态 s,从根到 s 的路径定义解空间中的一个元组。答案状态是指那些解状态 s,从根节点到 s 的路径定义一个元组,且这个元组为问题的解集合(满足隐式约束)中的一个元素。

使用状态空间树,就可以系统地生成问题状态,决定其中的哪些状态是解状态,最终决定哪些解状态是答案状态的方式来解决问题。这种方式是从根节点开始,然后再生成其他的节点。节点已经生成,但是其子节点还未生成,这种节点称为活节点。对于一个活节点,当前它的子节点正在生成,称为可拓展节点,一个已经生成、不再扩展的节点,或者子节点都已经生成的节点称为死节点。界限函数用于删除活节点,无需生成它的所有子节点。界限函数必须设计的非常严密,使得在整个过程完成时,至少生成一个答案节点,如果问题本身需要寻找所有答案,就可以得到所有节点。带有限界函数的深度优先节点生成法也就是回溯法。

回溯算法的形式化描述

设 \( \left ( x_{1},x_{2},…x_{i} \right ) \) 为根节点到状态空间树中任一节点的路径。设 \( T \left ( x_{1},x_{2},…x_{i} \right ) \) 为xi+1的所有可能的值的集合,且满足 \( \left ( x_{1},x_{2},…x_{i+1} \right ) \) 也是到一个问题状态的路径。则\(T \left ( x_{1},x_{2},…x_{i+1} \right ) = \Phi \) ,假定限界函数 \(B_{i+1}\) (用谓词表示)存在,且满足从根节点到问题状态的路径的 \( \left ( x_{1},x_{2},…x_{i+1} \right ) \) 值为假,那么这个路径就无法拓展得到答案节点。因此,解向量 \( \left ( x_{1},x_{2},…x_{n} \right ) \) 的第 \( i+1 \) 个位置的后选值就是那些由生成且满足限界函数 \(B_{i+1}\) 的值。

递归回溯算法

解向量 \( \left ( x_{1},x_{2},…x_{n} \right ) \) 可以作为一个全局数组 \(x[1∶n]\)。逐个生成满足 \(B_{k}\) 的元组中的第 k 个位置处所有可能的元素,然后把它连接到当前向量 \( \left ( x_{1},x_{2},…x_{k-1} \right ) \) 中,每当连接一个 \(x_{k}\) 时,检查是否得到了解,然后对这个算法进行递归调用。当外层 for 循环退出 \(x_{k}\) 就不复存在,当前的 Backtrack 结束。在通过调用 Backtrack(1) 开始。

非递归回溯算法

使用深度优先搜索逐个产生解向量的每一个位置的值,变量k不断增加,解向量也不断完善直到找到一个解或者 \(x_{k}\) 的取值都已尝试过,当 k 减小时,将继续生成还未尝试的第 k 个位置的可能元素。直到最后回溯退回 k 的值减为 0 退出循环。

回溯算法解决 N 皇后问题

问题描述

经典的 N 皇后问题是指如何在一个 N*N 的棋盘上放置 N 个皇后使得任意两个皇后之间不能互相攻击,即他们不能处在同一行、同一列、同一对角线上。假设第 i 个皇后就是位于第 i 行上,可以用\( \left ( x_{1},x_{2},…x_{n} \right ) \) 表示一个解, \(x_{i}\) 表示第 i 个皇后所在的列号。则一个互不攻击的格局应该满足以下两个约束条件。N 皇后问题就转化为如何尽快求得所有合理布局的解。

\(x_{i} \neq x_{j} ; i \neq j \) (1)

\(x_{i}-x_{j} \neq \pm \left ( i-j \right ) ; i \neq j \) (2)

回溯法求解N皇后问题

利用回溯算法求解 N 皇后问题,可以将该问题的解空间组织为树结构,然后以深度优先的方法搜索。以 4 皇后为例,假设初始的根节点为唯一的活节点,此节点为可拓展节点,路径为()。接着生成一个子节点,假设子节点按升序生成。因此生成图1中的编号为2的节点,路径为(1),也就是将第一个皇后放置于第一列上。节点2成为可拓展节点,生成节点3,发现冲突又删除,下一个生成的节点为节点8,路径为(1,3)。节点8又成为可拓展节点,通过检查发现它的所有的子节点组成棋盘布局不是一个合法的布局,因此也被删除。因此回溯到节点2,生成另外一个子节点13,路径为(1,4)。如此继续,图1给出了回溯算法解决 4 皇后的部分生成树。N皇后也类似。节点下面标的D表示在搜索的过程中删掉的节点,也就是不可能生成可能的解的节点。

4皇后回溯过程中生成的部分树

回溯算法是一个既带有系统性又带有跳跃性的搜索算法,它在包含问题的所有解空间树中,按照树的先根遍历的搜索策略,从根节点出发搜索解空间树,搜索到解空间树的任一节点时,首先判断该节点是不是能够满足部分解的界限函数,如果不能满足,则跳过该节点为根的子树的搜索。逐层向其祖先节点回溯,否则进入其子节点继续搜索。在回溯法求解N皇后问题中,要回溯到根节点,且所有的子树都已经搜索完成才结束。因此搜索了全部的解空间,在搜索的过程中应用界限函数,也就是不能满足合理布局的约束条件,避免了无效解的搜索。

用非递归回溯算法实现N皇后问题,通过设计一个栈来保存的部分解,发现N皇后问题的空间复杂度(在 N<27 的情况下)是多项式的空间复杂度而不是指数的空间复杂度。

最坏情况下总的时间复杂度为 \(O\left ( n^{n+1}) \right )\) 。

改进的回溯算法求解 N 皇后问题

对于任一合理布局的经过有限次顺时针旋转、逆时针旋转、水平旋转、垂直翻转及其复合所得的结果仍是一个合理的布局。

基于这条公理,对回溯算法进行改进以提高效率,对棋盘的翻转可以有垂直翻转、顺时针翻转、逆时针翻转、对直线 y=x 和 y=-x 做轴对称翻转,主要考虑顺时针旋转 90 度, 180 度和 270 度。

设 \(x=\left ( x_{1},x_{2},…x_{n} \right )\) 是一个合法解,则顺时针旋转 90 度得到 \(y=\left ( y_{1},y_{2},…y_{n} \right )\) 也是一个合法解。记为 \(y=TURN90 \left( x \right)\) ; x 经顺时针旋转 180 度得到 y 也是一个合法解,记为 \(y=TURN180 \left( x \right)\) ;经顺时针旋转 270 度得到也是合法解,记为 \(y=TURN270 \left( x \right)\) 。对于任何一个合法解的合理棋盘布局,顺时针旋转 360 度将仍是该解本身,因此对于任一合法解 x 满足以下关系。

\(x=TURN^{4}90\left ( x \right )=\) \(TURN^{2}180\left ( x \right )TURN90(TURN270\left ( x \right ))\)

(3)

\(TURN90\left ( x \right )=TURN^{3}270\left ( x \right )=\) \(TURN180\left ( TURN270\left ( x \right ) \right )=\) \(TURN270\left ( TURN180\left ( x \right ) \right )\)

(4)

\(TURN270\left ( x \right )=TURN^{3}90\left ( x \right )=
\) \(TURN180\left ( TURN90\left ( x \right ) \right )=
\) \(TURN90\left ( TURN180\left ( x \right ) \right )\)

(5)

由以上公式可以看出,旋转变换具有以上等效关系,因此,在考虑对任一个合理布局应用 3 个旋转变换函数时,每种变换只应用一次。只需要确定顺时针旋转 90 度、180 度、270 度之后的格局不是原来的格局,就可以对该合理格局进行旋转以产生新的格局。

对于可以进行顺时针旋转 90 度的格局,也就是该格局顺时针旋转 90 度后的格局不是其本身。如果一个合法格局的解用一维数组 \( A[1:n] \) 表示,即 \(x=A[1:n],xi=A[i]\) 。那么如果一个格局存在 \(x=TURN90(x)\) 关系的布局,满足关系为:

如果 \(A[1]=num\) ,则有\(A[N-num+1]=1\) (6)

对于可以进行顺时针旋转 180 度的格局,也就是该格局顺时针旋转 180 度后的格局不是其本身。如果一个合法格局的解用一维数组\(A[1:n]\)表示,即 \(x=A[1:n]\) , \(xi=A[i]\) 。那么如果一个格局存在 \(x=TURN180(x)\) 关系的布局,满足关系为:

如果 \(A[1]=num\) ,则有\(A[N]=N-num+1\) (7)

对于可以进行顺时针旋转 270 度的格局,也就是该格局顺时针旋转 270 度后的格局不是其本身。如果一个合法格局的解用一维数组 \(A[1:n]\) 表示,即 \(x=A[1:n],xi=A[i]\)。那么如果一个格局存在 \(x=TURN180(x)\) 关系的布局,满足关系为:

如果 \(A[1]=num\) ,则\(A[num]=N\) (8)

以5皇后为例,一个合理布局 x=(2,5,3,1,4),满足条件(6),其旋转 90 度之后仍是该布局,所以产生该布局后不可以对其做 90 度顺时针旋转,该布局也满足条件(7),旋转 180 度后仍是该布局,不做 180 度旋转,该布局同时也满足条件(8),不做 270 度顺时针旋转。

通过上述方法实现对回溯算法的修改,可以快速地生成 N 皇后的所有解。如果一个解满足条件(6),可以做 90 度顺时针旋转,返回两个解,如果同时满足条件(6)、(7),那么可以做 90 度顺时针旋转和 180 度顺时针旋转,返回 3 个解,如果同时满足条件(6)、(7)、(8)那么可以做 90 度顺时针、180 度顺时针、270 度顺时针旋转,得到 4 个解。

N皇后求解问题的应用

对改进的的 N 皇后求解,可以通过固定前3行皇后的位置,把问题分割成多个任务,将改进的回溯算法推广成并行算法,分配到不同的计算机与 CPU 上,可以实现并行求解 N 皇后的问题。通过实现程序的标准化,可以成为检验计算机集群性能的基准。N 皇后问题的解的个数随着 N 的增加呈指数增加,从 1 到 10 皇后的解的个数为:1,0,0,2,10,4,40,92,352,724。当 N=23 时,其可行解将超过 24 万亿。因此将 N 皇后问题实现并行化可以成为检验计算机集群性能的基准。

结语

回溯算法作一种通用的问题求解的算法对求解很多问题是有效的,例如经典的三着色问题,即对一个无向图 \(G\leqslant V\) ,需对每一个顶点着 1,2,3 3 种颜色之一,使得任意两个相邻顶点颜色不同。对 n 个顶点的图,如果用穷尽法搜索,将要搜索各种可能,如果用回溯算法,则可以在最坏情况下缩减为 \(3+3^{2}+…3^{n}=3\left ( 3^{n}-1 \right )/2\) 种可能。对回溯算法修改也可以用来求解组合优化问题,即在所有的可行解中计算最优解。所以回溯算法适用于检测有限但是却大量的肯能解的组合问题。