A Polynomial-time Algorithm to Solve the Airplane Refueling Problem the Sequential Search Algorithm

2025-04-30 0 0 510.31KB 21 页 10玖币

侵权投诉

A Polynomial-time Algorithm to Solve the

Airplane Refueling Problem: the Sequential

Search Algorithm

Jinchuan Cui1* and Xiaoya Li2

1,2Academy of Mathematics and Systems Science, Chinese Academy of

Sciences, No. 55 Zhongguancun East Road, Beijing, 100190, China.

*Corresponding author(s). E-mail(s): cjc@amss.ac.cn;

Contributing authors: xyli@amss.ac.cn;

Abstract

Airplane refueling problem is a nonlinear unconstrained optimization problem

with n!feasible solutions. Given a ﬂeet of nairplanes with mid-air refueling tech-

nique, the question is to ﬁnd the best refueling policy to make the last remaining

airplane travel the farthest. In order to solve airplane refueling problem, we pro-

posed the deﬁnition of sequential feasible solution by employing the refueling

properties of data structure. We proved that if an airplane refueling instance has

feasible solutions, it must have sequential feasible solutions; and the optimal fea-

sible solution must be the optimal sequential feasible solution. So we need to

numerate all the sequential feasible solutions to get an exact algorithm. We pro-

posed the sequential search algorithm which consists of two steps, the ﬁrst step of

which aims to seek out all of the sequential feasible solutions, and the second step

aims to search for the maximal sequential feasible solution by bubble sorting all of

the sequential feasible solutions. We observed that the number of the sequential

feasible solutions will change to grow at a polynomial rate when the input size

of nis greater than an inﬂection point N. Then we proved that the sequential

search algorithm is a polynomial-time algorithm to solve the airplane refuel-

ing problem. Moreover, we built an eﬃcient computability scheme, according to

which we could forecast within a polynomial time the computational complex-

ity of the sequential search algorithm that runs on any given airplane refueling

instance. Thus we could provide a computational strategy for decision makers or

algorithm users by considering with their available computing resources.

Keywords: Airplane refueling problem (ARP), Sequential search algorithm (SSA),

Polynomial-time algorithm, Inﬂection point, Eﬃcient computability scheme

arXiv:2210.11634v7 [cs.DS] 25 Nov 2024

1 Introduction

The Airplane Refueling Problem (ARP) was raised by Woeginger [1] from a math

puzzle problem [2]. Suppose there are nairplanes referred to A1,· · · , An, each Aican

carry vitanks of fuel, and consumes citanks of fuel per kilometer for 1 ⩽i⩽n. The

ﬂeet starts to ﬂy together to a same target at a same rate without getting fuel from

outside, but each airplane can refuel to other remaining airplanes instantaneously dur-

ing the trip and then be dropped out. The goal is to determine a drop out permutation

π= (π(1),· · · , π(n)) that maximize the ﬂight distance by the last remaining airplane.

Previous research on ARP centralized on its complexity analysis and its exact

algorithm [3–6]. Related research also focused on equivalent problems of ARP such

as the n-vehicle exploration problem [7–9] and the single machine scheduling problem

[3]. V´asquez [4] studied the structural properties of ARP such as connections between

local precedence and global precedence. Iftah and Danny [5] proposed a fast and easy-

to-implement pseudo polynomial time algorithm that attained a Polynomial Time

Approximation Scheme (PTAS) for ARP. We mainly focused on the performance of

an algorithm on instances with large input size, and cared about that how long will a

given algorithm take to solve real-life instances. We tried to ﬁnd a superior algorithm

that is able to handle the large size problem in any reasonable amount of time [10], and

to explore the possibility of a fast exact algorithm which is eﬃcient on ARP instances.

Li et al. [6] put forward a fast exact algorithm for the ﬁrst time by searching for

all the feasible solutions satisﬁed with some necessary conditions. They run the algo-

rithm on some large scale of ARP instances and got relatively eﬃcient results than

previous algorithms. However, the authors did not investigate the theoretical compu-

tational complexity the fast exact algorithm will perform on worst case, and did not

demonstrate that how fast and to what degree will the fast algorithm be when per-

form it on larger scale of ARP instances. Is it an exponential-time algorithm, or is it

probably a polynomial-time algorithm? In this paper, we proposed the deﬁnition of

the sequential feasible solution at ﬁrst, and then we put forward the sequential search

algorithm (SSA) by bubble sorting all of the sequential feasible solutions. The compu-

