1. We cant solve large instances by Enumeration because it invloves very large number of Calculations.
On an Average for an instance of solving a problem of size n it will form at least 2 ^ n combinations. And in each cobination, It will lopp onto all terms .
If n=20,
Least number of calculations =(2^20)*20=1048576*20= 20971520 microseconds= 20 seconds
If n=200,
Least number of calculations =1.6069380442589903e+60 *20 =approx 1.6 e +55 seconds= approx 6 hours
It is a very large time for such a small problem
2. Greedy solved all the instances optimally in real time.
No dynamic programming algorith do not worked on all instances and it thrown a segmentation Fault error for hard1.2000.1.txt . Becuase for solving such a huge dataset it needed huge memory. Computer could not provide that much memory for all the arrays. So the problem came to a Halt.
Yes, branch-and-bound ca,e to a stop on all the instances and gave us the result in real time.
3. i) For greedy, the hard1 instances do not possess any problem and they were easy for greedy algorithm to solve because only sorting is required in greedy algorithm and no other memory requirements are there.
ii) For branch and bound also, the hard1 instances do not possess any problem and they were easy for this algorithm to solve. Because a comparision is being made at every step to keep or release the solution vector. The time taken is real time as it only requires time equal to traversing the list and performing some calculations.
(iii) It is a hard problem for Dynamic Problem because it need extra memory allocated for the calculations, the compiler is not able to give that much memory to the program and thus is failing.
4. In my opinion greedy algorithm and branch- and- bounce are best suited for airline Problem. Because they have smaller memory requirements and can give the result in real time. The result given by greedy is not sure to be optimal but time taken is very less.
So final solution would be to go with branch and bound algorithm. If the algorithm runs out of time, then they can use greedy algorithm for such instances.
