The shortest path problem is one of the most fundamental problems corresponding
to the optimization problem where the state space is represented as a network,
and is applicable in various fields.This thesis focuses on the route finding
problem and the multiple sequence alignment problem as instances of this
problem,and provides solutions based on the A* algorithm for these problems.
In the route finding problem,not only the optimal route but also some
suboptimal routes are often required. We call the set of such routes better
routes.This thesis first shows the effect of the bidirectional A* algorithm for
finding the best route,and devises an algorithm for finding edges contained in
better routes based on this algorithm.
For the multiple sequence alignment problem,this thesis takes an approach to
utilize the infotmation on pairwise alifnments for estimaates. This thesis
investigates the A* algorithm based on this approach and an faster approximate
method based on the A algorithm. We futher consider methods to improve the
common weak point of these algorithms due to the fact that they searches all
descecdant vertices when they expand a vertex.