Описание тега branch-and-bound
Branch and bound is a general technique for finding optimal solutions of various combinatorial and integer programming problems. It entails examining candidates (“branches”), while utilizing knowledge of upper and lower limits (“bounds”) to eliminate sub-trees, to find the optimal solution quicker.
2
ответа
C-код для ветвления и связанного выпуска
Так что я думаю, что я на правильном пути, используя метод ветвления и привязки для решения моего эвристического решения задачи о путешествии, однако, я получаю ошибку сегментации в своей "наименьшей" функции, но мне все еще трудно справиться со сво…
05 апр '13 в 23:05
1
ответ
Рюкзак ветка и переплет
У меня есть следующие данные: item weight value value/weight 1 5 40 8 2 2 10 5 3 6 30 5 4 1 12 12 5 2 18 9 Емкость составляет 10. Как приступить к вычислению верхней границы для узла 0? Я рассчитываю верхнюю границу для узла 0 следующим образом: ub …
11 дек '13 в 14:05
1
ответ
Как понять проблему с памятью поиска в ширину в ветке и привязке
Недавно меня смутил метод ветвления и привязки. В методе ветвления и привязки есть три стратегии поиска: поиск по глубине, поиск по ширине и поиск по первому. Во всех книгах и литературах утверждается, что в первую очередь и в лучшую очередь потребу…
27 фев '17 в 09:53
0
ответов
CPLEX (+Java): использовать все пользовательские вызовы, но не обязательно все целочисленные
У меня есть следующая проблема: Используя CPLEX, я решаю TSP-подобную структуру. Очевидно, я использую ветвление и границу над линейной релаксацией. Для исключения подуровня я впоследствии добавляю ограничения. Для меня не важно найти наилучшее из в…
08 июн '18 в 11:37
1
ответ
Количество уровней в ветке и связанном дереве
Учитывая оптимизацию ILP (целочисленное линейное программирование) с n целочисленными переменными и m ограничениями и реализацию ветви и связанного дерева для решения канонической задачи, Сколько уровней (высота дерева) требуется дереву, чтобы дости…
24 фев '14 в 16:29
1
ответ
Ветвь и связанный алгоритм для максимизации важности
У меня есть проблема, которая должна быть решена с помощью алгоритма ветвления и привязки, но мне трудно думать, как ее решить. Я не могу понять, как запустить алгоритм ветвления и привязки. Вот проблема: У машины максимальный вес и объем, и мне нуж…
08 мар '11 в 19:26
0
ответов
Алгоритм ветвления и ограничения для решения задач назначения
Я начал делать Branch and Bound Algorithm для задачи присваивания в C++, и я не могу найти правильное решение. В первую очередь пример задачи присваивания: проблема присваивания Итак, каждый человек может быть назначен на одну работу, и идея состоит…
21 янв '17 в 14:12
1
ответ
Ошибка ветвления и привязки: Node1 не может быть приведен к java.lang.Comparable
Я пытаюсь реализовать алгоритм поиска филиала и границ в Java. Я знаю его концепцию (как она работает), но я не уверен, как это реализовать. Я нашел несколько примеров в Google, но они намного сложнее, и я не могу понять их. Я хочу реализовать это п…
14 май '15 в 05:37
0
ответов
Как использовать алгоритм ветвления и связывания, решающий проблему последовательности задач с крайним сроком в Java
Я уже знаю о том, как использовать "алгоритм ветвления и привязки" для решения "проблемы последовательности заданий", но это только в концепции. Я пытаюсь написать эту проблему на Java, но мой разум опустел, я не знаю, как начать. Может ли кто-нибуд…
04 дек '18 в 19:24
0
ответов
Численная устойчивость симплексного алгоритма
Редактировать: Симплекс математического алгоритма оптимизации, не путать с симплексным шумом или триангуляцией. Я реализую свой собственный решатель линейного программирования, и я хотел бы сделать это, используя 32-разрядные числа с плавающей запят…
15 фев '19 в 14:38
1
ответ
Разница между ATSP и TSP
Это может быть немного глупый вопрос, но какова точная разница в решении TSP и ATSP. Я всегда думал, что в ATSP вам нужно вычислить обратный путь (поскольку входная матрица асимметрична). Таким образом, путь для ATSP вдвое длиннее, чем TSP. Я прав? …
13 янв '16 в 09:15
2
ответа
Подсчет предметов, входящих в ветку и связанный рюкзак
Используя алгоритм ветвей и границ, я оценил оптимальную прибыль от данного набора предметов, но теперь я хочу выяснить, какие предметы включены в это оптимальное решение. Я оцениваю значение прибыли оптимального ранца следующим образом (адаптирован…
10 апр '13 в 13:15
4
ответа
C++ реализация ранцевых ветвей и границ
Я пытаюсь в C++ реализовать эту проблему ранца с помощью ветвления и ограничения. Здесь есть версия Java на этом сайте: Реализация веток и связок для ранца Я пытаюсь сделать так, чтобы моя версия на C++ распечатала 90-й, который должен был быть, но …
16 июл '12 в 04:19
0
ответов
Существуют ли точные методы решения покрытия Path в двудольных графах?
Рассмотрим простой граф G =(V; E). Хорошо известная проблема Path Cover ( https://en.wikipedia.org/wiki/Path_cover) является NP-полной для всех классов графов, для которых NP-полная для гамильтоновой задачи, включая планарные графы, двудольные графы…
15 июл '15 в 16:56
1
ответ
Погоня за игрой в C
Я застрял с довольно сложной проблемой: На поле MxN, содержащем курицу, орла и двор, курица пытается убежать от орла (входя во двор), и орел пытается поймать курицу. Цыпленок убегает, когда достигает во дворе, и орел ловит курицу, когда он находится…
07 янв '14 в 19:23
2
ответа
Ветвь и связанная реализация
Я работал над этой проблемой и могу получить некоторые результаты, но у меня возникают проблемы с реализацией метода ветвления и привязки здесь.Ребята, вы можете мне помочь? Строительные Склады Описание После выигрыша в лотерею вы решаете купить нес…
13 мар '11 в 05:30
1
ответ
Алгоритмическое сравнение нескольких вариантов цен для многих клиентов
У нас есть 1000 000 клиентов. Стоимость проданных товаров для каждого из них может быть выражена как цена A или цена B. Цена А << Цена Б. Цена A и Цена B не являются линейными по отношению друг к другу. В некоторых случаях B стоит в 2 раза дороже, в…
06 окт '13 в 02:34
1
ответ
Поиск оптимальной цены для нескольких клиентов
Пересчет сравнения нескольких вариантов цены для многих клиентов алгоритмически, без излишних затрат. У нас есть 1000 000 клиентов. Стоимость проданных товаров для каждого из них может быть выражена как цена A или цена B. Цена А << Цена Б. Цена A и …
18 окт '13 в 17:47
0
ответов
Как найти наименьшую упаковку, которая может содержать набор предметов?
Как я могу обобщить алгоритм упаковки 3D одного контейнера, чтобы найти наименьшие размеры контейнера, которые могут содержать набор элементов? Я смотрю на алгоритм ветвления и привязки, есть ли условие, которое позволяет мне разрезать ветку, а не т…
17 апр '15 в 10:08
1
ответ
InputMismatchException чтение десятичных дробей
В функции main() http://penguin.ewu.edu/cscd501/Wint-2011/BranchAndBound/Knap01BnB.txt inp = new Scanner ( new File(lineIn) ); maxWeight = inp.nextInt(); n = inp.nextInt(); System.out.printf ("Reading data from file %s, with %d items\n", lineIn, n);…
29 авг '12 в 11:35