AlgoList

[mserg]

Хочу обсудить практического применения NP-трудных задач на практике.

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

Предположим, что разработана некоторая программа и мы пытаемся применить ее на практике. Возможны четыре варианта, описывающих комбинации существования решения и возможностью решать NP-трудные задачи за приемлимое время.
1. Поставленная задача имеет решение и мы смогли его найти за приемлимое время
2. Поставленная задача имеет решение, но мы не можем найти решение за приемлимое время (то есть программа «повисла» и мы не знаем, «отвиснет» она или нет)
3. Поставленная задача не имеет решения и мы можем это доказать за приемлимое время
4. Поставленная задача не имеет решения, но мы не можем это доказать за приемлимое время

На практике успешный бизнес ставит цели всегда выше, чем может реально достичь (см. например, литературу по проектному менеджменту). Поэтому практически всегда будем иметь варианты 3 или 4. Сможет ли программа доказать неразрешимость задачи или нет – не имеет никакого значения, так как ответ: «Задача неразрешима» бизнесмена не устроит. И он не будет смотреть доказательство на 100 страниц, почему задача не имеет решения. Он спросит что-то вроде того : «Что я могу сделать, чтобы задача была решена?» или «Какие есть варианты, чтобы сделать задачу решаемой?». Математики по этому поводу либо молчат, либо высказываются очень скромно, могут обойти эти вопросы под предлогом «сложности темы» или излогать неработоспобные методы в сложной математической символике. Бизнес же придумал вполне успешную методологию решения «неразрешимых» задач
Если возникает вариант 2, то причиной может быть туповатый алгоритм или постановка задачи в «абструкционной форме» - в обвешанной ненужными и трудными для удовлетворения деталями. Если бы даже сверхумный алгоритм нашел решение задачи и возник бы вариант 1, то на практике его нельзя применять. Раз нам пришлось быть весьма изощренными для отыскания решения, то существует высокая вероятность того, что решение будет неустойчиво к изменению входных параметров. Бизнесмены всегда оценивают риски решений (устойчивость к изменению входных параметров) и стараются избегать авантюр. Математиков же презирают на неспособность помочь в решении реальных проблем.
Лично я не сомневаюсь, что умение приемлимо решать NP-трудные задачи весьма важно. Но не менее важно правильно работать с контекстом возниконовения задачи и уметь ставить задачи так, чтобы можно было в приемлимой форме объяснить противоречия и находить хорошие решения.

А что вы думаете по этому вопросу?

[Граф]

[Гость]

а разве факторинг NP-полна?

[mserg]

Насколько я понял, речь идет о постановке задачи взлома RSA-шифра как NP-трудной задачи. Если я не прав, прошу поправить.

Представим себя на месте бизнесмена, стригущего купоны с RSA-шифрования. Оно основывается на том, мы не умеем решать NP-трудные задачи достаточно хорошо, чтобы взлом был экономически оправдан. Если научимся, то стричь купоны будет не с чего. Будет ли бизнесмен платить за то, чтобы лишить себя бизнеса? А именно это и утверждается.

Я не плохо знаю, как работает западный бизнес. В данном случае конкурс объявлен по трем причинам:
1) Реклама. Материальное вознаграждение привлекает людей и они будут рассказывать о сайте, и значит потенциально увеличивается число клиентов. Это основная причина.
2) Поиск кадров. Если кто-то научился ломать шифры, то такого человека можно взять на работу. Вероятности перескочить через шифр настолько мала, что можно ее даже не рассматривать и материальные риски компании минимальны. И никаких тебе чтений резюме, никаких тестов, испытательных сроков и прочей мороки, не нужно человека искать, учить и прочее - чертовски выгодно.
3) Убедиться, что шифр надежен. Для этого с помощью возможности ( без гарантии!) материального вознаграждения привлекают большое количество людей. Щедрость такого предложения нетрудно подсчитать: прикиньте общее число потраченных человеко-часов людей, жаждущих славы и богатства, и поделите на минимальное вознаграждение. Легко убедиться, что в среднем выгоднее сдавать пустые бутылки.

Вот что скрывается за готовностью платить за решение NP-трудной задачи. Лохотрон...

[Граф]

[Гость]

[mserg]

Коллеги, не суть. Можем ли мы или не можем свести одну задачу, которую мы не умеем решать, к другой, которую мы тоже не умеем решать? Какой смысл это обсуждать? Что мы получим с того, что классифицируем или не классифицируем задачу как NP-полную или как NP-трудную? Оправдание своей профессиональной беспомощности? Никто за это не заплатит. Прошу также заметить, что тема обсуждения - не тонкости классификации алгоритмов.

[Гость]

[mserg]

Мне знакома эта проблема. По моим подсчетам стоимость разработки КАЧЕСТВЕННОЙ программы составления расписаний для учебных заведений - примерно $10 млн. Это крайне рискованный проект и очень трудно убедить потенциальных инвесторов в его рентабельности. Очевидно, что проект не может быть сделан в одиночку или даже в десятиром. Лично я бы не стал рисковать. При стоимости одной лицензии $10000 это может не окупиться даже если продвигать программу по всему миру. К тому же на рынке составления расписания уже есть игроки и вытеснить их не так то просто.

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

Когда то я баловался тем, что составлял модель составления школьного расписания (а оно проще ВУЗовского). Оказалось, что даже далеко неполная модель состоит из 30 (программных) классов и около 40 ограничений. Проводил же эксперименты еще на более упрощенной модели. Возникли как раз те проблемы, которые я в общей форме изложил в самом первом сообщении темы. Здесь задача комбинаторного взрыва вариантов существует, но при приложении значительных усилий она мне кажется удовлетворительно решаемой. Рассуждать о NP-полноте можно, но зачем? Это никуда нас не продвигает...

Однако профиссионально эта задача мне интересна. Если есть люди, тратящие свою жизненную энергию на эту тему, то я заинтересован в получении контактной информации. Готов содействовать в решении проблем составления расписания.

[wormball]

[KPAH]

2 wormball
Так как моя жена несколько раз составляла расписание для школы, в которой рабтает кое-что я об этом знаю. И всё действительно плохо..
Ограничений там до задницы (в школе) - и количество часов "трудных" и "лёгких" уроков, нельзя ставить некоторые уроки в начале и конце учебного дня итд итп. Для ВУЗов все эти "детские" ограничения убираются.

[mserg]

[mserg]

Простенькая, почти работающая, программа составления расписания для школ здесь:

http://www.np-soft.ru/projects/schedules/school/sheinst.ZIP - инсталляционный пакет (~2.5M)
http://www.np-soft.ru/projects/schedules/school/shesrc.ZIP - исходники на VB (~0.5)

[Гость]

пости работающая!

звучит смешно.

как почтилетающий самолет
или почти лечащий врач


и не стыдно

[mserg]

Не понял смысла сообщения... Есть лучший открытый код?

Насколько я помню, в программе не работают ограничения "наличие окон в параллелях" и ограничения на закладке "Напряженность", а все остальное работоспособно. Проблемы, связанные с использованием, описаны ранее.