Время на проход ледовых полей

#алгоритм

На собеседовании дали задачку для решения на любом языке за 1 час. Я не сумел уложиться
в 1 час. :( Очень бы хотелось узнать решения коллег и время решения ими задачи.

Группа из n кораблей должна пройти через ледовые поля. В группе один ледокол, за
которым может идти только один корабль без ледовой защиты и один корабль с ней, поэтому
тактика прохода через поля такая: ледокол проводит один из кораблей без защиты и один
корабль с ней, потом защита ставится на один из кораблей и ледокол возвращается с ним.
 Время прохода пары определяется кораблем с наименьшей скоростью.
Требуется найти наименьшее время, за которое группа пройдет ледовые поля.
Исходные данные: n - количество кораблей, v[n] - массив времен на прохождение кораблями
полей.

Пример: 4 корабля. Время прохода: 1, 10, 5, 2. Общее время: 17. Ниже движение кораблей.
1 2 5 10   ||              = 0
5 10       ->   1 2        = 2
1 5 10     <-   2          = 3
1          ->   5 10 2     = 13
1 2        <-   5 10       = 15
           ->   1 2 5 10   = 17
    

Ответы

Ответ 1

Правильную тактику расписал @Fiztex: сначала выбираем пару самых быстрых кораблей
- они будут таскать экран обратно. Далее алгоритм следующий:

Переправляем пару быстрых
Если все корабли перевезены, то задача выполнена, иначе идем к п.3
Первого быстрого (любого из пары быстрых) возвращаем
Переправляем пару самых медленных
Второго быстрого (оставшегося из пары быстрых) возвращаем
Переходим к п.1

Соответственно, что бы рассчитать минимальное время, можно сделать следующее:

Отсортировать все корабли по скорости
Разбить все корабли по парам начиная с самых медленных (pairs)
Выделить из каждой пары самый медленный корабль - это и будет скорость пары
Первая пара - это перевозчики щита (fast_ships)
Соответственно конечная формула будет: sum(max(pair)) + ((sum(fast_ships) + max(fast_ships))
* (len(pairs) - 1))

Пример программы на питоне:
import sys

if len(sys.argv) < 2:
    print('Usage: %s ship1 ship2 shipN' % sys.argv[0])
    exit(1)

try:
    ships = map(int, sys.argv[1:])
except ValueError:
    print('Incorrect input')
    exit(1)

ships.sort()

fast_ships, ships = ships[:2], ships[2:]
pairs = [ships[max(0, i-2):i] for i in range(len(ships), 0, -2)]
best_time = sum([max(pair) for pair in pairs]) + max(fast_ships) + (sum(fast_ships)
+ max(fast_ships)) * (len(pairs))

print('Best time: %d' % best_time)

.
$ python ships.py 10 5 2 1
Best time: 17

PS Примечательно, что точно такая же задача была в космических рейнджерах :) Даже
цифры в примере те-же самые.


Ответ 2

Мне кажется, что надо балансировать между двумя тактиками, на каждом шаге, выбирая
оптимальную:
Тактика 1:
Переправляем сначала два самых быстрых, соответственно один из них возвращаем. Затем
переправляем два самых медленных, возвращаем второй из самых быстрых. Далее опять переправляем
оба самых быстрых, один из них возвращаем. Далее переправляем два самых медленных из
оставшихся, возвращаем второй из самых быстрых и т.д. 
Тактика 2:
Переправляем самый быстрый с самым медленным, самый быстрый возвращаем. Далее снова
самый быстрый с самым медленным из оставшихся и т.д.
Строго пока не доказал.
А вообще можно в любом случае написать решение на основе динамического программирования,
хотя оно, судя по всему, будет далеко не оптимальным.


Ответ 3

Вопрос актуальность утратил, по-видимому, но алгоритм может быть полезен кому-то
  function iceFieldTime(mas) {
    // Вырожденные случаи
    if (mas.length == 0) return 0;
    if (mas.length == 1) return mas[0];

    // Сортируем корабли по времени
    mas.sort(function (a, b) {
      return a - b;
    });

    // Самые быстрые корабли - "драйверы", driver1 - быстрый, driver2 - медленный
    var driver1 = mas.shift();
    var driver2 = mas.shift();

    // Время на перегон драйверов через поле
    var time = driver2;

    // В случае нечетного числа кораблей добавляем время на перегон быстрого драйвера
на исходную и обратно через поле с самым быстрым из оставшихся кораблей
    if (mas.length % 2 == 1) time += mas.shift() + driver1;

    // Осталось перегнать четное число кораблей, перегоняем их по парам
    while (mas.length > 0) {
      // Перегоняем быстрый драйвер с защитой на исходную позицию
      if (mas.length > 0) time += driver1;

      // Добавляем время на перегон самого медленного
      var ship1 = mas.pop();
      time += ship1;

      // В зависимости от минимального времени, 
      // либо перегоняем второй корабль пары с самым медленным 
      // и потом два раза медленный драйвер за быстрым (driver2 * 2),
      // либо перегоняем второй корабль с быстрым драйвером (driver1 + ship2)
      var ship2 = mas.pop();
      time += driver2 * 2 < driver1 + ship2 ? driver2 * 2 : driver1 + ship2;
    };
    return time;
  }


