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

Решение проблемы начинается с формулировки проблемы. Если мы посмотрим на задачу коммивояжера (TSP), постановка задачи состоит в том, чтобы найти кратчайший путь из известных городов с их расстояниями, где каждый город нужно посетить ровно один раз и вернуться обратно в ту же точку. Это пример задачи, которую мы здесь используем. И говорят, что цель достигнута, когда у нас есть работоспособный код, решающий проблему.

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

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

Шаги:

  1. Пример работы вручную
  2. Запишите, что вы сделали
  3. Найдите закономерности
  4. Проверить вручную
  5. Перевести в код
  6. Запуск тестовых случаев
  7. Отладка неудачных тестов

Шаг 1. Пример работы вручную

Первый подход, который мы собираемся сделать, — это взять небольшой экземпляр. В задаче TSP мы возьмем небольшой пример, то есть посетим пару городов и просуммируем их расстояние для расчета маршрута.

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

Шаг 2. Запишите, что вы сделали

После завершения первого шага мы запишем шаги, которые мы сделали на шаге 1. То есть вы дадите кому-то указания по решению этого экземпляра проблемы. Основная идея написания этого состоит в том, чтобы отразить обоснование ответа, который мы придумали для конкретного случая проблемы.

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

Шаг 3. Найдите закономерности

Шаг 3 посвящен поиску шаблонов. Так как мы хотим написать алгоритм для любого экземпляра проблемы, а не только для конкретного экземпляра, над которым мы работали. Здесь мы будем думать о повторении. То, что мы делали снова и снова, в разное время и при разных условиях, приведет нас к циклам и условным конструкциям. Эти условия или зацикливание могут быть следствием увеличения поступления частиц, и мы должны думать и об этом.

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

Шаг 4. Проверка вручную

Как только мы закончим с шагом 3, мы хотим проверить алгоритм вручную. Алгоритм, который мы придумали, может содержать ошибки. Возможно, мы поняли, что что-то произошло в конкретном случае или оставило значение, характерное для выбранных нами параметров. Если есть какие-либо ошибки, мы хотели бы найти их, прежде чем мы начнем переводить наш алгоритм в код. По этой причине мы собираемся проверить один или несколько входов с управляемым размером, который можно сделать вручную.

1) Consider city 1 as the starting and ending point.

2) Generate all (n-1)! Permutations of cities. 

3) Calculate the cost of every permutation and keep track of the minimum cost permutation. 

4) Return the permutation with minimum cost.

Шаг 5. Преобразование в код

Когда мы уверены в нашем алгоритме, мы начинаем переводить его в код. Здесь происходит фактическое кодирование. Реализация нашего алгоритма показана здесь с помощью JavaScript.

   /* 
    Code taken from https://www.geeksforgeeks.org/
    travelling-salesman-problem-using-dynamic-programming/
   */

   const n = 4; // four nodes in example graph
   let MAX = 1000000; // give appropriate maximum to avoid overflow
 
   // dist[i][j] represents shortest distance to go from i to j
   // this matrix can be calculated for any given graph using
   // all-pair shortest path algorithms
   let dist = [
     [0, 0, 0, 0, 0], [0, 0, 10, 15, 20],
     [0, 10, 0, 25, 25], [0, 15, 25, 0, 30],
     [0, 20, 25, 30, 0],
   ];
 
   // memoization for top down recursion
   let memo = new Array(n + 1);
   for (let i = 0; i < memo.length; i++) {
     memo[i] = new Array(1 << (n + 1)).fill(0)
   }
 
   function fun(i, mask) 
   {
     
     // base case
     // if only ith bit and 1st bit is set in our mask,
     // it implies we have visited all other nodes already
     if (mask == ((1 << i) | 3))
       return dist[1][i];
         
     // memoization
     if (memo[i][mask] != 0)
       return memo[i][mask];
 
     let res = MAX; // result of this sub-problem
 
     // we have to travel all nodes j in mask and end the
     // path at ith node so for every node j in mask,
     // recursively calculate cost of travelling all nodes in
     // mask except i and then travel back from node j to
     // node i taking the shortest path take the minimum of
     // all possible j nodes
 
     for (let j = 1; j <= n; j++)
       if ((mask & (1 << j)) && j != i && j != 1)
         res = Math.min(res, fun(j, mask & (~(1 << i)))
           + dist[j][i]);
     return memo[i][mask] = res;
   }
     
   // Driver program to test above logic
   let ans = MAX;
   for (let i = 1; i <= n; i++)
     
     // try to go from node 1 visiting all nodes in
     // between to i then return from i taking the
     // shortest route to 1
     ans = Math.min(ans, fun(i, (1 << (n + 1)) - 1)
       + dist[i][1]);
 
   console.log("The cost of most efficient tour " + ans);

Шаг 6. Запуск тестовых случаев

После того, как мы напишем наш код, мы хотим запустить тестовые примеры, чтобы убедиться, что написанная нами программа получает ответ, основанный на том, что мы ожидаем от правильного ответа, зная, какую проблему мы пытаемся решить. Каждый раз, когда мы запускаем тестовый пример, правильный ответ, который мы получаем, придаст нам больше уверенности в нашей программе. Если это не удается, мы переходим к шагу 7, отлаживая неудачные случаи.

Шаг 7. Отладка неудачных тестов

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

В конечном счете, если мы столкнемся с алгоритмической проблемой, мы вернемся к шагу 3 и исправим ее. В случае, если наш алгоритм не может быть переведен в код (проблема реализации), мы вернемся к шагу 5 и исправим наш перевод нашего алгоритма в код.

Заключение

В результате реализации нашей программы мы обнаружили, что путь 1–2–4–3–1 экономически эффективен, а стоимость тура составляет 80, что верно. Используя семиэтапный подход, показанный выше, мы решаем проблему TSP и можем использовать его в качестве руководства для решения других задач программирования.