tational complexity of SSA depends on the number of sequential feasible solutions for

any given ARP instance. Then we found that SSA has a characteristic that it will run

in polynomial time on ARP instances when the input size is greater than an inﬂec-

tion point. According to the theoretical analysis on the algorithmic upper bound, we

explained why there exists an inﬂection point for the algorithmic complexity. More-

over, we proved that the time complexity of SSA raises at a polynomial rate when the

input size of nis greater than an inﬂection point N.

At last we also proposed an eﬃcient computability scheme to predict the sequen-

tial search algorithmic complexity for any given ARP instance. The idea of eﬃcient

computability is inspired by the following literature. In [8], the authors provided a

conceptual mechanism of eﬃcient computation on the n-vehicle exploration problem,

which could acquire reasonable computing cost analysis to help decision makers choose

corresponding algorithm. In book [11], the authors mentioned that it is possible to

quantify some precise senses in which an instance may be easier than the worst case,

and to take advantage of these situations when they occur. They also pointed out that

some ”size” parameters has an enormous eﬀect on the running time because an input

with ”special structure” can help us avoid many of the diﬃculties that can make the

worst case intractable. In [12], the authors provided a worst-case explanation for the

phenomenon that why some real-life maximum clique instances are not intractable.

They claimed that real-life instances of maximum clique problem often have a small

clique-core gap, however real hard instances are still hard no matter the input size is

large or small.

2 Preliminary

We consider a permutation order πand its related sequence Aπ(1) ⇒Aπ(2) ⇒ · · · ⇒

Aπ(n)(see ﬁg. 1), where Aπ(i)refuels to Aπ(j)for any i<j. Let Sπ=

i=1

xπ(i)denotes

the total distance that the nairplanes can approach, and xπ(i)denotes the segmented

part of distances that Aπ(i)travels farther than Aπ(i−1), which is also the ﬂight dis-

tance that Aπ(i)contributes to Sπseparately. Then ARP is described as a scheduling

problem, which aims to ﬁnd a drop out permutation π= (π(1), π(2),· · · , π(n)) that

maximizes the following Sπ. Since each Sπcorresponds to a permutation order of n

airplanes, there are totally n! of feasible solutions need to be compared.

Sπ=vπ(1)

cπ(1) · · · +cπ(n)

+· · · +vπ(n)

cπ(n)

(1)

δε

;

δε

;

δε ;

δQε

δε

δQε

δQε

Fig. 1 Airplane refueling problem scheme.

Let Crepresents the cumulative sum of fuel consumption rates in an order π=

(π(1), π(2),· · · , π(n)), then Cπ(n)= 0, and Cπ(l)=

t=l+1

cπ(t)for any l < n.

3 Overall strategy

We would like to give the deﬁnition of polynomial-time algorithm [13] before we

proposed our algorithm.

Deﬁnition 1. Apolynomial-time algorithm is deﬁned to be an algorithm whose

time complexity function is O(p(n)) for some polynomial function p(n)for all values

of n⩾0.

In Deﬁnition 1, the condition of n⩾0 means that a polynomial-time algorithm is

polynomial in time no matter the problem’s input size is large or small. Normally, an

algorithm runs in exponential time on small size of instances, it should be exponential-

time on larger input size of instances. Thus, in studying the complexity of an algorithm,

instances with larger inputs are of more priorities than other kinds because the larger

inputs determine the applicability of the algorithm [14].

Here, we mainly focused on seeking for a polynomial-time algorithm to solve ARP.

We proposed SSA by numerating all of the sequential feasible solutions. The complex-

ity of SSA depends on the number of sequential feasible solutions to the given ARP

instance. We proved that for worst case of ARP instances, the number of its sequential

feasible solutions is upper bounded by 2n−2. Then we focused on the following two

major challenges. The ﬁrst one is that will the running time of SSA decline down to

polynomial-time when the input size of ngets to be suﬃciently large? The other chal-

lenge is that how can we predict the speciﬁc computational complexity of any given

ARP instance in polynomial time before running SSA on it?

The answer to the ﬁrst question is positive. For any ARP instance, if each airplane’s

single ﬂight distance is limited in an interval [L, S], then there must exist an constant

Nsuch that SSA runs in polynomial time when the inputs size of nis greater than an

inﬂection point Nwhich does not depend on n. So we proved that SSA is a polynomial-

time algorithm to solve ARP when its input size of nis greater than an inﬂection

