OutlineAnnouncements: PA3 is online, PA2 performance report due nowToday:• Travelling Salesman Problem (TSP)• Branch and Bound and Backtracking [Preiss 14.2]• k-approximation and k-optSugih Jamin ([email protected])Graph Algorithm QuestionsSee airline flight graphDescribe an algorithm to determine:• all non-stop flights from JFK (O( ))• if any non-stop flights from JFK exist (O( ))• greatest distance covered by a non-stop flight from JFK (O( ))Associate a price with each flight, describe an algorithm to determine:• best “value” non-stop flight from JFK (max distance/price) (O( ))• best “value” tour (non-stop or connecting flights) from JFK (O( ))Sugih Jamin ([email protected])Graph Algorithm QuestionsDescribe an algorithm to determine:• if a flight from JFK to SFO exists (O( ))• minimal cost (distance or price) from JFK to SFO (O( ))Suppose numbers represent cost (in billions USD) to build high-speed rail,describe an algorithm to determine least cost construction, such that anycity can be reached from any other city (O( ))Suppose you are planning a family reunion. Your family is spread out allover the US and you are paying for their travel. Describe an algorithm tofind the city to host the reunion that minimizes total travel cost (O( ))Sugih Jamin ([email protected])Hamiltonian Cycles and the Travelling Salesman Problem (TSP)For the flight routes given in the airline flight graph is there a tour thattakes us to each city exactly once and then takes us back to the startingcity?Such a tour is called a Hamiltonian Cycle, and a graph containing aHamiltonian cycle is called HamiltonianGiven a weighted graph, the Travelling Salesman Problem asks to find aHamiltonion cycle with minimal weight (or of weight less than a givenbound)Sugih Jamin ([email protected])Example: the Travelling Professor ProblemFig. 10.2.10 (J&S) lists some cities in India with the approximate roaddistances in milesI’ve never been to India. I’d like to cover all of these cities in 10 days,going 450 miles a dayIs there a tour that would take me to all of the cities in less than 4500miles?I’ll be flying in and out of ChennaiSugih Jamin ([email protected])A Tour of IndiaC0CN650Sugih Jamin ([email protected])A Tour of IndiaC0CN650CNA1135Sugih Jamin ([email protected])A Tour of IndiaC0CN650CNA1135CNAK1885Sugih Jamin ([email protected])A Tour of IndiaC0CN650CNA1135CNAK1885CNK1320Sugih Jamin ([email protected])A Tour of IndiaC0CN650CNA1135CNAK1885CNK1320CNKA2070Sugih Jamin ([email protected])A Tour of IndiaC0CN650CNA1135CNAK1885CNK1320CNKA2070CNKAD2190Sugih Jamin ([email protected])A Tour of IndiaC0CN650CNA1135CNAK1885CNK1320CNKA2070CNKAD2190CNKADS2665Sugih Jamin ([email protected])A Tour of IndiaC0CN650CNA1135CNAK1885CNK1320CNKA2070CNKAD2190CNKADS2665CNKASP3005Sugih Jamin ([email protected])A Tour of IndiaC0CN650CNA1135CNAK1885CNK1320CNKA2070CNKAD2190CNKADS2665CNKASP3005CNKADSPM3725Sugih Jamin ([email protected])A Tour of IndiaC0CN650CNA1135CNAK1885CNK1320CNKA2070CNKAD2190CNKADS2665CNKASP3005CNKADSPM3725CNKADSPMC4525Sugih Jamin ([email protected])A Tour of IndiaC0CN650CK1005CNA1135CNAK1885CNK1320CNKA2070CNKAD2190CNKADS2665CNKASP3005CNKADSPM3725CNKADSPMC4525Sugih Jamin ([email protected])A Tour of IndiaCKA1755C0CN650CK1005CNA1135CNAK1885CNK1320CNKA2070CNKAD2190CNKADS2665CNKASP3005CNKADSPM3725CNKADSPMC4525Sugih Jamin ([email protected])A Tour of IndiaCKA1755C0CN650CK1005CKAN2240CNA1135CNAK1885CNK1320CNKA2070CNKAD2190CNKADS2665CNKASP3005CNKADSPM3725CNKADSPMC4525Sugih Jamin ([email protected])A Tour of IndiaCKA1755C0CN650CK1005CKAN2240CKANM2760CNA1135CNAK1885CNK1320CNKA2070CNKAD2190CNKADS2665CNKASP3005CNKADSPM3725CNKADSPMC4525Sugih Jamin ([email protected])A Tour of IndiaCKA1755C0CN650CK1005CKAN2240CKANM2760CNA1135CNAK1885CNK1320CNKA2070CKANP2800CKANPD2950CKANPDS3425CKANPDSM4105CKANPDSMC4905CNKAD2190CNKADS2665CNKASP3005CNKADSPM3725CNKADSPMC4525Sugih Jamin ([email protected])A Tour of IndiaCKA1755C0CN650CK1005CKAN2240CKANM2760CNA1135CNAK1885CNK1320CNKA2070CKANP2800CKANPD2950CKANPDS3425CKANPDSM4105CKANPDSMC4905CKAD1875CKADS2250CKADSM2930CKADSMP3650CKADSMPN4210CKADSMPNC4860CNKAD2190CNKADS2665CNKASP3005CNKADSPM3725CNKADSPMC4525Sugih Jamin ([email protected])A Tour of IndiaCKA1755C0CN650CK1005CKN1675CKNA2160CKNAP2300CKNAPD2450CKNAPDS2925CKNAPDSM3605CKNAPDSMC4405CKAN2240CKANM2760CNA1135CNAK1885CNK1320CNKA2070CKANP2800CKANPD2950CKANPDS3425CKANPDSM4105CKANPDSMC4905CKAD1875CKADS2250CKADSM2930CKADSMP3650CKADSMPN4210CKADSMPNC4860CNKAD2190CNKADS2665CNKASP3005CNKADSPM3725CNKADSPMC4525Sugih Jamin ([email protected])A Tour of IndiaCKA1755C0CN650CK1005CKN1675CKNA2160CKNAP2300CKNAPD2450CKNAPDS2925CKNAPDSM3605CKNAPDSMC4405CKAN2240CKANM2760CNA1135CNAK1885CNK1320CNKA2070CKANP2800CKANPD2950CKANPDS3425CKANPDSM4105CKANPDSMC4905CKAD1875CKADS2250CKADSM2930CKADSMP3650CKADSMPN4210CKADSMPNC4860CNKAP2210CNKAPD2360CNKAPDS2835CNKAPDSM3515CNKAPDSMC4315CNKAD2190CNKADS2665CNKASP3005CNKADSPM3725CNKADSPMC4525Sugih Jamin ([email protected])Finding a Tour for the ProfIf we avoid the long route from Chennai to Kolkata, we can try:Chennai-Nagpur-Kolkata-Agra-Delhi-Jaiselmer-Jaipur-Mumbai-Chennaifor a total distance of 4525 milesOr perhaps we should try to avoid the expensive routes to Nagpur fromChennai and Kolkata:Chennai-Kolkata-Agra-Nagpur-Jaipur-Delhi-Jaiselmer-Mumbai-Chennaifor a total distance of 4905 milesChennai-Kolkata-Nagpur-Agra-Jaipur-Delhi-Jaiselmer-Mumbai-Chennaiis only 4405 miles: tour found!In general, how does one find a Hamiltonian cycle in a graph?Sugih Jamin ([email protected])Problem Space vs. Solution SpaceWhile you search for a solution in the problem space, you are generating“states” in the solution spaceThe “states” in the solution space form a search tree, with each internalnode being a partial solution and the leaves potential solutionsFor example:• problem space: find a TSP tour starting from Chennai• solution space: each step you take forms a partial path that is aunique “state” in the solution search treeSugih Jamin ([email protected])Solution Space SearchWhen we talk of searching for a solution, we’re talking about searching thesolution space/search treeDesign patterns:• brute force• greedy, usually involving heuristics• divide-and-conquer, usually involving recursion• amortized• randomized• branch-and-bound and backtracking• approximation• local search• dynamic programming• steepest