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?