i've a question about the following task: given is a maze (it's a simplified pacman-game) which contains several pills (and powerpills). now the goal is to write a program which is to find a path to eat all pills in the maze (while the path should be as short as possible). what would be a good strategy? thx

Simple:

Use A* to go to the nearest pill, from there go the the nearest other pill etc...

Hard:

Sounds like a traveling salesman problem. Google.

Edo

Quote:

Simple: Use A* to go to the nearest pill, from there go the the nearest other pill etc...

that seems to be a greedy-algorithm.


and yeah it sounds like a traveling salesman problem.

i should mention that the execute time limit is 30 seconds. it doesn't matter if you need the whole 30 seconds or just 2. Therefore it would be possible to use an algorithm which is not perfectly fast. the maximum dimension of the maze is also just 40x40 (very small).

Now, when you say that the execution time is 30 seconds, does that mean just the path finding? or does that include everything else?

Do you create the path first? or create it on the fly?

Yeah, it does look like its going to be a special case of the travelling salesman problem. There's just going to be quite alot of overlapping going on.

You'll probably need something slightly more complicated than A*.

Quote:

Original post by WeirdoFu Now, when you say that the execution time is 30 seconds, does that mean just the path finding? or does that include everything else? Do you create the path first? or create it on the fly?

i should explain that:

given is a maze (text-file) and the program must find a path (however you do that). after maximum 30 seconds the program is to output a path (in a outputfile). it's not a live-time interaction; it's a static problem.

Here's how you might formulate the problem.

You will need to create a graph where each of the nodes will be any turn in the path and any crossroad. Actually, just the crossroads will work. So, basically, create a graph with all the forks in the maze as nodes and have a link between any two nodes that have a path between them. Your goal will then be to find a tour that crosses every link at least once. The length of each link will be defined by how many pellets occupy or can occupy that path.

As for solving it....that I'm still thinking about. :p

it's important that i need not an algorithm which finds always the optimal solution (but it would be fine if there is one) but a good solution (that includes heuristic methods)

[Edited by - nikita on March 31, 2005 2:57:25 AM]

How many is a 'few'?

(i've got an idea. But it all depends on how many things there are to search.)

From,
Nice coder

well, for a 40x40 maze, I'd guess you wouldn't have more than 30 or 40 intersections. Is that a small enough number to brute-force TSP?

<referential tsp linky>