Computer Complexity of a real case scenario: facility location

[quatrosem]

There is a problem of facility location that I solve with genetic algorithms.

I can get good results. So I would like to compare my genetic algorithm complexity O(n^2) with the brute force algorithm. But I am not getting an answer.

(n = number of individuals in my population, usually 200.)
See the picture attached. Ignore the gray and pink squares. I want to know the complexity to find all the solutions for the problem. The problem is how I can connect the blue circle to the black squares.

In the picture, you can see one possible combination.

But in the worse scenario I see a O(k!), where k is the number of available places (20x20 in this case = 400).

If that is correct, in the worst scenario this would take 400! to be computed.

How I did it? I considered that for the first k places in the scenario I would have k-1 available places, and so on. In the worst case, I would have:

k.(k-1).(k-2).(k-3),...,1 possibilities
Is that correct?

image: http://i.stack.imgur.com/SaPBm.jpg

[rproffitt]

Crossposted it seems. http://stackoverflow.com/questions/37689654/computer-complexity-of-a-real-case-scenario-facility-location

[Gribouillis]

I don't understand the rules. Also there are 2 blue circles in the picture. How are the legal paths defined ?

[quatrosem]

Ruler: you can go from one square to any other.
You can use all the 400 squares or less than 400. So the question is, how many routes can you do. In my opinion, if you have one blue dot and want to pass through all the squares, them it would be 400!.

ok. but it is possible to do it with aldo n-1 squares... them it would be n! + (n-1)! ?
if that is true... the complexity should be SUM (n-i)! <i=0..400> ???

I do not know.

The second blue square you can ignore, please.

and I posted in the stake first ... as I did not get an answer, I posted here.
Is that a problem? Sorry, I do not know if it is a problem.

[rproffitt]

@q
I see replies at your other discussion. Some folk only want "answers." They often flame out later. Stick to it?

[Gribouillis]

You must choose the intermediary squares between the blue dot and a black square. It means that you are counting the number of one-to-one sequences of the n = 398 remaining squares. There are
n! \sum_{k=0}^{n} \frac{1}{k!}
such sequences. See this reference for example Click Here.

When n is large, this is approximately e \times n!

[quatrosem]

Yes Gribouillis!!! I just read your article. I believe that is right. Really good.
So imagine that I have now more than one square.
Then my n = (total squares - blue dots -black square).
And, if n is large, my formula would be: e \times n! \times number_blue_dots.

Do you think this is correct?

[quatrosem]

I am very happy with your explanation Gribouillis ....
I am just trying to explore even more the answere and learn a bit ... I think this is why discussions are so good.

So, I am reading again your post ... If the formula says:
"The number of arrangements of any subset of n distinct objects"

If n=398, then we are also counting the groups with 300 squares... also the group with 20 squares and so on.
And that is correct, that is exactly what I want.

That wouldn´t be: \sum_{k=0}^{n} (n-k)! ?

Because if yes... it means that: e \times n! = \sum_{k=0}^{n} (n-k)!

[Gribouillis]

No, the formula is this one Click Here. It is not an equality, it is an equivalent when n is large.