Комментарии 7
Я с C++ почти никак, но хотелось бы потрогать прогу руками.
Не могли бы вкратце описать, как скомпилить? Что предварительно установить, какой командой собрать?
Система, если что, ubuntu 16.04
Не могли бы вкратце описать, как скомпилить? Что предварительно установить, какой командой собрать?
Система, если что, ubuntu 16.04
> Ее оптимизационная версия является NP-трудной, поэтому оптимальное решение можно получить либо полным перебором, либо оптимизированным полным перебором — методом ветвей и границ.
Пусть P != NP.
Пусть P != NP.
Вообще сравнение с брутфорсом за n! как-то бессмысленно. Простой брутфорс на TSP — это динамика по маске за 2^n * n^2. Честнее было бы с ним сравнивать.
Как раз таки n! это брутфорс, он же полный перебор. А вот динамика это уже оптимизированное решение, учитвающее наличие в задаче оптимальной структуры и повторяющихся подзадач.
«Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.»
«Динамическое программирование в теории управления и теории вычислительных систем — способ решения сложных задач путём разбиения их на более простые подзадачи. Он применим к задачам с оптимальной подструктурой (англ.), выглядящим как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений, по сравнению с «наивными» методами, можно значительно сократить.»
С перебором за n! стоит сравнивать просто как с самым наивным методом. Другой вопрос — дествительно стоило добавить сравнение с динамическим программированием как с еще одним способом получения действительно оптимального решения. Каюсь, не подумал о том, что им можно решить задачу коммивояжера. Когда будет время запрогаю и дополню пост.
Благодарю, друг, спасаешь! Ещё и код чистый, с комментариями и понятный + Qt — замечательно!
Вот ещё хорошая книжка: mexalib.com/view/33768
Вот ещё хорошая книжка: mexalib.com/view/33768
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Решение задачи коммивояжера алгоритмом Литтла с визуализацией на плоскости