public class BestTourFinder
extends java.lang.Object
Modifier and Type | Field and Description |
---|---|
private double |
bestDistance |
private java.util.List<Position> |
bestTourPositions |
private java.util.List<Shop> |
bestTourShops |
private Position |
endPos |
private GroceryList |
groceryList |
private static int |
NUM_SHOP_LIMIT_WHERE_WE_STOP_FINDING_OPTIMAL_TOUR |
private java.util.Map<Shop,java.util.List<ProductAmount>> |
productsAtShop |
private java.util.List<Shop> |
shops |
private Position |
startPos |
Constructor and Description |
---|
BestTourFinder(Position startPos,
Position endPos,
java.util.List<Shop> shops,
GroceryList groceryList)
Constructor that finds the best tour to buy all the products in the grocery list
among the given shops that starts at the startPos and ends at endPos.
|
Modifier and Type | Method and Description |
---|---|
private double |
distance(Position posA,
Position posB)
Give the linear distance between two points
|
private void |
findBestRoute(java.util.Set<Shop> solution)
Find the shortest path starting at startPos, going through all the shops in the best tour
and ending at endPos, for small instances.
|
private void |
findBestRouteUsingBacktrack(java.util.List<Shop> shopList,
java.util.List<Shop> route,
double distance)
extension of the findBestRoute algorithm using backtracking.
|
private Shop |
findBestShopForProduct(java.util.Set<Shop> solution,
java.util.Set<Shop> remainingShops,
ProductAmount productAmount)
Finds the best shop to buy the given product.
|
BestTour |
getBestTour()
Create a BestTour object to store the result of the algorithm
|
java.util.List<Position> |
getBestTourPositions()
Returns all the positions of the tour: the start position, the shops (in order) and the end position.
|
java.util.List<Shop> |
getBestTourShops()
Returns the shops (in order) of the best tour.
|
private double |
getCostForProductInNewShop(ProductAmount productAmount,
Shop shop,
java.util.Set<Shop> solution)
Gets the cost of buying the product in the shop, given that we haven't planned yet to go to that shop.
|
private double |
getCostForProductInVisitedShop(ProductAmount productAmount,
Shop shop)
Gets the cost of buying the product in the shop, given that we already planned to visit the shop to buy another
product.
|
private double |
getDistanceCostOfAddingShop(Shop shop,
java.util.Set<Shop> solution)
Return the cost of adding a new shop to the actual tour, using an approximation.
|
Position |
getEndPos() |
private double |
getProductPriceAtShop(ProductAmount productAmount,
Shop shop)
Returns the price of buying a product in a certain amount at the given shop.
|
private java.util.List<ProductAmount> |
getProductsAtShop(Shop shop)
Returns all the products that the purchaser will buy in a given shop during the best tour.
|
Position |
getStartPos() |
private void |
searchForBestTour()
Finds the best shops to buy all the products in the grocery list.
|
private static final int NUM_SHOP_LIMIT_WHERE_WE_STOP_FINDING_OPTIMAL_TOUR
private final GroceryList groceryList
private final java.util.List<Shop> shops
private final Position startPos
private final Position endPos
private final java.util.List<Position> bestTourPositions
private final java.util.Map<Shop,java.util.List<ProductAmount>> productsAtShop
private java.util.List<Shop> bestTourShops
private double bestDistance
public BestTourFinder(Position startPos, Position endPos, java.util.List<Shop> shops, GroceryList groceryList) throws NoShopHasThatProductException
It uses the Commodity Adding Heuristic (CAH) algorithm to select the shops and then tries to find the best route among those shops if the number of shops is small enough.
When the grocery list has a product that no shop has, NoShopHasThatProductException is thrown.
startPos
- endPos
- shops
- groceryList
- NoShopHasThatProductException
private void findBestRoute(java.util.Set<Shop> solution)
We use backtracking to find the optimal route.
solution
- private void findBestRouteUsingBacktrack(java.util.List<Shop> shopList, java.util.List<Shop> route, double distance)
shopList
- route
- distance
- private void searchForBestTour() throws NoShopHasThatProductException
If a product is present in no shop, NoShopHasThatProductException is thrown.
NoShopHasThatProductException
private Shop findBestShopForProduct(java.util.Set<Shop> solution, java.util.Set<Shop> remainingShops, ProductAmount productAmount) throws NoShopHasThatProductException
If no shop has the given product, NoShopHasThatProductException is thrown.
solution
- remainingShops
- productAmount
- NoShopHasThatProductException
private double getCostForProductInVisitedShop(ProductAmount productAmount, Shop shop)
productAmount
- shop
- private double getCostForProductInNewShop(ProductAmount productAmount, Shop shop, java.util.Set<Shop> solution)
productAmount
- shop
- private double getDistanceCostOfAddingShop(Shop shop, java.util.Set<Shop> solution)
For each pair of shops A and B, we find the cost of adding the new between in the tour shop A and B and return the minimum value.
shop
- solution
- private double distance(Position posA, Position posB)
posA
- posB
- private double getProductPriceAtShop(ProductAmount productAmount, Shop shop)
productAmount
- shop
- public java.util.List<Shop> getBestTourShops()
public java.util.List<Position> getBestTourPositions()
private java.util.List<ProductAmount> getProductsAtShop(Shop shop)
shop
- public BestTour getBestTour()
public Position getStartPos()
public Position getEndPos()