检索结果-南通市图书馆

作者：孔七威南京财经大学

学位级别：硕士

当前,人工智能发展迅速,但是人工智能如何实现因果推理一直备受关注,线性规划理论是人工智能的基础优化理论,对线性规划的突破和创新即是对人工智能理论的创新。线性规划是否存在强多项式算法是跨世纪的国际数学难题,该问题的突破将为... 详细信息

当前,人工智能发展迅速,但是人工智能如何实现因果推理一直备受关注,线性规划理论是人工智能的基础优化理论,对线性规划的突破和创新即是对人工智能理论的创新。线性规划是否存在强多项式算法是跨世纪的国际数学难题,该问题的突破将为人工智能的发展化解一个重大的理论难点。为了给这一问题的突破提供思路,本文基于棱锥切割理论阐述并完善了三种求解技巧:(1)、拔高加速方法;(2)、在单纯形法的特定情况下比传统列消去定理更方便有效的列消去算法;(3)、可行点向可行域中心平移后再下降的水平退化算法。这三种技巧互相效力,可望为建立线性规划强多项式时间算法添砖加瓦,三种技巧结合的优化方法为线性规划提供了一种新的思路,或许能把单纯形法解决大规模线性规划问题变为一种不那么复杂的计算,并为提供解决著名的Klee-Minty反例问题提供一些启发性思路。基于线性规划和模糊数学,1982年,国内学者提出因素空间理论,该理论认为,在决策过程中出现的智能行为可以被看作是一个由主体观察和控制的动态状态,假定在因素空间中存在运动的一点y,若可行区域被一组超平面切割,当点y到达可行域的边界时,超平面将阻止其移动,这时运动主体需要调整移动方向,以便尽可能按预期趋近目标。由于一些情况下可行域边界不能用可微函数表示,常用的梯度法不能用来描述这样的调整过程。因此,基于因素空间,本文补充完善一种新的模型:线性调整规划方法(Linear adjustment programming,LAP)。LAP类似于一种松弛线性规划(Linear programming,LP),此文的LAP和LP的区别在于:LP方法的目标是寻找最终的最优点,而LAP更关注于在短期内做一个直接的动作,LAP关注遇到阻碍面时如何再次调整方向。在规划问题过程中,如果用LP无法找到最优解,那可以通过LAP算法进行一次调整,通常,现实中的情况多是LP无法快速找到最优解。在本文的算法模型中,用目标方向g在子空间中的投影取代传统的梯度向量,投影在线性调整规划中起着核心作用,如果一个超平面阻碍点y沿着方向d前进。那么我们需要根据g在阻碍平面中的投影,调整新的方向;如果一次只有一个阻碍面,计算投影会很直观,但当同时遇到多个阻碍时,如何计算投影呢?针对这一问题,本文采用一种命名为Hat矩阵的矩阵方法进行投影计算。LAP可以给经济结构调整、金融预测和资源分配等方面的研究者提供一些借鉴思路。

关键词：线性规划强多项式时间算法因素空间人工智能投影计算

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

单位无穷范数下边权有界的最小支撑树逆最优值问题

引用

运筹学学报 2022年第3期26卷 44-56页

作者：张斌武关秀翠河海大学理学院江苏南京210098 东南大学数学学院江苏南京210096

研究了单位l范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络G=(V,E,w),支撑树T^(0),下界向量l,上界向量u及数值K,寻求一个新的边权向量w满足上下界约束l≤w≤u,且T^(0)是在向量w下权值为K的一个最小支撑树,目标... 详细信息

研究了单位l范数下边权有界的最小支撑树逆最优值问题。给定一个边赋权无向连通网络G=(V,E,w),支撑树T^(0),下界向量l,上界向量u及数值K,寻求一个新的边权向量w满足上下界约束l≤w≤u,且T^(0)是在向量w下权值为K的一个最小支撑树,目标是在单位l范数下使得修改成本‖w-w‖最小。本文给出了该问题的数学模型,分析了其最优性条件,设计了求解该问题的时间复杂度为O(|V||E|)的强多项式时间算法。

