Привет ! Меня зовут Ксавье Жувено, и вот девятая часть длинной серии статей о Пришествии кода. Предыдущую часть можно найти здесь

В этом новом посте мы собираемся решить проблему от 9 декабря 2015 года под названием «Все за одну ночь». Решение я предложу на C++, но рассуждения можно применить и к другим языкам.

Часть 1

Проблема

Полную версию этой проблемы можно найти непосредственно на сайте Пришествие кода, здесь я опишу лишь суть проблемы:

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

Например, при следующих расстояниях:

London to Dublin = 464
London to Belfast = 518
Dublin to Belfast = 141

Самый короткий из них — London -> Dublin -> Belfast = 605, поэтому ответ — 605.

Решение

Итак, если мы удалим из этой задачи всю лексику Санты, нам нужно будет найти кратчайший путь в графе, проходящий через каждый узел только один раз. Но прежде всего нам нужно извлечь информацию для построения графика!

Чтобы извлечь города, я основывался на положении мира «в» и «=» и в итоге получил такой код:

std::pair<City, City> getCitiesFromInstruction (const std::string_view instruction)
{
  const auto citySeparatorPosition = instruction.find(" to ");
  const auto equalSeparatorPosition = instruction.substr(citySeparatorPosition+4).find(" = ");
  return std::make_pair(City(instruction.substr(0, citySeparatorPosition)), City(instruction.substr(citySeparatorPosition+4, equalSeparatorPosition)));
}

тогда как для расстояния между я использовал регулярное выражение, потому что почему бы и нет 😛

Distance getDistanceFromInstruction (const std::string& instruction) {
  std::regex word_regex("[0-9]+");
  auto words_begin = std::sregex_iterator(std::begin(instruction), std::end(instruction), word_regex);
  auto words_end = std::sregex_iterator();
  auto value{0};
  for (std::sregex_iterator i = words_begin; i != words_end; ++i)
  {
   std::smatch match = *i;
   return static_cast<Distance>(atoi(match.str().c_str()));
  }
  assert (false);
  return 0;
}

Теперь, когда у нас есть данные, мы можем сохранить их в графе перед поиском кратчайшего пути. Я не буду подробно описывать, какие классы я создал, я в основном сделал один класс для City, один для Distance, один для Route и один для Graph.

Давайте перейдем непосредственно к основному алгоритму!

Он состоит из двух функций: функция run, которая создаст элементы, которые нам понадобятся во второй функции, такие как отсортированный график, и некоторое хранилище для городов, которые мы посетили, и городов, которые нам еще предстоит посетить, перед вызовом второй функции. . Эта функция выглядит так:

Distance run()
{
  std::vector<Node> citiesToVisit, citiesVisited;
  std::sort(std::begin(sortedGraph), std::end(sortedGraph)); 
  citiesToVisit = sortedGraph;
  return travel (citiesToVisit, 0, citiesVisited);
}

Как видите, на данный момент города, которые мы должны посетить, состоят из отсортированного графа, а посещенные города пусты, так как мы еще не посетили ни один город. А вторая функция, как вы могли заметить, называется travel и принимает три аргумента: города, которые нам еще предстоит посетить, пройденное расстояние и города, которые мы уже посетили. Эта функция представляет собой рекурсивную функцию, в которой мы будем рассматривать каждую дорогу, проходящую через все города только один раз, вычислять пройденное расстояние и сравнивать с найденными кратчайшими расстояниями, пока не найдем кратчайший путь график.

Хватит болтать, давайте посмотрим на код!

Distance travel(const std::vector<Node>& citiesToVisit, Distance distanceTraveledUntilNow, const std::vector<Node>& citiesVisited)
{
  if(citiesToVisit.empty()) { return getRouteDistance(); }
  auto min = std::numeric_limits<Distance>::max();
  for(const auto& city : citiesToVisit)
  {
    std::vector<Node> citiesVisitedWithNewCity, citiesVisitedWithNewCitySorted, lastCitiesToVisit; 
    citiesVisitedWithNewCity = citiesVisited; 
    citiesVisitedWithNewCity.emplace_back(city); 
    citiesVisitedWithNewCitySorted = citiesVisitedWithNewCity; 
    std::sort(std::begin(citiesVisitedWithNewCitySorted), std::end(citiesVisitedWithNewCitySorted)); 
    std::set_difference(std::begin(sortedGraph), std::end(sortedGraph), std::begin(citiesVisitedWithNewCitySorted), std::end(citiesVisitedWithNewCitySorted), std::back_inserter(lastCitiesToVisit));
    const auto distanceTraveled = travel (lastCitiesToVisit, distanceTraveledUntilNow, citiesVisitedWithNewCity);
    min = std::min(min, distanceTraveled);
  }
  return distanceTraveledUntilNow + min + getRouteDistance();
}

Вау, это довольно большой кусок кода. Давайте объясним это понемногу. Во-первых, у нас есть:

