## 851 - Maze

Moderator: Board moderators

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:
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

artem
New poster
Posts: 17
Joined: Thu Jun 09, 2005 5:01 pm
This output for tests above

Code: Select all

``````west
west
south
south
east
east
south

west
west
north
north
east
east
east

west
west
west
east
east
east

east
east
west
south
south
east
east

south
south
west
west
south

west
south
west
west
south

south
west
south

east
west
west
west

north
south

north
west
west
north

east
south
south

south
west
east
east

south
east
west
north

north
south

east
south
east
south
south

south
south
east
east
west
south

south
south
south

east
east
west
south

north
north
north

``````
And this another intersting input:

Code: Select all

``````1
8
########
#......#
#......#
#......#
#....#.#
#..#..##
#...#..#
######.#

and output

west
north
west
west
west
north
west
east
east
south
south
south
east
south
east
south
east
south
``````

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

### 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...

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

### 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

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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[j] to the nearest escape-cell.
Thus I obtain admissible estimate - the solution is in the depth >= max(dist[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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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_VER
typedef unsigned __int64 uint64;
#else
typedef unsigned long long uint64;
#endif
``````

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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", ...).

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
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...

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm
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