关键词：最小支撑树 l_(∞)范数逆最优值问题强多项式时间算法

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

带约束的赋权哈明距离下最小流逆问题的若干研究

带约束的赋权哈明距离下最小流逆问题的若干研究

引用

作者：林伟丰厦门大学

学位级别：硕士

在一个组合优化逆问题中,在当前的参数下给定一个可行非最优的解,我们的目的是尽可能小地修改当前的参数使得给定的可行解最优.修改参数的成本可以用例如赋权l1范数,赋权l2范数,赋权l∞范数以及赋权哈明距离等等不同的范数进行测量.在... 详细信息

在一个组合优化逆问题中,在当前的参数下给定一个可行非最优的解,我们的目的是尽可能小地修改当前的参数使得给定的可行解最优.修改参数的成本可以用例如赋权l1范数,赋权l2范数,赋权l∞范数以及赋权哈明距离等等不同的范数进行测量.在这篇文章中,我们关注带约束的赋权哈明距离下最小流逆问题.针对一般情况下有界的赋权瓶颈型哈明距离最小流逆问题,通过构造剩余网络N’(V,A’,u’,s,t)并将其修改为赋权网络N"(V,A",w,s,t),找到时间复杂性为O(m+nkign)的强多项式时间算法1;针对带总和约束的赋权瓶颈型哈明距离下最小流逆问题,***等人[20]提出的算法2结果作为上界,算法1得出的结果作为下界,通过用二分法,找到时间复杂性为O(nmlogm)的强多项式算法3,并分三种情况证明了该算法的有效性;针对带瓶颈约束的赋权总和型哈明距离下最小流逆问题,找到强多项式时间算法4求解该问题,时间复杂性为O(nm).

关键词：最小流问题最优化逆问题赋权哈明距离强多项式时间算法

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

瓶颈型范数下最小-最大生成树部分反问题的研究

瓶颈型范数下最小-最大生成树部分反问题的研究

引用

作者：董庆珍兰州大学

学位级别：硕士

最小-最大生成树问题是一个经典的组合优化问题,其目的是在给定的边权图中找到一棵生成树使它的最大边权最小.给定一个连通图G,边权函数w,以及G的一个森林F,最小-最大生成树部分反问题的目标是找到一个新的权重函数w*,使得G中存在关于w... 详细信息

最小-最大生成树问题是一个经典的组合优化问题,其目的是在给定的边权图中找到一棵生成树使它的最大边权最小.给定一个连通图G,边权函数w,以及G的一个森林F,最小-最大生成树部分反问题的目标是找到一个新的权重函数w*,使得G中存在关于w*的包含F的一棵最小-最大生成树T;并要求w和w*之间的差距最小.在本文中我们分别针对赋权瓶颈型汉明距离和l-范数这两种瓶颈型范数研究了最小-最大生成树部分反问题.对于赋权瓶颈型汉明距离,我们首先研究最优树取值有限制的最小-最大生成树部分反问题,证明了该问题是强多项式时间可解的.然后,通过给出最优树取值的多项式规模的备选集,我们设计了求解最小-最大生成树部分反问题的时间复杂度为O（mlog m）的算法,其中m为图G中边的条数.同时,我们将上述算法推广到有容量限制的对应问题上.随后,通过给出更简单的判定最小-最大生成树部分反问题可行解的充分必要条件,我们设计了更加高效的求解算法,时间复杂度为O（mlogm）.此外,我们也证明了该算法可以推广到有容量限制的情形.对于l-范数,本文首先考虑了一种特殊情形——单位无穷范数下最小-最大生成树部分反问题,通过发现该问题最优值和最优解的特性,设计了求解问题的线性时间算法.进一步,本文分别研究了单位无穷范数下有容量限制的最小-最大生成树部分反问题和无穷范数下最小-最大生成树部分反问题的判定形式,并得到了求解这两个判定形式的充分必要条件.

关键词：部分反问题最小-最大生成树赋权瓶颈型汉明距离 l_∞-范数强多项式时间算法

来源：

同方学位论文库评论