|
I'm trying to figure out how to minimize the size of the search space for the A* algorithm.
I'm trying to solve the n-Queens problem using A*, and so, given a root and a goal, I create the intervening graph to be searched. That's fine, but the state space grows exponentially since its size in n^n (making n = 10 have a space of 10 billion items).
How could we deal with this?
Serialize and de-serialize?
The object is I'm trying to see how to build the SM-A* (Simplified Memory bounded A*).
Cheers
Don't forget to vote if the response was helpful
Sig history
"dad" Ishmail-Samuel Mustafa
"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib
Mustafa Ismail Mustafa wrote:
Keep it up.
Fool.
I now think of you as Mr. T! - Trollslayer
|
|
|
|
|
The simplest way to restrict a search space is to introduce appropriate constraints.
Alternatively, you could minimize some kind of heuristic function (defined on a per node basis) to pick the best possible search direction from any given node. The heuristic function will therefore only pursue searches from nodes at which it is minimized.
I don't know if some kind of Rapidly Exploring Random Tree might also be of interest.
|
|
|
|
|
73Zeppelin wrote: The simplest way to restrict a search space is to introduce appropriate constraints.
You mean like a maximum height for example? Or should I be thinking about generating them on the fly?
Like for example, where n == 4, if say the heuristics included that any queen should be in a column by itself, then the current node can generate 4 other nodes only if we follow the heuristic that one and one queen only will be moved up and down the column. This can be aided by the cost function, specifying a node with a greater number of constraints satisfied costing less.
Maybe the diagram expresses it better:
0 = empty
X = queen
when n == 4
A B C D
0 0 0 X 0
1 X 0 0 0
2 0 0 0 0
3 0 X 0 X
(1303 in compressed form)
Can generate any of 16 states (4 queens * 4 potential locations) or 12 states (4 queens * 3 potential locations if we decide that if a queen is chosen it must be moved to a location other than its present one)
So if we chose file D, the generated states to chose from are (generated states = n-1 heuristic):
(original)
A B C D A B C D | A B C D A B C D
0 0 0 X 0 | 0 0 0 X X | 0 0 0 X 0 | 0 0 0 X 0
1 X 0 0 0 | 1 X 0 0 0 | 1 X 0 0 X | 0 X 0 0 0
2 0 0 0 0 | 2 0 0 0 0 | 2 0 0 0 0 | 0 0 0 0 X
3 0 X 0 X | 3 0 X 0 0 | 3 0 X 0 0 | 0 0 X 0 0
(1303) (1300) (1301) (1302)
1302, the last one would have the smallest cost because it has the least number of conflicts, i.e. greatest number of constraints satisfied and it happens that it actually is a solution.
The closed queue's size can be maintained so that the search won't run to infinity.
Am I making sense? To me it seems like a viable solution.
Don't forget to vote if the response was helpful
Sig history
"dad" Ishmail-Samuel Mustafa
"There is no wealth like knowledge, no poverty like ignorance" Ali Ibn Abi Talib
Mustafa Ismail Mustafa wrote:
Keep it up.
Fool.
I now think of you as Mr. T! - Trollslayer
|
|
|
|
|
Generating on the fly using current available information about the state space is quite efficient (may or may not be "optimal", I'm not sure), in my opinion.
And it seems viable. It will, of course, require a bit of testing to make sure but offhand, it looks good.
|
|
|
|
|
Hello all.
I'm working on program decoding mpeg streams, decoding itself is performed on hardware - my code passes frames read from a file.
The problem is that I need recongnize i-frames. Is that information
contained in every frame or the frequency of i-frames in the stream is
in file header? I would appreciate any suggestions, links etc. (complete solution too).
|
|
|
|
|
that information is in the header of each Group Of Pictures,
MPEG TS {
Packet Elementary Stream (Video){
GOP {
### start code
header information <--- your mission, should you choose to accept it.
...
}
}
}
sorry for the late reply.
|
|
|
|
|
Hello everyone! I am a fourth year IT student and I am now currently making my thesis. By this time, I am in the process of building a mathematical model in helping to identify the right products to be purchased as well as its corresponding quantity to meet the desired goals like having an increase of sales and minimization of product purchasing costs. By the way, my study is all about Decision Support Sytem applying the goal-seeking analytical modeling technique. Is there anyone who can help me on how to build the model??? I really need your expertise on this matter. Please help me to deal with this...
|
|
|
|
|
If it's a thesis project, you should really be consulting with your thesis supervisor. Soliciting help from the internet could end up with you using somebody else's work in your thesis and claiming it to be yours; a big no-no.
Unless you have a specific question or programming issue, I suggest you consult with your supervisor first as to the best method by which to proceed.
|
|
|
|
|
For an incompletely-understood complex problem, I like to initially "push" the problem and see how it pushes back. This gives insights as to the issues the ultimate solution needs to address.
Since you're meeting goals while minimizing costs, one way to push the problem is to examine Linear Programming http://en.wikipedia.org/wiki/Linear_programming[^], which is a simple, effective, well-known approach to this type of problem.
Although Linear Programming probably won't meet your needs, the value here is in analyzing why it doesn't work for your problem. The answer to that will provide clues to coming up with a more sophisticated solution. Repeat as needed.
|
|
|
|
|
how to connect crystal report with ASP 2.0
|
|
|
|
|
I've been tasked by my AI Professor to create a solution for the n-Queens problem, using A* and GA, and maintaining Constraint Satisfaction.
Basically, is this possible? If so, how's the mix? I know I should have asked the Professor these questions in class, but he was in a rush to leave because he his wife was delivering and it did not click at the time in my head.
|
|
|
|
|
Isn't A* a path finding algorithm? In that sense using both A* and GA seems a little redundant. Just to take a whack at it, I would suggest using A* to search a possible population of paths generated by the GA.
Alternatively, you could use the GA to position the queen and then A* to calculate the paths.
Like I said, either algorithm should be sufficient, I'm not sure why you need to use both. Any more recent developments since posting the original question?
(I've been absent from the forums as I was taking a Christmas break.  )
|
|
|
|
|
I called the Prof this morning and I explained to him that what I understood made the assignment a load of rubbish. It turns out I misunderstood. He wants two assignments, both solutions to the n-Queens problem, one using SM-A* (simplified memory bounded A*) and the other using GA.
Cheers.
|
|
|
|
|
Mustafa Ismail Mustafa wrote: He wants two assignments, both solutions to the n-Queens problem, one using SM-A* (simplified memory bounded A*) and the other using GA.
Ah, that would make more sense. Seems unnecessary (and possibly difficult) to mix the two.
|
|
|
|
|
Precisely.
I couldn't understand how he wanted the mix. It does make a lot more sense.
Cursed MSc.
|
|
|
|
|
Mustafa Ismail Mustafa wrote: Cursed MSc.
You have much to learn yet, young Masters Student.
|
|
|
|
|
Actually, I'm top of my class 
It didn't register at the time but I got suspicious when I started reading for the assignment. Didn't make sense, so I posted here and then I called the Prof and he set the record straight.
I'm aiming for the PhD at Queens, I really hope it works out. Computational Biology or Financial Engineering.
|
|
|
|
|
Mustafa Ismail Mustafa wrote: Financial Engineering
Interesting you brought that up - since I am a "financial engineer". I would counsel you not to go into it. There have been huge lay-offs (150,000+) in the wake of the financial crisis and investment banks are decreasing their activity in this area as most are being merged with their deposit side activities. Combine that with calls for increased regulation of the financial markets and derivatives and the number of jobs available for financial engineers will see a marked decrease.
I am trying to get out of the field myself and it is proving very difficult to find a job. The profession is currently very unpopular - nobody wants to be associated with those thought to be behind the credit crisis.
|
|
|
|
|
Really?
I'd have thought that it would pick up after the recession, besides, wouldn't that actually help the financial institutions get back on their feet faster?
I prefer going into Computational Biology, specifically into the modeling and forecasting of diseases and/or chemical reactions in biological entities systems.
You've given me food for thought.
In either case, because of the financial crisis, in the States, many universities have cut down the number of PhD students that they're willing to take on, but come this summer, I'm leaving Jordan to either carry on with the PhD or to get a better paying job in [western] Canada.
|
|
|
|
|
Yes. All investment banks are cutting back their quantitative positions. The increased regulation will mean more routine uses of derivative products and less need for people with quantitative backgrounds to invent new products.
It's already happening. In Zurich, for example, there are thousands with backgrounds in financial engineering on the job market. For each job posting they are getting so many applications they can't handle them all. Even the headhunter organizations are telling me not to expect anything until late next year at the soonest and, even then, there will be huge competition for limited positions - those with the most experience will be taken first. It's terrible. Most banks are waiting to see what the "new system" will mean for their risk management operations. That could be two years or more before there's a solid draft and implementation.
I'm trying to get into financial regulation so that when the banks start hiring I'll have some experience.
And it's worse in the U.S. The number of unemployed is in excess of 150,000.
|
|
|
|
|
Would you mind if I emailed you later on tonight when I get back home? I'd like to discuss this in greater detail if you don't mind. I would so totally appreciate it.
|
|
|
|
|
No problem. I'm GMT+1, so my response could be delayed due to time difference.
|
|
|
|
|
Great, I'm GMT +2 so we should be fine 
|
|
|
|
|
how to calculate shortest path between houses. answer must take into account fully laden sleigh and naughty/nice rating of occupants. urgent!
CODE PLEASE!
Merry Christmas CodeProject 
|
|
|
|
|
Mark Churchill wrote: how to calculate shortest path between houses
Dijkstra's algorithm for the nice! The longest path algorithm for the naughty!
( Is this a homework question?  )
It's a bit past Christmas, so Happy Holidays, Mark!
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
