Вспоминаем графы

Прикольно. Максимальную скорость тоже можно учитывать, чтобы найти кратчайший или быстрейший?

Скорость в графах будет учитываться, если в веса рёбер писать не расстояние, а время.

Не получается пока посчитать, как объехать все областные центры (30 штук) затратив при этом минимальное расстояние.

DFS?

Задача коммивояжёра в общем случае NP полна и в случае более-менее большого количества пунктов (66 вроде как уже абсолютно неразумное число для обычной задачи на пару миллиардов лет на суперкомпьютере, подзадачи как у тебя ХЗ, но тоже много) и дорог решается либо приблизительно (эмпирически), либо никак (времени и ресурсов надо очень много). С clips не работал, так что кроме теории ничего тебе не подскажу.

с помощью экспертной системы

https://www.clipsrules.net

CLIPS
A Tool for Building Expert Systems

Developed at NASA’s Johnson Space Center from 1985 to 1996, the C Language Integrated Production System (CLIPS) is a rule‑based programming language useful for creating expert systems and other programs where a heuristic solution is easier to implement and maintain than an algorithmic solution. Written in C for portability, CLIPS can be installed and used on a wide variety of platforms. Since 1996, CLIPS has been available as public domain software.

Что-то мне говорит, что ты бредишь. Может быть у вас на олимпиаде-физмате и нерешаемо на суперкомпьютера, а у дистрибутеров - 66 пунктов доставки это просто шутка, а не работа.

Ну в реальности маршрутных листов на 66 точек не бывает, в день до восьми самое большее. У курьеров на пицце тоже три-четыре точки враз.

Ну так ты ж маршрут не на день планируешь, а на месяц (а кого-то нужно и 2-3 раза объехать) в чтоб всех клиентов объехать. Не так?

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

решается либо приблизительно

Ну там же единицы процентов разницы с идеальным решением. Поиск идеала того не стоит.

Сказали ж, суперкантуперы не справятся :)

Так ведь это правда: с поиском точного решения не справятся.

Им не обязательно находить кратчайший путь, чтобы всё работало. Они могут использовать всякие эвристики (типа не ездить из Владивостока в Хабаровск через Москву) дающие просто достаточно хороший путь. NP-полная задача именно поиска кратчайшего пути на произвольном графе.

Ну так я не весь маршрут сразу на месяц планирую ведь, он разбивается на дневные и по географическим зонам.

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

у дистрибутеров - 66 пунктов доставки это просто шутка, а не работа

Быстрые и простые эвристики:

Жадный алгоритм ближайшего соседа (Nearest Neighbor)

Выбираем случайную точку, на каждом следующем шаге выбираем ближайшую не посещённую точку.

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

Алгоритм вставки (Insertion Heuristics)

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

Алгоритм Кристофидеса (Christofides Algorithm)

Строим минимальное остовное дерево, находим паросочетание нечётных вершин, объединяем их в эйлеров цикл, затем преобразуем его в гамильтонов цикл. Гарантируется, что результат будет не менее чем в 1,5 раза хуже оптимального.

Более сложные метаэвристики:

Имитация отжига (Simulated Annealing)

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

Генетические алгоритмы (Genetic Algorithms)

Создаём популяцию из случайных маршрутов. «Скрещиваем» лучшие маршруты, например, комбинируя их части в один дочерний, применяем случайные «мутации». Отбираем наиболее «приспособленные» для следующего поколения.

Муравьиные алгоритмы (Ant Colony Optimization)

Моделируем поведение муравьёв, ищущих пищу. «Муравьи» строят маршруты, предпочитая рёбра с большим количеством «феромонов», которые откладываются «муравьями», нашедшими более короткие пути.

Также существуют продвинутые специализированные решатели (например, Concorde TSP Solver). Выдают гарантированно оптимальный результат, но заточены на географический контекст задачи.

Фубунту

Прозрачность в терминале не мешает?

Обычно единицы процентов разницы. В худшем случае из Москвы в Питер будет маршрут через Владивосток. Но такое крайне редко бывает.

Прозрачность в терминале не мешает?

Нет

Алгоритм Дейкстры

Алису поставь себе, она тебе посчитает и ещё отсо& т.

Расстояние невозможно «затратить».

как объехать все областные центры (30 штук)

Это не на графы задача, а на линейную оптимизацию.
Задача коммивояжера

В худшем случае из Москвы в Питер будет маршрут через Владивосток. Но такое крайне редко бывает.

В реальности бывают важные условия. Например, общественным транспортом из Ярославля во Владимир быстрее добраться через Москву (270 км + 180 км, две «Ласточки», 3 ч + 1ч 40 мин), чем напрямую (220 км, автобус идет 5 часов).

Собственно, Золотое Кольцо общественным транспортом - это в принципе NP-полный [опущен очевидный эпитет].

А это зависит от того что в рёбра графа писать - время или расстояние.

В реальной задаче будет несколько факторов.

Народ из какого-нибудь Омска может летать в Тай через Москву, например. Потому что {список проблем, которые проще решить так}.