Chinese Postman Problem is an unsettled graphic problem. It was approached seldom by evolutionary computation. Now we use genetic algorithm to solve Chinese Postman Problem in undirected graph and get good results. It...Chinese Postman Problem is an unsettled graphic problem. It was approached seldom by evolutionary computation. Now we use genetic algorithm to solve Chinese Postman Problem in undirected graph and get good results. It could be extended to solve Chinese postman problem in directed graph. We make these efforts for exploring in optimizing the mixed Chinese postman problem.展开更多
In this paper,we address the k-Chinese postman problem under interdiction budget constraints(the k-CPIBC problem,for short),which is a further generalization of the k-Chinese postman problem and has many practical app...In this paper,we address the k-Chinese postman problem under interdiction budget constraints(the k-CPIBC problem,for short),which is a further generalization of the k-Chinese postman problem and has many practical applications in real life.Specifically,given a weighted graph G=(V,E;w,c;v_(1))equipped with a weight function w:E→R^(+)that satisfies the triangle inequality,an interdiction cost function c:E→Z^(+),a fixed depot v_(1)∈V,an integer k∈^Z^(+)and a budget B∈N,we are asked to find a subset S_(K)■E such that c(S_(K))=∑_(e∈S_(k)c_(e))≤B and that the subgraph G\S_(k)is connected,the objective is to minimize the value min_(C_(E)\S_(k))max{w(C_(i))|C_(i)∈C_(E)\S_(K)}among such all aforementioned subsets S_(k),where C_(E)S_(k)is a set of k-tours(of G\S_(k))starting and ending at the depot v_(1),jointly traversing each edge in G\S_(k)at least once,and w(C_(i))=∑e∈C_(i)w(e)for each tour C_(i)∈C_(E)\S_(k).We obtain the following main results:(1)Given an-approximation algorithm to solve the minimization knapsack problem,we design an(α+β)-approximation algorithm to solve the k-CPIBC problem,whereβ=7/2-1/k-[1/k].(2)We present aβ-approximation algorithm to solve the special version of the k-CPIBC problem,where c(e)1 for each edge e in G and is defined in(1).展开更多
If we restrict the postman to traversing each edge at most twice in the windypostman problem (WPP), we will get a new problem: 2WPP. An approximation algorithmhas been posed by M. Guan for the WPP. In the present pape...If we restrict the postman to traversing each edge at most twice in the windypostman problem (WPP), we will get a new problem: 2WPP. An approximation algorithmhas been posed by M. Guan for the WPP. In the present paper, we improve the estimatederror given by M. Guan and show that we can estimate the error for the 2WPP by findinga minimum cost circulation. We also pose a new sufficient condition for the equivalencebetween WPP and 2WPP, which can be checked in polynomial time steps.展开更多
接口或API测试是日常软件测试过程中常见内容之一,接口测试工具可选性很多,文章主要针对常用的三个接口测试工具:SoapUI、JMeter、Postman,分析它们之间的不同之处以及在实际工作中的应用。具体而言,使用不同的工具来解决日常软件测试...接口或API测试是日常软件测试过程中常见内容之一,接口测试工具可选性很多,文章主要针对常用的三个接口测试工具:SoapUI、JMeter、Postman,分析它们之间的不同之处以及在实际工作中的应用。具体而言,使用不同的工具来解决日常软件测试中的不同接口类型的接口测试问题、性能测试问题、工作效率问题。在运营商运营支撑系统(Operation Support Systems,OSS)领域实际项目测试过程中,有的放矢地选择测试工具,不仅能有效提高了软件质量,同时有助于提高测试人员的效率。展开更多
基金Supported by the National Natural Science Foundation of China(60133010,70071042)
文摘Chinese Postman Problem is an unsettled graphic problem. It was approached seldom by evolutionary computation. Now we use genetic algorithm to solve Chinese Postman Problem in undirected graph and get good results. It could be extended to solve Chinese postman problem in directed graph. We make these efforts for exploring in optimizing the mixed Chinese postman problem.
基金supported by the National Natural Science Foundation of China(Nos.11861075,12101593)Project for Innovation Team(Cultivation)of Yunnan Province(No.202005AE-160006)+2 种基金Peng-Xiang Pan is also supported by Project of Yunnan Provincial Department of Education Science Research Fund(No.2020Y0040)Jun-Ran Lichen is also supported by Fundamental Research Funds for the Central Universities(No.buctrc202219)Jian-Ping Li is also supported by Project of Yunling Scholars Training of Yunnan Province(No.K264202011820).
文摘In this paper,we address the k-Chinese postman problem under interdiction budget constraints(the k-CPIBC problem,for short),which is a further generalization of the k-Chinese postman problem and has many practical applications in real life.Specifically,given a weighted graph G=(V,E;w,c;v_(1))equipped with a weight function w:E→R^(+)that satisfies the triangle inequality,an interdiction cost function c:E→Z^(+),a fixed depot v_(1)∈V,an integer k∈^Z^(+)and a budget B∈N,we are asked to find a subset S_(K)■E such that c(S_(K))=∑_(e∈S_(k)c_(e))≤B and that the subgraph G\S_(k)is connected,the objective is to minimize the value min_(C_(E)\S_(k))max{w(C_(i))|C_(i)∈C_(E)\S_(K)}among such all aforementioned subsets S_(k),where C_(E)S_(k)is a set of k-tours(of G\S_(k))starting and ending at the depot v_(1),jointly traversing each edge in G\S_(k)at least once,and w(C_(i))=∑e∈C_(i)w(e)for each tour C_(i)∈C_(E)\S_(k).We obtain the following main results:(1)Given an-approximation algorithm to solve the minimization knapsack problem,we design an(α+β)-approximation algorithm to solve the k-CPIBC problem,whereβ=7/2-1/k-[1/k].(2)We present aβ-approximation algorithm to solve the special version of the k-CPIBC problem,where c(e)1 for each edge e in G and is defined in(1).
文摘If we restrict the postman to traversing each edge at most twice in the windypostman problem (WPP), we will get a new problem: 2WPP. An approximation algorithmhas been posed by M. Guan for the WPP. In the present paper, we improve the estimatederror given by M. Guan and show that we can estimate the error for the 2WPP by findinga minimum cost circulation. We also pose a new sufficient condition for the equivalencebetween WPP and 2WPP, which can be checked in polynomial time steps.
文摘接口或API测试是日常软件测试过程中常见内容之一,接口测试工具可选性很多,文章主要针对常用的三个接口测试工具:SoapUI、JMeter、Postman,分析它们之间的不同之处以及在实际工作中的应用。具体而言,使用不同的工具来解决日常软件测试中的不同接口类型的接口测试问题、性能测试问题、工作效率问题。在运营商运营支撑系统(Operation Support Systems,OSS)领域实际项目测试过程中,有的放矢地选择测试工具,不仅能有效提高了软件质量,同时有助于提高测试人员的效率。
