OJ Board

Posted: **Wed Jun 25, 2003 1:31 am**

Is there a way to solve this problem with backtrack?

What I need to do to avoid repeating states?

Thanks!

JP.

Posted: **Thu Jun 26, 2003 2:04 pm**

Hi!

Man, I've tried to solve this one but I'm in trouble...

I've used BFS and hash to store configurations I've seen and I'm getting MLE and some SIGSEGV

Can anyone tell me some tips on A* or IDA*, by pointing some sites or even describing the algorithm?

Thanks,

JP!

Posted: **Fri Jun 27, 2003 7:42 pm**

hi. when i visit a new state, i just checked that a state cannot be an ancestor of itself. i used a stack of depth 52 to keep track of this.

hope this helps.

Posted: **Sat Jun 28, 2003 12:01 am**

Hi,

I didn't understand very well what you mean. Can you show an example or try to explain it better?

I really don't know how to store only 52 configurations!!! My queue goes as big as 60000 when it reachs the 45-50 steps.

Thanks,

JP!

Posted: **Sat Jun 28, 2003 6:54 pm**

i'll try to explain. consider the following tree:

Code: Select all

             A
    ---------|---------
    B(1)              C(1)
  ---|---          ----|----
  .     .              D
  .     .              |
  .     .              .
                      .
                      .
                      E
                  ----|----
                  C(2)    B(2)
                          |
                          .
                          .
                          .

in this tree, A, B, C, D, E are different states. C(1) is the first occurance of state C. C(2), B(1) and B(2) have similar meanings. A is the initial state.

now i expand from state A to B(1) and expand B(1), and dont get a solution there. so i again start from A and go to C(1). expanding from C(1), if i reach the same state again, here C(2), then i don't expand from there. but if i reach B(2), then although it was expanded earlier, i expand it again since B(2) is not on the path from A to E. so i only have to store which states have been visited on the current path from the root to the current state.

i hope it is clear enough now.

Posted: **Sat Jun 28, 2003 10:16 pm**

I think I've get it. I'll try to implement it when I get to linux (I'm using windows right now...)

Thanks a lot for your help!

JP!

Posted: **Mon Jun 30, 2003 2:20 pm**

What search do you use?

I'm now using DFS with max depth 46 and it can't solve in time...

JP!

Posted: **Mon Jun 30, 2003 6:18 pm**

i used IDA* with adjustments as mentioned by wyvmak.

Posted: **Mon Jun 30, 2003 6:51 pm**

Hi, again!

Can you point me with some site with good info on IDA* or A* similar algorithms?

Thanks,

JP!

Posted: **Tue Oct 05, 2004 5:34 pm**

http://en.wikipedia.org/wiki/A-star_search_algorithm

Posted: **Tue Mar 22, 2005 12:45 pm**

Hi,

My code can't pass the time limit.
I use IDA* algorithm.

Can somebody help me?
or you can give me some tips and hints.

Thanks in advance!

Posted: **Wed Mar 23, 2005 6:04 pm**

Hi,

I got accepted now.

1.705 seconds and memory cost 452

IDA* and F(x)=G(x)+4/3*H(x)

^_^

Posted: **Thu Sep 22, 2005 6:30 am**

What should I do if the initial configuration is in the correct order?
I mean what is the output of the program if the initial configuration is:

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0

My program (which has got WA) prints an empty line. So, can anybody help?

Posted: **Fri Feb 17, 2006 3:46 am**

I got WA for this problem but it works for all of my test data. I need some test data for this problem.

Is there any thing critical, tricky in this problem.

Thank You,
Ahsan

Posted: **Tue Jul 04, 2006 7:57 pm**

Hello

I am trying to solve Problem 10181 because I wanted to learn more about A*. But I always get TLE. I can solve the example problem from the problem definition, but when I try to solve a more complicate problem my Programm runs forever. Just a short informal description of what I do (the code is really messy).

- Create a "Peudo Hash Table" for the already visited states C
- Create a prority queue Q
- Get first state from Q
(which is cheapest of all states in Q according to f(n) = g(n) + h(n))
and remove it from Q
- Check if it is A goal state ( h(n) == 0 )
- If not, create all successors and insert state in C
- for each succesor
- check if it is in C
- if not, push it in Q
- continue from start

o Q is initialiyed with the start state
o state is a class I defined which stores the current layout of the puzzle as
an [4][4] array, the path as a string, the current step cost and has
memberfunctionss for comparing to other states (so I can use the STL
prority queue)
o The psuedo hash table is also a class I defined my own. It has a
list<state>[16][16][16][16] "hashing" the states by 4 elements of the
puzzle (upper left, right, lower left, right). The "insert" function only
inserts a state if it is not alread in the array.
o h(n) is manhatten distance sum of the tiles of the puzzle

I think I did a pretty straight forward implementation of A* on a graph with a consistent heuristic....
I read that you cannot solve this problem using A* but you have to use IDA*... I cannot find a "good" description of IDA* anywhere

or, one that I understand....
I think my hash class is, well, "not so good" but I have no idea how I could efficently store already visited states... but I think I have to store those, or there will be "loops"....

Can someone please help? Is there something wrong in the "code" I posted? Or do you know a webpage with a good/detailed/easy-to-read descriptions of IDA*

I'm working on this problems for 2 days now and I'm kinda stuck....

Thanks in advance for any help!

OJ Board

10181 - 15-Puzzle Problem

Backtrack

MLE

10181 15-puzzle: I need a clarification

10181 -- 15 Puzzle -- Test data required

10181 - 15 Puzzle