Ответ 4

@Fiztex предложил две тактики и правильный ответ для произвольных скоростей будет
их комбинацией.
Надо исходить из того за какое время можно перевезти два корабля (при этом ледокол
и броня должны оказаться в исходной точке), т.е. задача делится на перевоз пар самых
медленных кораблей. NB: Если останется один медленный корабль (плюс два быстрых), он
перевозится одним способом - с помощью самого быстрого. Два быстрых перевозятся за
одну ходку.
Перевезти два корабля можно двумя способами, один из них будет оптимальным, его и
надо выбрать. Пусть у нас есть 4 корабля в начальной точке. a,b,c,d - их время поездки,
отсортированы они так: a 2; i -= 2) {
    result += Math.min(2 * v[0] + v[i - 1] + v[i], v[0] + 2 * v[1] + v[i]);
}
if (i == 2) {
    result += v[0] + v[2];
}
result += v[1];
alert(result); // 119


Ответ 5

Fiztex, считаю, что тактика 2 действительно верная. Предлагаю доказательство.
"Туда"
Так как в любом случае придется переправить все корабли, то суммарное время "туда"
будет никак не меньше просто суммы подолжительностей для всех кораблей (с поправкой
на скорость ледокола разумеется: связка со скоростным кораблём всё равно не может двигаться
быстрее ледокола). При этом ясно, что минимизировать время "туда" действительно возможно:
из двух кораблей кроме ледокола оставлять на той стороне следует более медленный, в
этом случае он больше нигде нас не затормозит.
"Обратно"
Теперь становится ясно, что как-то улучшить общее время можно именно здесь. Задача
путешествия "обратно" - в наименьшее время вернуть ледовую защиту для следующего рейса.
Понятно, что наименьшее время будет, если скорость корабля, несущего защиту, будет
наибольшей.
Итак, тактика действительно проста: ледокол и самый быстрый корабль по очереди перевозят
оставшиеся. Можно даже указать суммарное время при этом:
T = Sum(i:=1..n-1; min(t;v[i])) + (n-1)*min(t;v[0]), где

t - время ледокола
v[0] - время самого быстрого корабля (просто для удобства, пусть он будет первым
в массиве)


Ответ 6

Не обращайте внимания на переменные функций, моя теория такая, 3 корабля проходят
поле, при этом время в любом случае определяется кораблем с наименьшей скоростью, обратно
едут 2 корабля, вот здесь второй корабль либо быстрый либо нет, поэтому для обратной
пути определяем корабль с наибольшей скоростью так как надо вычислить наименьшее возможное
время. Потом берем следующий корабль и считаем снова. По моему не важно в каком порядке
брать корабли из списка, можно по очереди...
function min(v[1],v[2],v[3]) {
    if(v[1] + v[2] > v[2] + v[3]) {
        if(v[2] > v[3]) {
            return v[3];
        }
        else {
            return v[2];
        }
    }
    else {
        if(v[1] > v[2]) {
            return v[3];
        }
        else {
            return v[2];
        }
    }    
}

function big(v[1],v[2],v[3]) {
    if(v[1] + v[2] > v[2] + v[3]) {
        if(v[1] > v[2]) {
            return v[1];
        }
        else {
            return v[2];
        }
    }
    else {
        if(v[2] > v[3]) {
            return v[2];
        }
        else {
            return v[3];
        }
    }    
}

total= 0;

for (i = 1; i < n.length; i = i + 1) {
    summa = v[i] + v[i + 1] + v[i + 2];
    min =  min(v[i],v[i + 1],v[i + 2]); 
    big = big((v[i],v[i + 1],v[i + 2]);
    middle = summa - (min + big);
    TimeForOneTeam = big + middle;
    total = total + (TimeForOneTeam);
}


Ответ 7

Если в задаче именно такое условие:
    В группе один ледокол, за которым может идти только один корабль без ледовой
защиты и один корабль с ней...

То, думаю, тут нет особого "размаха" для поиска наиболее верной тактики - здесь она
одна - та, которую вы описали. А вот если бы можно было, например, ледоколу вести за
собой два защищенных корабля, а потом забирать у них броню и возвращаться за незащищенными,
то тут бы уже было поинтересней( и побыстрее ). Еще было бы интереснее, если можно
было бы вести за собой более двух кораблей.

А вообще, зачем ледоколу гонять туда-сюда - ведь лед-то после первого его прохода
"туда" уже расколот, а, следовательно, по расколу уже в обратную сторону можно пускать
простые корабли с защитой(точнее один корабль, который шел за ледоколом с защитой) =)