Например нахождение прототипа по хешу имеет простую проверку - сама хеш-функция, а в проблеме коммивояжера такой простой проверки (доказательства, что путь кратчайший) - нет. Приоритет - простота проверочной функции и практическая польза решения такой задачи (например, восстановление документа из клочков имеет практическую пользу, а выясление чисел из произвольного массива в сумме дающих нуль - нет прямой пользы).

задан 27 Апр '15 19:19

изменен 27 Апр '15 23:11

То, что допускает простую проверку, оно и принадлежит классу NP. Это как бы одно и то же. Задача коммивояжёра в виде нахождения кратчайшего пути к такому классу не относится, но там сами задачи ставятся так, что ответ на них "да" или "нет". В этом смысле, даётся число S и спрашивается, имеется ли маршрут с общей стоимостью не более S. Решение такой задачи, конечно, допускает простую проверку.

(27 Апр '15 19:51) falcao

Простите мое невежество, я и на самом деле глубоко не знаком с этим вопросом (поэтому и спрашиваю). Нашел статью https://ru.wikipedia.org/wiki/%D0%9A%D0%BB%D0%B0%D1%81%D1%81_NP (Примеры задач класса NP), что коммивояжер принадлежит классу NP, наверное не так понял.

(27 Апр '15 21:27) asianirish

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

(27 Апр '15 22:49) asianirish
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×33

задан
27 Апр '15 19:19

показан
223 раза

обновлен
27 Апр '15 23:11

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru