1. A method for generating a virtual machine migration plan, the method comprising: determining an initial mapping of a plurality of virtual machines to a plurality of hosts as an origin state; determining a final mapping of the virtual machines to the hosts as a goal state; generating a plurality of candidate paths to transition from the initial mapping to the final mapping; evaluating the candidate paths based on a heuristic state transition cost to transition from state-to-state from the origin state through a plurality of intermediate states to the goal state by recursively obtaining a list of transitions that a parent state underwent to reach the parent state from the origin state; identifying a heuristic goal cost to reach the goal state from the intermediate states based on a fewest number of virtual machine movements; and generating the virtual machine migration plan based on the heuristic state transition cost of the candidate paths in combination with the heuristic goal cost of a sequence of transitions from the origin state to the goal state having a lowest total cost.