Attributes | Values |
---|
rdfs:label
| |
rdfs:comment
| - Задача коммивояжёра (коммивояжёр — бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов.
|
dcterms:subject
| |
dbkwik:resource/35rzF-BhL_otm9wCtVTaeg==
| - 159(xsd:integer)
- 1296(xsd:integer)
|
dbkwik:resource/4AivDxIwDSIeegYP-z9FLQ==
| |
dbkwik:resource/8WZQ1ZzI1NKp0sap4bN5GA==
| |
dbkwik:resource/9AXiqEjPKQ6Z9TSFEgu5Dg==
| - Ананий В. Левитин
- Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн
|
dbkwik:resource/QjxfzC_GfdpB3emLTkwFmA==
| |
dbkwik:resource/fco9BXc0-68mng7EiSFwrA==
| |
dbkwik:resource/hEinrC5DRtFi1sSnEzNC-w==
| - Алгоритмы: построение и анализ
- Алгоритмы: введение в разработку и анализ
|
dbkwik:ru.science/...iPageUsesTemplate
| |
dbkwik:resource/Ws_SYt2NFkQUqaEEV9ZEBA==
| - Глава 3. Метод грубой силы: Задача коммивояжера
|
dbkwik:resource/kUq4r6m06kqYMRfOFZ7m_g==
| - Introduction to Algorithms
- Introduction to The Design and Analysis of Algorithms
|
ISBN
| |
abstract
| - Задача коммивояжёра (коммивояжёр — бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и т. п.) и соответствующие матрицы расстояний, стоимости и т. п. Как правило, указывается, что маршрут должен проходить через каждый город только один раз — в таком случае выбор осуществляется среди гамильтоновых циклов. Существует несколько частных случаев общей постановки задачи, в частности геометрическая задача коммивояжёра (также называемая планарной или евклидовой, когда матрица расстояний отражает расстояния между точками на плоскости), треугольная задача коммивояжёра (когда на матрице стоимостей выполняется неравенство треугольника), симметричная и асимметричная задачи коммивояжёра. Также существует обобщение задачи, так называемая обобщённая задача коммивояжёра. Общая постановка задачи, впрочем как и большинство её частных случаев, относится к классу NP-сложных задач.
|