这是一篇澳洲的python算法代码代写

First, a formal statement of the base station load balancing problem:

**Input: **A set *B *of base stations with a location *x**b **∈ *R2 given for each station *b **∈ **B*, and a set *P *of mobile computers with a location *y**p **∈ *R2 and effffective transmission radius *r**p **∈ *[0*, **∞*) given for each *p **∈ **P*.

**Goal: **Find a computer–station assignment *g *: *P **→ **B *of computers to base stations, such that

*p*is within range*r**p*of the base station*g*(*p*) that it is assigned to; and

is minimized.

Sometimes to solve a given problem, it helps to solve a difffferent, related problem fifirst. The above problem is an *optimization problem *– we are trying to minimize the maximum load *L**g *over all admissible choices of assignment *g*. Rather than solving this problem directly, we will instead start by considering a related *decision problem*: given a set of base stations, a set of computers, and a desired max load *L **∈ *N, does there exist an assignment *g *such that the load on each station is at most *L*?

**Reduction to Max Flow **

We reduce the decision version of the base station load balancing problem to the problem of determining whether a flflow network has a valid flflow with value at least as high as a specifified number *K*.

Each of the following sections refers to an arbitrary instance of the base station load balancing problem given by a set *B *of base stations, a set *P *of mobile computers, and a desired max load *L*.

**Description of reduction: **Construct a flflow network *G *= (*V, E*) with capacity function *c *as follows:

*s*and a sink vertex*t*to*V*.*p**∈**P*, add a vertex*u**p*to*V*and an edge (*s, u**p*) to*E*, and set*c*(*s, u**p*) = 1.*b**∈**B*, add a vertex*v**b*to*V*and an edge (*v**b**, t*) to*E*, and set*c*(*v**b**, t*) =*L.**p, b*)*∈**P**×**B*, if*k**y**p**−**x**b**k ≤**r**p*, then add an edge (*u**p**, v**b*) to*E*, and

set *c*(*u**p**, v**b*) = *∞*.

Finally, set the desired flflow value to *K *= *|**P**|*.

**Proof of correctness: **Assume that the max flflow instance outputted by our reduction is given by flflow network *G *= (*V, E*) with source *s *and sink *t*, capacity function *c*, and desired flflow value *K*.

We prove that the original base station load balancing instance admits a valid computer–station assignment with max load at most *L*, if and only if the max flflow instance outputted by our reduction admits a flow with value equal to *K*.

(a) ”*⇐ *”: assume that the output flflow network admits a flflow *f *with value *K*. *K *is the maximum possible flow value since

*K *= *|**P**| *= *c*(*{**s**}**, V **\ {**s**}*)*, *

i.e. *K *is the capacity of the source cut, so by flflow integrality we can assume that all flflow values assigned to edges by *f *are integers. We can deduce that *f**out*(*u**p*) = *f**in*(*u**p*) = 1 for each computer *p **∈ **P *from the fact that the cut (*{**s**}**, V **\ {**s**}*) is saturated and from flflow conservation.

To defifine a computer–station assignment *g *: *P **→ **B*, for each *p **∈ **P*, we use flflow integrality and the fact that *f**out*(*u**p*) = 1 to observe that exactly one edge of the form (*u**p**, v**b*)*, *for some *b **∈ **B*, has a flow value of 1. Using this fact, if *f*(*u**p**, v**b*) = 1 then we set *g*(*p*) = *b. *The existence of the edge (*u**p**, v**b*) in *G *ensures that *k **y**p **− **x**b**k ≤ **r**p*, so this assignment is valid.

It remains to see that the load placed on each base station *b **∈ **B *by *g *is at most *L*. To see this, observe that each computer *p *with *g*(*p*) = *b *has *f*(*u**p**, v**b*) = 1, and that the total of such contributions is given by

*f**in*(*v**b*) = *f**out*(*v**b*) *≤ **c*(*v**b**, t*) = *L. *

It follows that the max load assigned by *g *to any station is at most *L*.

(b) ”*⇒*”: assume that there is a valid computer–station assignment *g *for the base station load balancing instance with max load at most *L*. Defifine a flflow *f *on the max flflow instance as follows:

- Set
*f*(*s, u**p*) = 1 for each computer*p**∈**P*; - For each computer–station pair (
*p, b*)*∈**P**×**B*for which (*u**p**, v**b*) is an edge, set*f*(*u**p**, v**b*) = 1 if*g*(*p*) =*b*, and*f*(*u**p**, v**b*) = 0 otherwise.

- Set
*f*(*v**b**, t*) =*f**in*(*v**b*) for each base station*b**∈**B*. (Having followed the previous step,*f**in*(*v**b*) is well-defifined.)

It can be seen by inspection of the reduction that the above steps assign a flflow value to each edge in *G*.

