Skip to content

Latest commit

 

History

History

practice_2.3

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
analysis.ipynb
analysis.ipynb
 
 
data.csv
data.csv
 
 

README.md

Практическая работа №8 "Задача коммивояжера"

Разработать алгоритм решения задачи коммивояжера.

Испытать свой алгоритм на населенных пунктах Сибирского Федерального Округа.

Рассматриваются только города, села, деревни и поселки. Всего 9629 населенных пунктов.

Ссылка на соревнование: https://www.kaggle.com/c/tsp-russian-cities

Карта

Крупная карта

Алгоритмы:

Разрешены любые способы решения задачи коммивояжера, например:

  • Муравьиный алгоритм
  • Генетический алгоритм
  • Рой частиц
  • Гравитационный поиск
  • Метод ветвей и границ
  • и другие

Требования к реализации

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

Расстояние между населенными пунктами рассчитывается как евклидово расстояние между точками.

Входные и выходные данные

В качестве данных используется населенные пункты типа "город", "село", "деревня", "поселок" Сибирского Федерального Округа с населением более 100 человек. Набор данных из 6145 населенных пунктов вы найдете в файле data.csv. Его структура состоит из следующих столбцов:

  • id - порядковый номер (целое число)
  • region - Регион (строка с пробелами)
  • municipality - Муниципальный район (строка с пробелами)
  • settlement - Наименование населенного пункта (строка с пробелами)
  • type - тип: г - город, с - село, п - поселок, д - деревня (строка)
  • latitude_dd - десятичное представление географических координат широты (целое число)
  • longitude_dd - десятичное представление географических координат долготы (целое число)

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

Пунктом отправления считать Красноярск, в data.csv его id равен 3753.

Первые 5 строк файла data.csv:

id;region;municipality;settlement;type;latitude_dd;longitude_dd
0;Республика Алтай;Шебалинский район;Каспа;с;5111;8601
1;Алтайский край;Смоленский;Молочный;п;5241;8497
2;Красноярский край;Казачинский район;Отношка;с;5738;9270
3;Республика Тыва;Каа-Хемский кожуун;Кундустуг;с;5157;9518

Пример визуализации набора данных приведен в файле analysis.ipynb. Для его запуска вам потребуется установить библиотеки pandas и folium.

Выходными данными должен быть файл с расстояниями между населенными пунктами в порядке их прохождения. Например, если первая поездка должна быть из Красноярска с координатами (5601;9285) в Петропавловку с координатами (5661;9621), то результирующий файл solution.csv должен содержать строку 0;341.3151036798694. Таким образом, для 6145 населенных пунктов должно получиться 6144 расстояния. Расстояние между населенными пунктами рассчитывается как евклидово расстояние между точками.

Полезные материалы