CS 1501代做、代写Python/Java程序设计

日期：2024-04-07 09:22

Support for Assignment 4

CS 1501

Sherif KhattabGeneral Hints

? You can get the number of vertices using ag.getAirports().size(), whereby

ag is an AirlineGraph object

? Iterate over airports using for(String airport: ag.getAirports()){ … }

? You can get a unique integer for each airport in the graph using the

ag.getAirportNo() method

? You can retrieve the set of neighbors of an airport using

ag.adj(airportName)

? To iterate over the set of neighbors: for(Route r: ag.adj(airportName)){ … }

? You can retrieve the name of a neighboring airport using r.destination

? You may use HashSet to instantiate Set objectsfewestStops

? Use BFS

? check the pseudo-code in lecture notes

? Shortest path Source -> transit -> destination can be found by

? shortest path source ? transit

? shortest path transit ? destination

? concatenate the two shortest paths

? Be careful not to add transit twice to the concatenated pathConnected Components

? Use BFS

? You can find the pseudo-code in the lecture notesallTrips

? Use backtracking and pruning

? Define a recursive helper method: solve(current decision, current solution)

? current decision ? current vertex (int or String) ? current solution

? Set<ArrayList<Route>> of trips found so far

? current path: ArrayList<Route>

? total price so far of current path

? number of stops so far of current path

? destination, budget and max number of stops for comparison

? Inside the recursive helper method:

? if current vertex is the destination ? add current path to the solution set and return

? iterate over all possibilities (unmarked neighbors)

? check if you can add the neighbor to the current path (total price won’t exceed budget and total number of stops won’t exceed maximum stops)

? if so, mark neighbor, update current path, its price, and its number of stops.

? make a recursive call on the neighbor

? undo changes to current path, price, and number of stops and unmark neighbor

? mark start airport before calling solve the first timeallRoundTrips

? Use backtracking and pruning

? Define a recursive helper method: solve(current decision, current solution)

? current decision ? current vertex (int or String) ? current solution

? Set<ArrayList<Route>> of trips found so far

? current path: ArrayList<Route>

? total price so far of current path

? number of stops so far of current path

? budget and max number of stops for comparison

? Inside the recursive helper method:

? if current vertex is the source and stops so far > 0 ? add current path to the solution set and return

? iterate over all possibilities (unmarked neighbors)

? check if you can add the neighbor to the current path (total price won’t exceed budget and total number of stops won’t exceed maximum stops)

? if so, mark neighbor, update current path, its price, and its number of stops.

? make a recursive call on the neighbor

? undo changes to current path, price, and number of stops and unmark neighbor

? Don’t mark start airport before calling solve the first time