|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
01.12.2022, 14:17 | #1 |
Пользователь
Регистрация: 01.12.2022
Сообщений: 18
|
Реализовать метод ветвей и границ
помогите написать программу по псевдокоду
Реализовать алгоритм, находящий оптимальное (точное) решение задачи коммивояжера с помощью метода ветвей и границ. Решение методом ветвей и границ: Код:
graph.h Код:
Код:
|
08.12.2022, 12:41 | #2 |
Пользователь
Регистрация: 01.12.2022
Сообщений: 18
|
Решение методом ветвей и границ:
Length(Path) - возвращает длину маршрута Path MinPath(P1, P2) - из двух маршрутов возвращает кратчайший маршрут LowerBound(G, S) - возвращает нижнюю оценку длины маршрута в графе G для подмножества решений S G - граф, start - стартовая вершина TSP_BnB(G, start): BestPath = некоторое эвристическое решение или ∅ Visited = {start} - список пройденных вершин Вернуть BnB(G, Visited, BestPath) BnB(G, Visited, BestPath): Если Visited содержит все вершины графа G: Вернуть MinPath(BestPath, Visited) Для каждой вершины v графа G не из Visited: VNext = Visited + {v} Если LowerBound(VNext) < Length(BestPath): Path = BnB(G, VNext, BestPath) BestPath = MinPath(BestPath, Path) Вернуть BestPath LowerBound(G, Visited): Для каждой вершины графа G найти два смежных с ней ребра с минимальным весом, с учетом уже построенной части маршрута Visited: ребра, входящие в маршрут, рассматриваются в первую очередь Вернуть сумму весов таких двух ребер для каждой вершины по всем вершинам графа G, поделенную на 2 Код:
|
08.12.2022, 12:42 | #3 |
Пользователь
Регистрация: 01.12.2022
Сообщений: 18
|
что такое "некоторое эвристическое решение или ∅" ?
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
задача коммивояжера метод ветвей и границ | alesya-san | Помощь студентам | 0 | 07.01.2017 18:30 |
Задача коммивояжера(метод ветвей и границ) | merick | Помощь студентам | 5 | 16.06.2016 23:13 |
метод ветвей и границ в c# | Альберт0 | C# (си шарп) | 1 | 24.03.2015 17:20 |
метод ветвей и границ на с++ | kirillkucelap | Помощь студентам | 1 | 13.10.2014 22:09 |
Коммивояжера метод ветвей и границ | kop | Помощь студентам | 2 | 21.10.2011 23:30 |