I'm looking for the best algorithm to optimize the decisions made in a simulation to find a fast result in a reasonable amount of time. The simulation does several "ticks" and occasionally needs to make a decision. Eventually, a goal state is reached. ( It would be possible to never reach a goal state if you make very bad decisions )
There are many many goal states. I want to find the goal state with the least number of ticks ( a tick equates roughly to a second in real life." I want to decide which decisions to make to get to the goal in as few seconds as possible,
Some points about the problem domain:
Straight off the bat, I can generate a series of choices that will lead to a solution. It won't be optimal.
I have a reasonable heuristic function to determine what would be a good decision
I have a reasonable function to determine the minimum possible time cost from a node to a goal.
Algorithms:
I need to process this problem for about 10 seconds and then give the best answer I can.
I believe A* would find me the optimal solution. The problem is that the decision tree will be so large that I won't be able to calculate it quick enough.
IDA* would give me a good first few choices in 10 seconds but I need a path to a goal.
At the moment I am thinking that I will start with the known non-optimal path to a goal and then perhaps use Simulated Annealing and attempt to improve it over 10 seconds.
What would be a good algorithm to research to try to solve this sort of problem?