point N.

Deﬁnition 2. When we run an algorithm on a problem, at ﬁrst the time complexity

grows in exponential time when the input size is small. But the time complexity of the

algorithm will changes to grow in polynomial time when the input size is greater than

N. For such situation, the point Nis deﬁned as an inﬂection point.

Besides, when nis less than N, the number of sequential feasible solution is upper

bounded by 2n−2, which is still less than nmfor m=N/2. Therefore we proved that

SSA is a polynomial-time algorithm to solve ARP.

The key point to answer the second question is to predict the inﬂection point

Nfor any given ARP instance in polynomial time. We proposed an algorithm to

estimate the Nfor worst case, and we improved the algorithm for general case by

using heuristic method to attain the computational complexity in the design of the

eﬃcient computability scheme.

In section 4, we proposed the deﬁnition of sequential feasible solution, and con-

structed SSA by bubble sorting all of the sequential feasible solutions. We sharpened

the upper bound of the number of sequential feasible solutions to 2n−2. In section 5,

by exploring the computational complexity of ARP instances from a dynamic perspec-

tive, we found that the computational complexity of SSA grows at a slowing down

rate when the input size of ngets to be greater than an inﬂection point. In section 6,

our eﬀorts were devoted to construct the eﬃcient computability scheme. We proposed

a heuristic algorithm to estimate an inﬂection point N= 2mfor general case of ARP

instances. Then we explained how to use the eﬃcient computability scheme to predict

computational complexity before we choose a proper algorithm for any given ARP

instance.

4 Sequential feasible solutions and the complexity

upper bound

4.1 Deﬁnition of sequential feasible solution

A special case of n-vehicle exploration problem [7] is extended to ARP as follows.

Theorem 1. In an ARP instance, if

⩽v2

⩽· · · ⩽vn−1

n−1

⩽vn

and v1

⩽v2

⩽· · · ⩽vn−1

cn−1

⩽vn

then the optimal sequence is A1⇒A2⇒ · · · ⇒ An.

For general case of ARP instances, we randomly choose two neighbored airplanes

Ai−1and Aiin π= (1,· · · , n).

Suppose Ci=

t=i+1

cπ(t).

If Ai−1⇒Ai, then

xπ(i−1) +xπ(i)=vi−1

ci−1+ci+Ci

+vi

ci+Ci

otherwise if Ai⇒Ai−1, then

xπ(i)+xπ(i−1) =vi

ci+ci−1+Ci

+vi−1

ci−1+Ci

Consequently, if vi

ci×(ci+Ci)>vi−1

ci−1×(ci−1+Ci), then Ai−1⇒Aiis a better sequence;

otherwise if vi

ci×(ci+Ci)⩽vi−1

ci−1×(ci−1+Ci), then Ai⇒Ai−1is a better sequence.

Deﬁnition 3. Given current cumulative sum of fuel consumption rates Co, the

relative distance factor of Aiis deﬁned as φ(Ai,Co) = vi

ci×(ci+Co).

The following Corollary 1is a corollary of Theorem 1by considering the deﬁnition

of relative distance factor.

Corollary 1. For an ARP instance with a given cumulative sum of fuel consumption

rates Co, if v1

⩽v2

⩽· · · ⩽vn−1

cn−1

⩽vn

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

10 玖币 0人已下载

立即下载

摘要：

APolynomial-timeAlgorithmtoSolvetheAirplaneRefuelingProblem:theSequentialSearchAlgorithmJinchuanCui1*andXiaoyaLi21,2AcademyofMathematicsandSystemsScience,ChineseAcademyofSciences,No.55ZhongguancunEastRoad,Beijing,100190,China.*Correspondingauthor(s).E-mail(s):cjc@amss.ac.cn;Contributingauthors:xyli@...

展开>> 收起<<

A Polynomial-time Algorithm to Solve the Airplane Refueling Problem the Sequential Search Algorithm.pdf

共21页,预览5页

还剩页未读，继续阅读

声明：本站为文档C2C交易模式，即用户上传的文档直接被用户下载，本站只是中间服务平台，本站所有文档下载所得的收益归上传人(含作者)所有。玖贝云文库仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私，请立即通知玖贝云文库，我们立即给予删除！

A Polynomial-time Algorithm to Solve the Airplane Refueling Problem the Sequential Search Algorithm

相关推荐

开通VIP享超值会员特权

作者详情

相关内容

热门标签

举报选择: