## 851 - Maze

Moderator: Board moderators

I got Accpeted just before.
In this problem, using IDA* can save us a lot of memory and improve the speed.

--
DJWS, a newbie in programming
DJWS
Learning poster

Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan

This output for tests above
Code: Select all
`westwestsouthsoutheasteastsouthwestwestnorthnortheasteasteastwestwestwesteasteasteasteasteastwestsouthsoutheasteastsouthsouthwestwestsouthwestsouthwestwestsouthsouthwestsoutheastwestwestwestnorthsouthnorthwestwestnortheastsouthsouthsouthwesteasteastsoutheastwestnorthnorthsoutheastsoutheastsouthsouthsouthsoutheasteastwestsouthsouthsouthsoutheasteastwestsouthnorthnorthnorth`

And this another intersting input:
Code: Select all
`18#########......##......##......##....#.##..#..###...#..#######.#and outputwestnorthwestwestwestnorthwesteasteastsouthsouthsoutheastsoutheastsoutheastsouth`
artem
New poster

Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm

### 851 Maze II - IDA*?

I am struggling in this problem using IDA*.
I tried different ways to estimate the cost and heuristics functions but I didnot success.
My way to make estimation is:
g(x)
should be an addition of the parent node's g(x) with number of possible moves at this stage. for example, at certain stage, 3 'people' can move in one direction, then the g(x) = previous g(x) + 3

h(x)
Summation of all the 'people' that makes the shortest distance with any goal.

I am not sure what the admissible function is, but mine seems (and I tested) not the admissible one......
Is there any better estimation of f(x)? I am not eligible enough to obtain one for myself.
Solving problem is a no easy task...
Hackson
New poster

Posts: 35
Joined: Sun Nov 10, 2002 5:36 am

### Re: 851 Maze II - IDA*?

Hackson wrote:My way to make estimation is:
h(x)
Summation of all the 'people' that makes the shortest distance with any goal.

In heuristic searching, the estimate function h(x) must be an under-estimate.

According to this problem, more than 1 people may be able to escape at each step. So we can not estimate the steps with summation from all people. It's maybe an over-estimate.

I have send a message to you.
Good luck.
--
DJWS, a newbie in programming
DJWS
Learning poster

Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan

I was thinking to myself it's a very hard problem, for only 85 of us all solved it and mostly with heaps of time... Hm...
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
serur
A great helper

Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Hi fellows!

What do you think of 851-"Maze"?
I tried to solve it with IDA*.

My approach:
1) for every free position (i,j) I find (with bfs) distance[i][j] to the nearest escape-cell.
Thus I obtain admissible estimate - the solution is in the depth >= max(dist[i][j]).
2)if there is no solution in the depth D, then I increase D...

Now let the code speak for itself:

/
Code: Select all
` bad code is cut :) `

The above gives TLE...
Last edited by serur on Sat Apr 14, 2012 3:23 pm, edited 2 times in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
serur
A great helper

Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Your code implements just iterative-deepening DFS, not IDA*.
In a proper IDA* you should calculate heuristic function at each visited state.
If g is the distance to the current state ("depth" of it), h is the value of (non-overestimating!) heuristic for this state, then the distance from source to goal through this state is at least g+h. You stop recursion when this value exceeds current limit. The limit for the next iteration of IDA* is the minimum of these g+h's.

You can represent states more efficiently, if you just keep 64 bits (fits in a 'long long' type); 1 bit for each unblocked location, which indicate whether there may be a person there, for some starting position. Initially all bits are 1's for unblocked locations. For each move just shift the 1's left, up, down or right, except near the walls. This can be very efficiently implemented with binary operators and shifts.
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

Hi mf!

I beg you pardon for inaccuracy.
When deciding which move to make next -

north,east,south or west - we must analyze

all these possibilities by means of function

f=(steps made so far ) + (bfs-distance from

current position of the prisoner to

escape-cell) for each prisoner.
If for some prisoner this f()-evalutaion

gets beyond the depth that's contemplated in

the current iteration of IDA*, we prune the

branch..

about long long, though implementation is

not clear to me as yet... (also, Visual C++

doesn't support long long, but this makes

no matter after all)

Thank you, due to you I've grasped the

situation better now.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
serur
A great helper

Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Hi mf!

I need one more hint about states and long long.

Thank you
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
serur
A great helper

Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

You can use the following code, it should work both for MSVC and gcc:
Code: Select all
`/* Declares 64-bit unsigned integer type 'uint64' */#ifdef _MSC_VERtypedef unsigned __int64 uint64;#elsetypedef unsigned long long uint64;#endif`
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

Hi mf!

Thank you so much for your help.

This is my next attempt, which gives TLE.
It looks very awkward, and it's enormous, I know, but I'll appreciate your opinion.

Well, I think I'm on the right direction, so I'll try to improve my IDA*, and tweak something...

Thank you.
Last edited by serur on Tue May 30, 2006 3:30 pm, edited 1 time in total.
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
serur
A great helper

Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Hi. A few points:

1)
In an expression like 1 << k, the result is a 32-bit integer by default (when both operands are of type 'int', C standard demands 'int' as the result type).
You have to tell the compiler explicitely that you want a 64-bit shift.

For gcc it's sufficient to append suffix ULL to 1: 1ULL << k.
In MSVC, probably this will work: ((uint64)1) << k.

2)
I didn't at all mean to use 64-bit ints just instead of arrays.
Use all the power of bitwise operators, THAT is what makes them perfect for this problem.

In my solution I have these bitmaps:
all_inner: indicates which of the cells are strictly inside the map (not on the boundary or outside)
walls: which cells of the map are blocked by walls,
inner: inner = (~walls) & all_inner;
Each number represent 8x8 map; a cell (row, col) corresponds to bit 1<<(8*row+col).

Performing a move from a state s can be then done in this simple way:
Code: Select all
`north: s' = ((s >> 8) | (s & (walls << 8))) & inner)south: s' = ((s << 8) | (s & (walls >> 8))) & inner)west:  s' = ((s >> 1) | (s & (walls << 1))) & inner)east:  s' = ((s << 1) | (s & (walls >> 1))) & inner)`

3)
I don't think it makes much sense to use everywhere short's instead of int's.
Judge runs on a modern processor (not on some prehistoric 8086), you have lots of memory (100Mb+), and time (90 seconds).
That should be more than enough for IDA*. My own solution used BFS, much slower than IDA*, and it manages to finish in just 50 seconds.

Also, you have a bug: short's should be parsed with scanf("%hd", ...).
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

Hi mf!

Congratulations - you hold now your proper place in the ranklist
I also got AC (of course one is hardly surprised )
Thank you so much for your help - I don't know how I'd have done without your ingenius ideas.

Also,

Code: Select all
`south: s' = (((s<< 8) | (s & (walls>> 8))) & inner) north: s' = (((s >> 8) | (s & (walls << 8))) & inner) east:  s' = (((s << 1) | (s & (walls >>1))) & inner) west:  s' = (((s >>1) | (s & (walls << 1))) & inner) `

Now that you set better standard for this problem I dare say time limit (90 sec) will be adjusted also.

Thank you again.

Keep posting!
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
serur
A great helper

Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Oh, I've just "upgraded" my older solution from BFS to IDA*.
Literally it became 500 times faster (50sec -> 0.1s), I'm surprised myself...
mf
Guru

Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland

Hi!

you are quite prolific today
I see you have AC 358 - "Cow". With bisection I got WA so many times
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke
serur
A great helper

Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

PreviousNext

### Who is online

Users browsing this forum: No registered users and 1 guest