Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 7
В первой части рисунок не тот после: "Результирующий исходный код выглядит следующим образом:" — код на zython
А так — интересно.
А так — интересно.
Правильно ли я понимаю: Решение сводится к созданию системы линейных уравнений и их решению, но с ограничением типа (char)?
Насколько производительно такое решение возможно ли за разумное время посчитать задачу коммивояжера, допустим, на маршруте 16-20 пунктов.
Насколько производительно такое решение возможно ли за разумное время посчитать задачу коммивояжера, допустим, на маршруте 16-20 пунктов.
Правильный ответ заключается в том, что алгоритм и время его работы зависит от солвера.)
Вот здесь очень много слайдов.
Модель на чистом minizinc без связок с python для 20 городов, использующая солвер gecode 6.3.0 выдаёт решение за 16s 806msec (естественно, можно указать отсечку по времени, тогда выдаст текущее хорошее решение). Если дать ему 4 потока, то за 7s 795msec. Скорее всего он использует метод ветвей и границ, так как это общий солвер, соответственно должен быть в состоянии решить любую, заданную модель. Можно ли прикрутить к minizinc более специфический солвер, расчитанный именно на эту задачу, честно говоря не знаю.
А ну и gecode работает только для целых чисел. :)
Вот здесь очень много слайдов.
Модель на чистом minizinc без связок с python для 20 городов, использующая солвер gecode 6.3.0 выдаёт решение за 16s 806msec (естественно, можно указать отсечку по времени, тогда выдаст текущее хорошее решение). Если дать ему 4 потока, то за 7s 795msec. Скорее всего он использует метод ветвей и границ, так как это общий солвер, соответственно должен быть в состоянии решить любую, заданную модель. Можно ли прикрутить к minizinc более специфический солвер, расчитанный именно на эту задачу, честно говоря не знаю.
А ну и gecode работает только для целых чисел. :)
Под «решением» подразумевается истинное решение с гарантированным минимумом?
Если так, то неплохо — мне надо было лет десять назад решить задачу перемещения робота-манипулятора (точек там полтора десятка было) и решение перебором «в лоб» находилось за несколько часов (впрочем в скорость я не особо упирался — задачка была одноразовая).
Если так, то неплохо — мне надо было лет десять назад решить задачу перемещения робота-манипулятора (точек там полтора десятка было) и решение перебором «в лоб» находилось за несколько часов (впрочем в скорость я не особо упирался — задачка была одноразовая).
Боюсь что-то утверждать, так как сам особо не ковырял внутренности, но на сколько я могу судить — да, солвер отсекает плохие ветви, целиком проверяет хорошие и выводит текущее оптимальное решение на каждой фазе.
В случае, когда мы находим решение, которое удовлетворяет условиям (solve satisfy), солвер останавливается после первого найденного решения, но можно попросить его выдать N решений или все решения, если запускать оптимизацию, то он выводит решения:
В конце выводится ``==========``, что означает, что были пересмотрены все варианты. Это такое условное обозначение у minizinc.
В случае, когда мы находим решение, которое удовлетворяет условиям (solve satisfy), солвер останавливается после первого найденного решения, но можно попросить его выдать N решений или все решения, если запускать оптимизацию, то он выводит решения:
----------
cost: 387 tour: [15, 14, 10, 13, 16, 7, 18, 6, 20, 11, 2, 8, 9, 4, 12, 17, 3, 19, 5, 1]
----------
cost: 384 tour: [15, 11, 9, 14, 16, 7, 18, 6, 20, 3, 10, 8, 4, 2, 12, 17, 13, 19, 5, 1]
----------
cost: 383 tour: [17, 14, 11, 13, 19, 15, 6, 10, 20, 3, 2, 8, 9, 4, 12, 5, 16, 7, 18, 1]
----------
==========
В конце выводится ``==========``, что означает, что были пересмотрены все варианты. Это такое условное обозначение у minizinc.
а какого размера модели переваривает такое решение?
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Constraint Programming или как решить задачу коммивояжёра, просто описав её