@stivjack

Всем доброго времени суток!
Заранее выражаю Вам благодарность за интерес к данной теме.

Мне необходима по возможности консультация и советы от более опытных людей в программированию на С++, так как у меня другой основной язык программирования, поэтому некоторые моменты реализации остаются для меня загадкой даже после усердного поиска в интернете. Огромное спасибо Вам заранее!

В университете дали задание решить задачу коммивояжера методом ветвей и границ с реализацией на С++. Преподаватель поделился программой, которую необходимо "доработать" в соответствии с определенными требованиями, а именно:

1) Размерность задачи:
а) 21 и 35;
б) 25 и 31.

Этот пункт в принципе мне понятен - размерность матрицы, например из а, 21 на 21 и 35 на 35. С остальными аналогично. Поправьте, пожалуйста, если я неправильно понял, буду очень благодарен.
Далее дано следующее указание, которое мне немного не понятно.

2) Исходная функция плотности вероятности для случайных данных:
а) c2·(1+x^2), x∈[0,1];

(во всех случаях надо подобрать константу ci, чтобы на отрезке [0,1] такой плотностью вероятности задавалось бы всё распределение, т.е. нужный интеграл от 0 до 1 давал бы значение 1;
(при этом можно сказать, что «обычное» равномерное распределение имеет плотность c, и не будет ошибкой сказать c·(1+x^0), x∈[0,1]).

Здесь, как я понимаю необходимо очевидно вычислить интеграл, который равняется 3/4 (дробь). Опять же если я не прав, пожалуйста, поправьте, буду очень благодарен. Далее, вопрос заключается в том, что делать с этим интегралом после вычисления? Как я понимаю, эту функцию плотности вероятности нужно реализовать на С++ и с помощью неё заполнять матрицы, размерность которых указана в пункте 1.
Пожалуйста, подскажите как это сделать или хотя бы приведите аналогичный пример реализации заполнения матрицы через функцию плотности вероятности. Буду здесь очень благодарен!

Далее по заданию идут пункты которые я уже разобрал, однако остались вопросы еще по некоторым моментам.

3) . Далее запускаем МВГ с ограниченным временем выполнения (truncated branchand-bound method), причём 5 вариантов: 0.01·Т, 0.03·Т, 0.1·Т, 0.3·Т и 0.5·Т (т.е. 1%, 3%, 10%, 30% и 50% от времени, предварительно вычисленного для этой размерности). Каждый из этих вариантов запускается 2 способами: с применением вызова последовательности правых задач (ППЗ, см. материал лекции) и без его применения. Таким образом, всего у каждого из вас будут такие разные задачи:
• 2 варианта размерности;
• 5 вариантов времени;
• 2 варианта вызова ППЗ
итого 2×5×2 = 20 вариантов.

Здесь у меня главный вопрос заключается в том, как реализовать в коде "ограниченное время выполнения". Столько статей пересмотрел и нигде не находил хоть приближенного ответа на поставленную задачу. Заранее огромное спасибо!

И последний пункт, по которому у меня остался вопрос.

4) Для каждого запуска фиксируем результат (значение целевой функции), полученный к окончанию выделенного времени. После этого досчитываем задачу до конца – и тоже получаем значение целевой функции. Отношение оптимального
значения к значению целевой функции, полученному к окончанию выделенного времени, назовём качеством решения. Усредняем эти значения качества на 10 новых запусках – это будет критерием качества этой одной из 20 задач, указанных в
пункте 3. При этом само усреднение можно делать разными способами (не только как среднее арифметическое).

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

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

Еще раз всем огромное спасибо! До связи!

Вернуться к обсуждению:
Задача коммивояжера C/C++

0