Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Задача коммивояжера не проходя все вершины - Мир MS Excel

Регистрация · Логин: · Пароль: · · Забыли пароль?
Страница 1 из 11
Модератор форума: _Boroda_, Pelena, Manyasha, SLAVICK 
Мир MS Excel » Вопросы и решения » Вопросы по Excel » Задача коммивояжера не проходя все вершины (Формулы/Formulas)
Задача коммивояжера не проходя все вершины
Erdman1900 Дата: Пятница, 28.04.2017, 01:27 | Сообщение № 1
Группа: Пользователи
Ранг: Прохожий
Сообщений: 2
Репутация: 0 ±
Замечаний: 0% ±

Excel 2013
Здравствуйте.

Дано:
граф из 14 вершин с четным количеством ребер из каждой
Начинаем и заканчиваем в точке А

Найти: кротчайший маршрут для объезда ПЯТИ любых точек (можно с учетом вершины, т.е. 4+А)
9 точек должны остаться нетронутыми

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

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

p.s. если это может оказаться принципиальным, то 14 вершин можно сократить до 8
К сообщению приложен файл: 1575851.jpg(27Kb)
 
Ответить
СообщениеЗдравствуйте.

Дано:
граф из 14 вершин с четным количеством ребер из каждой
Начинаем и заканчиваем в точке А

Найти: кротчайший маршрут для объезда ПЯТИ любых точек (можно с учетом вершины, т.е. 4+А)
9 точек должны остаться нетронутыми

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

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

p.s. если это может оказаться принципиальным, то 14 вершин можно сократить до 8

Автор - Erdman1900
Дата добавления - 28.04.2017 в 01:27
Светлый Дата: Пятница, 28.04.2017, 07:39 | Сообщение № 2
Группа: Проверенные
Ранг: Обитатель
Сообщений: 270
Репутация: 63 ±
Замечаний: 0% ±

Excel 2007
Здравствуйте.
Пяти ЛЮБЫХ не получится. Точки 11 и/или 2 уже будут включены в посещаемые.
Останется посетить 2 или 3 точки. Они тоже известны: 9, 12, 13. Задача решена.
Зависит ещё от того, можно ли дважды посещать одну точку.
Если бы в условии стояло "найти оптимальный маршрут для посещения пяти ЗАДАННЫХ точек, проезжая сквозь остальные", то задача бы имела смысл.
И по правилам надо приложить xls файл с "будущей матрицей".


Программировать проще, чем писать стихи.
 
Ответить
СообщениеЗдравствуйте.
Пяти ЛЮБЫХ не получится. Точки 11 и/или 2 уже будут включены в посещаемые.
Останется посетить 2 или 3 точки. Они тоже известны: 9, 12, 13. Задача решена.
Зависит ещё от того, можно ли дважды посещать одну точку.
Если бы в условии стояло "найти оптимальный маршрут для посещения пяти ЗАДАННЫХ точек, проезжая сквозь остальные", то задача бы имела смысл.
И по правилам надо приложить xls файл с "будущей матрицей".

Автор - Светлый
Дата добавления - 28.04.2017 в 07:39
Erdman1900 Дата: Пятница, 28.04.2017, 15:39 | Сообщение № 3
Группа: Пользователи
Ранг: Прохожий
Сообщений: 2
Репутация: 0 ±
Замечаний: 0% ±

Excel 2013
Здравствуйте, спасибо за отклик.
Да, я читал правила оформления темы. Проблема в том что я бы хотел понять алгоритм действий/узнать модель общего вида такой задачки.
Т.е не совсем общего формулировка задачи именно такая, как я описал, но значения ребер и их количества могут отличаться
 
Ответить
СообщениеЗдравствуйте, спасибо за отклик.
Да, я читал правила оформления темы. Проблема в том что я бы хотел понять алгоритм действий/узнать модель общего вида такой задачки.
Т.е не совсем общего формулировка задачи именно такая, как я описал, но значения ребер и их количества могут отличаться

Автор - Erdman1900
Дата добавления - 28.04.2017 в 15:39
Мир MS Excel » Вопросы и решения » Вопросы по Excel » Задача коммивояжера не проходя все вершины (Формулы/Formulas)
Страница 1 из 11
Поиск:

Яндекс цитирования
© 2010-2017 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!