Algorithm for optimal teritorial coverage

ivanatora · 04-09-2007, 08:27 AM

Hi there!
I have the following task: a country teritory is given as a matrix of 0 and 1. I must place military bases across the country - every base cover the neighbour teritory as well. All bases must be optimal placed - in other words I have to cover the whole teritory with minimum amount of bases.
To make things look clear I will apply the following example: Lets take this as input data:

Code:

0 0 0 0 1 0
0 0 0 1 1 1 
0 0 1 1 1 0 
1 1 1 1 1 0 
0 0 0 1 1 1

There is a 1 for teritory needed coverage, and 0 for teritory that doesn't need coverage (out of the country, enemy teritory, etc).
If we take the minus sign (-) as a military base, and the 'X' sign for covered teritory, this is what would we have after placing one base:

Code:

0 0 0 0 1 0 
0 0 0 1 1 1 
0 0 X X X 0 
1 1 X - X 0 
0 0 0 X X 1

The target is to make Xs from all 1s with minimum amount of minuses

I hope I'm clear in some grade...
I'm going to write that in C, and I have experience in C, but I'm poor at algorithms. Just give me an idea and I'll try to make something of it. Now I just don't know where from I have to start...

entz · 04-09-2007, 09:27 AM

Wow , it's not that common that I see such stuff , hehe
anyways , Speaking on my experience with AI I'd tend to use optimization algorithms (i.e algorithms that produce better and better results after each interval/iteration etc ) to solve this kind of task.
...and speaking on the basis of my (shall I say not so humble) knowledge of optimization algorithms
I'd tend to use Genetic algorithms or any other varient of it , like simulated annealing , hill climbing and stuff like that.

basically your Territory coverage problem has something in common with the famous knap-sack problem and/or the traveling sales person problem

google "genetic algorithms" "traveling salesperson problem" and/or "knapsack problem"
hope that gets you going!

oh before I forget and if I'm allowed to ask , why are you bothering yourself with this kinda thing?
you aren't setting a scheme for laying out military bases across bulgaria , are you? (kidding)

cheers

Mara · 04-09-2007, 01:33 PM

It looks like a variant of the traveling salesperson problem, so NP-complete. Do you need the best solution or just one that's correct? The simpliest algorithm would be to put -'s in random until the whole area is covered

It looks like an algorithmic homework/project, so I guess you need to find out something more sophisticated. The terms entz gave you for a search are good ones. Start with that.

graemef · 04-09-2007, 11:00 PM

How about the following idea...
Examine each 1 that you have and calculate the number of adjacent 1's there are.
Find the 1 with the smallest number of adjacent 1's, you want to make that an X, and you want to make it an X by finding the 1 adjacent to this with the greatest number of adjacent 1s a -
A simple greedy algorithm that might be optimal?

To run it through your example:

Code:

0 0 0 0 1 0
0 0 0 1 1 1 
0 0 1 1 1 0 
1 1 1 1 1 0 
0 0 0 1 1 1

Calculate the number of adjacent 1s

Code:

0 0 0 0 3 0
0 0 0 5 5 3 
0 0 5 7 6 0 
1 3 5 7 6 0 
0 0 0 4 4 2

So the point with 1 neighbour needs to be an X and the adjacent square becomes a -

Code:

0 0 0 0 1 0
0 0 0 1 1 1 
0 0 X 1 1 0 
X - X 1 1 0 
0 0 0 1 1 1

Now repeat the process, counting the neighbouring 1s

Code:

0 0 0 0 3 0
0 0 0 5 5 3 
0 0 X 5 6 0 
X - X 5 6 0 
0 0 0 3 4 2

Now it is the 2 that becomes an X with the 6 becoming the -, hence:

Code:

0 0 0 0 1 0
0 0 0 1 1 1 
0 0 X X X 0 
X - X X - 0 
0 0 0 X X X

Doesn't take much to work out that it will resolve in one more iteration with the final result being:

Code:

0 0 0 0 3 0
0 0 0 2 3 2 
0 0 X X X 0 
X - X X - 0 
0 0 0 X X X

Code:

0 0 0 0 X 0
0 0 0 X - X 
0 0 X X X 0 
X - X X - 0 
0 0 0 X X X

or

Code:

0 0 0 0 - 0
0 0 0 X X X 
0 0 X X X 0 
X - X X - 0 
0 0 0 X X X

Resolving ties would be an issue, I'm not certain if it would matter...?