Алгоритм: задача коммивояжера собирать предметы - PullRequest
Новая
       39

Алгоритм: задача коммивояжера собирать предметы

0 голосов
/ 02 февраля 2020

У меня вопрос о коммивояжере. У меня есть матрица расстояний между городами. В каждом городе разное количество пива. Мне нужно собрать как можно больше предметов и вернуться к исходной точке. У меня есть машина, которая может проехать 1000 км. Может ли кто-нибудь помочь с этим? Есть идеи? 

    List<BreweryCodes> breweryList = new ArrayList<>();

    for (BreweryCodes brewery : breweryCodesService.getAllBreweryCodes()) 
    {
        // we calculate distance between home and breweries
        double distanceToHome = BeerUtils.haversine(myCoordinates, brewery);

        // collecting breweries that fit by the distance
        if (distanceToHome <= BeerUtils.MAX_DISTANCE / 2d) 
        {
            breweryList.add(brewery);
        }
    }

    int beerCount = 0;
    List<Long> result = new ArrayList<>();
    TravelInfo home = new TravelInfo(Arrays.asList(0L), 0, 0);
    home.setLatitude(myCoordinates.getLatitude());
    home.setLongitude(myCoordinates.getLongitude());

    Stack<TravelInfo> stack = new Stack<>();
    stack.add(home);

    while (!stack.isEmpty()) 
    {
        TravelInfo currentPoint = stack.pop();
        List<Long> breweryIds = currentPoint.getBreweries();

        for (BreweryCodes nextBrewery : breweryList) 
        {
            if (breweryIds.contains(nextBrewery.getBreweryId())) 
            {
                continue;
            }

            double distanceToHome = BeerUtils.haversine(myCoordinates, nextBrewery);
            double distanceBetween = BeerUtils.haversine(currentPoint, nextBrewery) + currentPoint.getTraveledDistance();

            if ((distanceBetween + distanceToHome) <= BeerUtils.MAX_DISTANCE) 
            {
                List<Long> ids = new ArrayList<>(breweryIds);
                ids.add(nextBrewery.getBreweryId());

                TravelInfo travel = new TravelInfo(ids, 0, distanceBetween);
                travel.setLatitude(nextBrewery.getLatitude());
                travel.setLongitude(nextBrewery.getLongitude());

                beerCount = currentPoint.getBeerCount() + nextBrewery.getBeerCount();
                travel.setBeerCount(beerCount);

                stack.push(travel);
            } 
            else 
            {
                System.out.println(currentPoint.getBreweries() + "          " + beerCount);
            }
        }
    }
...