Member Avatar for 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

  • 3 Contributors
  • 8 Replies
  • 499 Views
  • 21 Hours Discussion Span
  • Latest Post Latest Post by Gribouillis

Dani AI

Generated

There’s a notation mix-up that causes much of the confusion: used n earlier for GA population size, then re-used n for grid squares. Use distinct symbols: let M = total squares (400), B = number of blue start points, T = number of black target points, and N = M − B − T (available intermediates). With that clear, the combinatorics become straightforward.

With a fixed start and a fixed end, every route is an ordered selection of 0..N distinct intermediate squares. Counting those ordered selections gives an astronomically large total (as explained qualitatively). Special cases worth noting: if a route must visit every square exactly once and the start is fixed, the count is (M−1)!, not M!. If both start and end are fixed it is (M−2)!. If neither endpoint is fixed then full permutations are M!. These reductions come from fixing positions in a permutation and are the root of why the raw “400!” intuition overcounts when a start is specified.

If multiple starts or targets are allowed and each start→target pair is considered distinct, then multiply the per-pair count by B×T. Care is required: if the question is “how many distinct ordered sequences of squares exist regardless of which square is labelled start,” do not multiply—that would double‑count identical sequences viewed from different starting labels.

Practical takeaway: factorial growth quickly becomes impossible to enumerate (12! ≈ 4.8×10^8, 15! ≈ 1.3×10^12, 20! ≈ 2.4×10^18; 400! is on the order of 10^869). Exact enumeration is only feasible for very small M. For TSP‑style or facility‑location variants consider exact DP algorithms (exponential but much smaller than n!) for small n, and use GAs or other heuristics for large grids. To compare the GA meaningfully to “brute force,” measure GA runtime and solution quality on small instances where exact answers are computable, and report how solution quality scales rather than trying to run full enumeration for M=400.

Recommended Answers

All 8 Replies

Member Avatar for Gribouillis

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

Member Avatar for 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.

Member Avatar for rproffitt

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

Member Avatar for 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!

Edited by Gribouillis
Member Avatar for 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?

Member Avatar for 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)!

Member Avatar for Gribouillis

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

commented: that is it! thanks... question answered! +0
Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.