Проблема минимизации роботов и контейнеров, необходим подход - PullRequest
Новая
       39

Проблема минимизации роботов и контейнеров, необходим подход

0 голосов
/ 29 декабря 2018

Учитывая эту проблему :

У вас есть склад с М контейнерами, заполненными бесконечным количеством конфет.Контейнеры расположены в один ряд, на одинаковом расстоянии друг от друга.У вас также есть 2 робота, которые могут забрать 1 конфету и транспортировать ее между любыми двумя контейнерами.

Роботы принимают инструкции в форме запросов, состоящих из двух целых чисел, Ma и Mb, соответственно.Чтобы выполнить запрос, робот перемещается к контейнеру Ma, берет 1 конфету, транспортирует ее в контейнер Mb, а затем останавливается на Mb, пока не получит другой запрос.

Рассчитайте минимальное общее расстояние, на которое роботы должны пройтивыполняйте N запросов по порядку.

Примечание: вы выбираете, какой робот выполняет каждый запрос.

Сначала я предполагал, что должен просто выбрать робота, который ближе к выполнению перемещения,но этот подход не работает в некоторых тестовых случаях, может кто-нибудь объяснить, почему этот подход не подходит для всех случаев, и каков правильный подход, спасибо.

Пример ввода и ожидаемый результат здесь .

Ответы [ 2 ]

0 голосов
/ 05 сентября 2019

Рабочий код с использованием динамического программирования (как объяснил Аурел Били) в C ++: 

#include <bits/stdc++.h>
using namespace std;
vector <pair <int,int > > input;
int dp[1002][1002];
int m,n;
int dis(int a,int b)
{
    if(a == 0) return abs(input[b-1].first-input[b-1].second);
    return abs(input[a-1].second-input[b-1].first)+abs(input[b-1].first-input[b-1].second);
}
int func(int i,int j)
{
    if(i+1 == n+1 || j+1 == n+1)
    {
        return 0;
    }
    //cout<<i<<" "<<j<<endl;
    if(dp[i][j] != -1)
     return dp[i][j];
    int result = INT_MAX;
    result = min(func(i,j+1)+dis(j,j+1),func(j,j+1)+dis(i,j+1));
    return dp[i][j] = result; 
}
int main()
{
    int t;cin>>t;
    while(t--)
    {
        cin>>m>>n;
        input.clear();
        input.resize(n);
        for(int i=0;i<n;i++)
        {
            int a,b;
            cin>>a>>b;
            input[i] = make_pair(a,b);
        }
        memset(dp,-1,sizeof(dp));
        int first = abs(input[0].first-input[0].second);
       // int second = abs(input[1].first-input[1].second);
        int val = func(0,1)+first;
        cout<<val<<endl;
    }
    return 0;
}
0 голосов
/ 29 декабря 2018

Проблема в категории «Динамическое программирование», и вы сами отметили свой вопрос greedy (ваш подход действительно жадный).Будут случаи, когда минимальное расстояние для данного запроса (локальный минимум) не является оптимальным для полного набора запросов (глобальный минимум).Следовательно, вам необходимо учитывать все возможные назначения роботов для запросов, но с помощью методов DP это не исчерпывающий поиск.

Я не хочу подробно описывать точное решение для вас, поскольку в Интернете имеется множество ресурсов.на DP (составьте двумерную таблицу затрат, перемещаясь по столбцам = робот 1, перемещаясь по рядам = робот 2, найдите оптимальный путь через таблицу…).Но я хочу показать вам пример ситуации, когда жадный подход является неоптимальным.

  • A робот 1
  • B робот 2
  • F начальная точка запроса
  • T конечная точка запроса

Решено с использованием жадного подхода: 

 (A)                  B
1 . . F . T . . . . . . // A is closer to F, travels 2 (to F) + 2 (to T) = 4
         (A)          B
2 . . . . . . F . T . . // A is closer to F, travels 2 (to F) + 2 (to T) = 4
                 (A)  B
3 F T . . . . . . . . . // A is closer to F, travels 8 (to F) + 1 (to T) = 9
    A                 B

Общее пройденное расстояние: 4 + 4 + 9 = 17.

Оптимальный подход (может быть несколько): 

 (A)                  B
1 . . F . T . . . . . . // A takes query, travels 2 (to F) + 2 (to T) = 4
          A          (B)
2 . . . . . . F . T . . // B takes query, travels 4 (to F) + 2 (to T) = 6
         (A)      B
3 F T . . . . . . . . . // A takes query, travels 4 (to F) + 1 (to T) = 5
    A             B

Общее пройденное расстояние: 4 + 6 + 5 = 15.

Обратите внимание, что B взял второй запрос дажехотя это было не ближе всего к начальной точке.

...