if(citiesToVisit.empty()) { return getRouteDistance(); }

Это stopping criterion метода travel. Это условие позволяет остановить рекурсивный метод. Действительно, когда у нас больше нет городов для посещения, мы можем вернуть расстояние маршрута до двух последних посещенных городов с помощью метода getRouteDistance.

Затем у нас есть цикл for:

for(const auto& city : citiesToVisit)
{
 std::vector<Node> citiesVisitedWithNewCity, citiesVisitedWithNewCitySorted, lastCitiesToVisit; 
 citiesVisitedWithNewCity = citiesVisited;
 citiesVisitedWithNewCity.emplace_back(city); 
 citiesVisitedWithNewCitySorted = citiesVisitedWithNewCity; 
 std::sort(std::begin(citiesVisitedWithNewCitySorted), std::end(citiesVisitedWithNewCitySorted)); 
 std::set_difference(std::begin(sortedGraph), std::end(sortedGraph), std::begin(citiesVisitedWithNewCitySorted), std::end(citiesVisitedWithNewCitySorted), std::back_inserter(lastCitiesToVisit));
  const auto distanceTraveled = travel (lastCitiesToVisit, distanceTraveledUntilNow, citiesVisitedWithNewCity);
 // ....
}

Все эти манипуляции с контейнером и есть основная часть рекурсии! Это позволяет нам вызывать метод travel для вызова самого себя с одним пройденным городом, добавленным в контейнер уже пройденных городов, и уменьшить количество городов, которые еще предстоит посетить. Более того, цикл for делает это таким, как мы вызываем метод travel с разными наборами городов, в которые путешествовали, и в которые путешествовали, поскольку мы добавляем другой город из городов для путешествий в города, в которые путешествовали (я давал вам прочитать это несколько раз с тех пор, как это нелегко получить, если у вас нет оснований на рекурсивных методах).

Теперь, благодаря этому рекурсивному методу, мы сможем travel пройти по всем путям графа, которые проходят через каждый город только один раз. Все, что нам осталось сделать, это найти самую короткую. И вот для чего предназначена последняя часть функции travel:

auto min = std::numeric_limits<Distance>::max();
for(const auto& city : citiesToVisit)
{
  // ...
  const auto distanceTraveled = travel (lastCitiesToVisit, distanceTraveledUntilNow, citiesVisitedWithNewCity);
  min = std::min(min, distanceTraveled);
}
return distanceTraveledUntilNow + min + getRouteDistance();

Таким образом, каждый раз, когда функция путешествия возвращает расстояние (либо из-за того, что она достигла stopping criterion, либо из-за приведенного выше кода), мы проверяем, является ли это расстояние кратчайшим среди всех вызовов travel в цикле for. Как только цикл for завершается, у нас есть кратчайшее расстояние путей, за которым следует метод travel для этой точки в алгоритме, и мы можем вернуть пройденное расстояние, которое представляет собой сумму пройденного расстояния до этого момента (параметр функции travel ), кратчайший путь от методов travel, вызываемых в цикле for, и расстояние между двумя последними посещенными городами.

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

А теперь давайте посмотрим, что нам приготовила вторая часть 😃

Часть 2

Проблема

Зачем идти по кратчайшему пути, если можно выбрать самый длинный? Разве путешествие не важнее пункта назначения? 😉

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

Решение

Все точно так же, кроме одной строчки! Знаете какой?

… (музыка опасности)

Такая интрига (а может и нет 😆), так что строка, которую нужно изменить, это та, которая вычисляет мин. Действительно, изменение этого вызова на std::max вместо std::min отлично справляется со своей задачей. Я рад, что это было так легко, так как первая часть была совсем не легкой!

И если мы хотим, чтобы наша переменная называлась правильно, в итоге последняя часть кода будет выглядеть так:

auto max = std::numeric_limits<Distance>::max();
for(const auto& city : citiesToVisit)
{
  // ...
  const auto distanceTraveled = travel (lastCitiesToVisit, distanceTraveledUntilNow, citiesVisitedWithNewCity);
  max = std::max(max, distanceTraveled);
}
return distanceTraveledUntilNow + max + getRouteDistance();

И вот оно, решение второй части 😄

Вывод

Вы можете заметить, что решения, написанные в этом посте, включают не все исходники для создания работающих программ, а только интересную часть исходников для решения этой проблемы. Если вы хотите увидеть программы от начала до конца, вы можете зайти на мою учетную запись GitHub, изучить полное решение, добавить комментарии или задать вопросы, если хотите, на платформе, на которой вы читаете эту статью, она также поможет мне. улучшить качество моих статей.

Вот список стандартных методов, которые мы использовали, я не могу убедить вас взглянуть на их определения:

Спасибо, что читаете, надеюсь, вам понравилось 😃

И до следующей части, получайте удовольствие, учась и развиваясь.

Первоначально опубликовано на http://10xlearner.com 2 сентября 2019 г.