Дано: граф из 14 вершин с четным количеством ребер из каждой Начинаем и заканчиваем в точке А
Найти: кротчайший маршрут для объезда ПЯТИ любых точек (можно с учетом вершины, т.е. 4+А) 9 точек должны остаться нетронутыми
Актуальность: когда каждая точка имеет одинаковую ценность, а наша вместимость(например, если забираем груз) всего на 5 вершин тогда и потребуется рассчитать такой маршрут
Возможно, такая задача имеет другое название, но я ничего не нашел. Пожалуйста подскажите, как можно решить задачу такого вида, прикладываю набросок-пример, но и без него, кажется, все понятно (будущая матрица симметричная)
p.s. если это может оказаться принципиальным, то 14 вершин можно сократить до 8
Здравствуйте.
Дано: граф из 14 вершин с четным количеством ребер из каждой Начинаем и заканчиваем в точке А
Найти: кротчайший маршрут для объезда ПЯТИ любых точек (можно с учетом вершины, т.е. 4+А) 9 точек должны остаться нетронутыми
Актуальность: когда каждая точка имеет одинаковую ценность, а наша вместимость(например, если забираем груз) всего на 5 вершин тогда и потребуется рассчитать такой маршрут
Возможно, такая задача имеет другое название, но я ничего не нашел. Пожалуйста подскажите, как можно решить задачу такого вида, прикладываю набросок-пример, но и без него, кажется, все понятно (будущая матрица симметричная)
p.s. если это может оказаться принципиальным, то 14 вершин можно сократить до 8Erdman1900
Здравствуйте. Пяти ЛЮБЫХ не получится. Точки 11 и/или 2 уже будут включены в посещаемые. Останется посетить 2 или 3 точки. Они тоже известны: 9, 12, 13. Задача решена. Зависит ещё от того, можно ли дважды посещать одну точку. Если бы в условии стояло "найти оптимальный маршрут для посещения пяти ЗАДАННЫХ точек, проезжая сквозь остальные", то задача бы имела смысл. И по правилам надо приложить xls файл с "будущей матрицей".
Здравствуйте. Пяти ЛЮБЫХ не получится. Точки 11 и/или 2 уже будут включены в посещаемые. Останется посетить 2 или 3 точки. Они тоже известны: 9, 12, 13. Задача решена. Зависит ещё от того, можно ли дважды посещать одну точку. Если бы в условии стояло "найти оптимальный маршрут для посещения пяти ЗАДАННЫХ точек, проезжая сквозь остальные", то задача бы имела смысл. И по правилам надо приложить xls файл с "будущей матрицей".Светлый
Здравствуйте, спасибо за отклик. Да, я читал правила оформления темы. Проблема в том что я бы хотел понять алгоритм действий/узнать модель общего вида такой задачки. Т.е не совсем общего формулировка задачи именно такая, как я описал, но значения ребер и их количества могут отличаться
Здравствуйте, спасибо за отклик. Да, я читал правила оформления темы. Проблема в том что я бы хотел понять алгоритм действий/узнать модель общего вида такой задачки. Т.е не совсем общего формулировка задачи именно такая, как я описал, но значения ребер и их количества могут отличатьсяErdman1900