A trajectory planning problem for a single unmanned combat aerial vehicle (UCAV) performing an air-to-surface multi target attack mission was studied. First, this problem was mathematically formulated as a variant of the traveling salesman problem (TSP), called the dynamic-constrained TSP with Neighborhoods (DCTSPN). A novel planning algorithm based on an updatable probabilistic roadmap (PRM) was then presented to solve the DCTSPN. This algorithm blends the sampling-based motion planning ideas with combinatorial optimization, and can reduce the complicated trajectory planning problem in high-dimensional continuous state space to a routing problem on a finite discrete graph, while maintaining completeness guarantees (in a probabilistic sense). The entire planning procedure was divided into two phases: 1) In offline preprocessing phase, the original problem was converted into a standard ATSP (Asymmetric TSP) by Halton quasirandom number generator and the Noon-Bean transformation algorithm; 2) In online querying phase, a fast heuristic searching algorithm was used to solve the ATSP. To generate dynamically feasible flight trajectories, a trajectory planning algorithm based on the Gauss pseudospectral method (GPM) was developed. Numerical experiments indicate that the algorithm adopted can generate both feasible and near-optimal attack trajectories quickly for online purposes.