Clearly *f *saturates the source cut, so *v*(*f*) = *c*(*{**s**}**, V **\ {**s**}*) = *|**P**| *= *K. *

To establish that *f *is a valid flflow, we nee d to check the flflow constraints.

(i) *f*(*e*) *≤ **c*(*e*) *for every edge **e **∈ **E**: *clear for edges of the form (*s, u**p*) since they are all assigned flow equal to their capacity; and a non-issue for edges of the form (*u**p**, v**b*) since all of these edges have infifinite capacity.

It remains to check edges of the form (*v**b**, t*) for each station *b **∈ **B*. For such an edge, the capacity is *L*, and the flflow assigned is *f**in*(*v**b*), which is constituted of contributions of 1 from each edge of form (*u**p**, v**b*) such that *g*(*p*) = *b*. The amount of computers *p *such that *g*(*p*) = *b *is the defifinition of the load placed on *b *by *g*, which by assumption can’t be greater than *L*. It follows that *f*(*v**b**, t*) = *f**in*(*v**b*) *≤ **L *= *c*(*v**b**, t*) as required.

(ii) *f**in*(*u*) = *f**out*(*u*) *for every **u **∈ **V **(excluding **s **and **t**): *for vertices of the form *v**b *for some base

station *b **∈ **B*, this follows immediately from the defifinition of *f*.

For each vertex of the form *u**p *for some computer *p **∈ **P*, *f**in*(*u**p*) = 1. The edge (*u**p**, v**g*(*p*)) is guaranteed to exist in *G *since *k **y**p**−**x**g*(*p*)*k ≤ **r**p *must be satisfified for *g *to be valid, and *f*(*u**p**, v**b*) = 1 exactly when *g*(*p*) = *b*, so *f**out*(*u**p*) = 1 also.

It follows that *f *is a valid flflow of value *K *as required.

**Time complexity analysis: **If *|**B**| *= *m *and *|**P**| *= *n*, then constructing an adjacency list representation of *G *takes Θ(*mn*) time, since

*G*takes constant time;*u**p*and an edge the form (*s, u**p*) with capacity 1 for each*p**∈**P*takes Θ(*n*) time;*v**b*and edge (*v**b**, t*) with capacity*L*for each*b**∈**B*takes Θ(*m*) time;*u**p**, v**b*) with infifinite capacity where applicable for each (*p, b*)*∈**P**×**B*

takes Θ(*|**P **× **B**|*) = Θ(*nm*) time, assuming we iterate over every pair in *P **× **B. *In the worst case all such edges may be required, so we can’t beat Ω(*nm*) here. (Here we make the assumption that the arithmetic required to check whether *k **y**p **− **x**b**k ≤ **r**p *takes constant time.)

The last of these steps dominates, for a total running time of Θ(*mn*).

The the resulting flflow network consists of *|**P**| *+ *|**B**| *+ 2 = *n *+ *m *+ 2 *∈ *Θ(*m *+ *n*) vertices and *|**P**| *+ *|**B**| *+ *|**P **× **B**| *= *n *+ *m *+ *nm **∈ *Θ(*mn*) edges in the worst case.

As the flflow network has a max flflow of *≤ **C *:= *c*(*{**s**}**, V **\ {**s**}*) = *|**P**| *= *n, *the Ford-Fulkerson algorithm using *any *reasonable (i.e. linear-time) augmenting path selection strategy would solve our max flflow instance within *O*(*|**E**|**C*) = *O*(*mn **· **n*) = *O*(*mn*2 ) time.

**Solving the optimization problem **

Our original aim was to minimize the maximum load *L**g *over all possible choices of computer–station assignment *g*. Having solved the *decision problem *of determining whether a computer–station assignment keeping the max load within some parameter *L *is possible, we can now solve the *optimization problem *of determining the minimum such *L*, by using a *binary search *over possible *L *values.

In more detail, we could imagine an array *A*, which, for each index *L*, stores at *A*[*L*] a 0 if it’s impossible to validly balance all the computers in *P *across the stations in *B *so that the max load is at most *L*, or a 1

if it is possible. Then *A *looks something like the following:

*A *= [0*, *0*, *0*, . . . , *0*, *0*,*0*, *1*, *1*, *1*, . . . , *1*, *1]

*↑ *fifirst entry for which it’s possible

*A *is clearly a sorted list, so we could binary-search it for the fifirst index *L *such that *A*[*L*] = 1, i.e. the lowest *L *such that there is a computer–station assignment with max load within *L*.

This search doesn’t require *A *to actually exist in memory – whenever our search needs to know *A*[*L*] for some *L*, we can just carry out the reduction for the decision problem with *L *plugged in, and solve the resulting flflow network – although that means that each ”index lookup” will take *O*(*mn*2 ) time. *L *= *n *is an obvious largest max load that must work if a valid computer–station assignment is possible at all, so this search process takes *O*(*mn*2 log *n*) time in total.