Embodiments relate to generating a virtual machine (VM) migration plan. A method includes determining an initial mapping of VMs to hosts as an origin state and a final mapping of VMs to hosts as a goal state. Candidate paths are generated from the initial mapping to the final mapping. The candidate paths are evaluated based on a heuristic state transition cost from the origin state through intermediate states to the goal state by recursively obtaining a list of transitions that a parent state underwent. A heuristic goal cost is identified to reach the goal state from the intermediate states based on a fewest number of VM movements. The VM migration plan is generated 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.