Homework SourseThis should be like a general type of search problem where y
This should be like a general type of search problem where you search for the Airline routes . The Airline Company wants a program based on Algorithm to process customer requests to fly from some origin city to some destination city. We shall solve this problem by using recursion. So that we can focus on recursion, we will simplify the problem: For each customer request, just indicate whether a sequence of flights from the origin city to the destination city exists.
Imagine three input text files that specify all of the flight information for the airline as follows:
• Pairs of city names, each pair representing the origin and destination of one of flights
• Pairs of city names, each pair representing a request to fly from some origin to some Destination
The program should then produce output such as Complete the solution to the problem.
The input to the program consists of three text files, as follows:
Request is to fly from Providence to San Francisco- flies from Providence to San Francisco.
Request is to fly from Philadelphia to Albuquerque. Sorry - does not fly from Philadelphia to Albuquerque.
Request is to fly from Salt Lake City to Paris. Sorry - does not serve Paris.
The flight map in Figure 1 represents the routes that flies.
An arrow from city C1 to city C2 indicates a flight from C1 to C2 .
In this case, C2 is adjacent to C1 and the path from C1 to C2 is called a directed path .
For example, in Figure 1 , there is a flight from city R to city X , but not from city X to city R .(C2 adjacent to C1 does not mean the vice versa is always true.)
. When processing a customer’s request to fly from some origin city to some destination city, you must determine from the flight map whether there is a route from the origin to the destination.
For example, by examining the flight map in Figure 1 , you can see that a customer could fly from city P to city Z by flying first to city W , then to city Y, and finally to city Z; that is, there is a directed path from P to Z : P?W , W?Y , Y?Z.
Thus, you must develop an algorithm that searches the flight map for a directed path from the origin city to the destination city. Such a path might involve either a single flight or a sequence of flights. The solution developed here performs an exhaustive search .
That is, beginning at the origin city, the solution will try every possible sequence of flights until either it finds a sequence that gets to the destination city or it determines that no such sequence exists.
First consider how you might perform the search by hand. One approach is to start at the origin city C0 and select an arbitrary flight that departs from the origin city.
This flight will lead you to a new city, C1 . If city C1 happens to be the destination city, you are done; otherwise, you must attempt to get from C1 to the destination city.
To do this, you select a path to travel out of C1 .
This flight will lead you to city C2 . If C2 is the destination, you are done; otherwise, you must attempt to get from C2 to the destination city, and so on.
A recursive strategy. To fly from the origin city to the destination city by first flying from the origin city to a city C and then by flying from C to the destination has a distinct recursive flavor.
We can restate this strategy as follows: To fly from the origin to the destination:
Select a city C adjacent to the origin
Fly from the origin to city C
if (C is the destination city ) Terminate— the destination is reached
else Fly from city C to the destination
Consider the possible outcomes of applying the previous strategy:
1. You eventually reach the destination city and can conclude that it is possible to fly from the origin to the destination.
2. You reach a city C from which there are no departing flights. 3. You go around in circles. For example, from C1 you go to C2 , from C2 you go to C3 , and from C3 you go back to C1 .
You might continue this tour of the three cities forever; that is, the algorithm might not terminate.
First outcome corresponds to a base case of the recursive algorithm. (if the o/p is obtained in 1st outcome, then fine). If you ever reach the destination city, no additional problems of the form “fly from city C to the destination” are generated, and the algorithm terminates.
However, because flight does not fly between all pairs of cities, you certainly cannot expect that the algorithm will always find a path from the origin city to the destination.
For example, if city P in Figure 1 is the origin city and city Q is the destination city, the algorithm could not possibly find a path from city P to city Q .
Even if there were a sequence of flights from the origin city to the destination, it would take a bit of luck for the previous strategy to discover it the algorithm would have to select a “correct” flight at each step.
For example, even though there is a way to get from city P to city Z in Figure 1 , the algorithm might not find it and instead might reach outcome 2 or 3.
You thus need to make the algorithm more sophisticated, so that it always finds a path from the origin to the destination, if such a path exists, and otherwise terminates with the conclusion that there is no such path.
Project narrative
When searching for a sequence of fights between cities, you must take into account the
possibility that the algorithm will make wrong choices. For example, the algorithm must
be able to backtrack when it hits a dead end, and you must eliminate the possibility that
the algorithm will cycle.
This project considers an organized way to make successive guesses at a solution. If a particular guess leads to a dead end, you back up to that guess and replace it with a different guess. This strategy of retracing steps in reverse order and then trying a new sequence of steps is called backtracking .You can combine recursion and backtracking to solve the following problem. You may use stack also in your solution.(may be DFS can help you)
You should develop following for this project.
1. A complete working algorithm with explanation of each line in the Pseudocode.
2. Writing a program in C++ based on your Algorithm with comments for each line of code.
Representing the Flight Data The flight map for HPAir is a graph Adjacent vertices Two vertices that are joined by an edge u Directed path a A sequence of directed edges Figure 7-10 Flight map for HPAirSolution
Algorithm:
* Intialy declare a variable to hold the no of airports totaly available lets say thats A.
Then create a pointer to an array to save the adajcent airports.
Create two functions one is to add a new port and the other one is to check the reachability.
Create a constructor and define the airports adjecent ports there .
Next inside the the add port method use stack\'s push concept to add more nodes.
Inside the reacability method,
check two major constraints ,
1) is there any direct path available
2) Is there any indirect path available, if any of the above is available return yes else return no.
Program
Class Flight {
int A;
list<int> *ad;
public:
Flight(int A)
void addport(char r , char t)
bool reachability( char d , char y);
};
Flight :: Flight( int A)
{
this -> A =A;
ad = new list <int> [A]
}
void addport(char r , char t)
{ ad[r]. push _back(t) };
bool reachability ( char d , char y)
{
boolean *entered =new bool [A];
for(int i = 0; i<A ;i++);
{ entered [i] = false;
}
list <int > queue;
visited[d] = true;
queue.push_back[d];
list< int>::iterator i
for (i = ad[d].begin(); i != ad[d].end(); ++i)
f.addEdge(p, r)
f.addEdge(r, x);
f.addEdge(q, x) ;
cout << \"Enter the source and destination airports you want to fly: \";
int d, y;
cin >> d >> y;
if (f.reachability(d, y))
cout << \"There exist a route from \" << d << \" to \" << y;
else
cout << \"\ There is no route from \" << d << \" to \" <<y;
temp= d;
d = y;
y = temp;
if (f.reachability(d, y))
cout << \"\ There exist a route from \" << d << \" to \" << y;
else
cout << \"\ There is no route from \" << d << \" to \" << y
return 0;
