Здравствуйте, Gadsky, Вы писали:
G>Кстати, насчет NP==P, что вы думаете насчет:
В позапрошлом году я показывал эту страницу моему научному руководителю, он сказал, что доказательства P=NP ему попадаются достаточно регулярно, примерно раз в год Кроме того я тогда облазил весь сайт (он был тогда ещё на русском) в поисках доказательства теоремы, ну или хотя-бы полиномиального алгоритма для какой-нибудь NP-трудной задачи, но не нашёл. Нет его там и сейчас...
Они, как я понял, изобрели новое представление булевых функций, и если генерировать вход задачи ВЫПОЛНИМОСТЬ в этом представлении, то у них получается полиномиальный алгоритм. Ну на мой взгляд здесь ничего удивительного: если подавать на вход полиномы Жегалкина, то ВЫПОЛНИМОСТЬ тоже полиномиально решается.
Здесь у кого-то в форуме есть подпись: "Часто сложные проблемы имеют простые неправильные решения". Имхо, тот самый случай
LCR>Они, как я понял, изобрели новое представление булевых функций, и если генерировать вход задачи ВЫПОЛНИМОСТЬ в этом представлении, то у них получается полиномиальный алгоритм. Ну на мой взгляд здесь ничего удивительного: если подавать на вход полиномы Жегалкина, то ВЫПОЛНИМОСТЬ тоже полиномиально решается.
LCR>Здесь у кого-то в форуме есть подпись: "Часто сложные проблемы имеют простые неправильные решения". Имхо, тот самый случай
Надов все-таки поразбираться.
Кажется у него первый том недавно появился.
А>Например, методом динамического программирования задача решается стандартно и полно. Есть точные А> оценки эффективности этого метода по сравнению с полным перебором примерно 10% итераций, и чем А> больше требуемых заготовок, тем эффективнее метод.
-----------------------------------------------------------------------------------------
Что до динамического програмирования то я эти виходные как раз им и занимался. Взял в библиотеке книгу и смотрел "что это и з чем его едят" поскольку я ещо только студент то сам не во всьом розобрался. Но мне показалось что он больше подходит в случае линейного розкроя и ещо если он и в правду даёт в 10 раз меньше итераций то я тут прикинул что при полном переборе в моей задаче надо перебрать около 10 в 30 степени комбинаций 10% от етого числа будет 10 в 29 степени что в принципе нечего не дает
P.S
Я пока только студент а многие из тех кто принимают участие в обсуждении моего вопроса имеют уже научную степень
Если что-то нето сморозил то заранее прошу меня извинить
Re[6]: Оптимальная упаковка
От:
Аноним
Дата:
26.05.03 13:29
Оценка:
Здравствуйте, Delf, Вы писали:
D>Здравствуйте, Аноним, Вы писали:
А>>Например, методом динамического программирования задача решается стандартно и полно. Есть точные А>> оценки эффективности этого метода по сравнению с полным перебором примерно 10% итераций, и чем А>> больше требуемых заготовок, тем эффективнее метод.
D>----------------------------------------------------------------------------------------- D>Что до динамического програмирования то я эти виходные как раз им и занимался. Взял в библиотеке книгу и смотрел "что это и з чем его едят" поскольку я ещо только студент то сам не во всьом розобрался. Но мне показалось что он больше подходит в случае линейного розкроя и ещо если он и в правду даёт в 10 раз меньше итераций то я тут прикинул что при полном переборе в моей задаче надо перебрать около 10 в 30 степени комбинаций 10% от етого числа будет 10 в 29 степени что в принципе нечего не дает
D>P.S D>Я пока только студент а многие из тех кто принимают участие в обсуждении моего вопроса имеют уже научную степень D>Если что-то нето сморозил то заранее прошу меня извинить
Не совсем так, я же указал, что это для задач небольшой размерности ПРИМЕРНО 10 %, чем больше размерность тем эффективнее. НО естествнно, что если размерность стремиться в бесконечностьт, то следует использовать приближенные алгоритмы.
Да ну и конечно динамическое программирование не самый эффективный метод, но в каждой конкрентной постановке задачи существуют возможнотсти сократить перебор, НО это уже надо дымать...
Re[4]: Оптимальная упаковка
От:
Аноним
Дата:
26.05.03 13:36
Оценка:
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Здравствуйте, Аноним, Вы писали:
А>>Здравствуйте, Андрей Тарасевич, Вы писали:
А>>"Это переборная задача и "стандартного" (и/или эффективного) точного алгоритма для ее решения нет."
А>>Бред. Еще как есть. Не вводите в заблуждение ежели не знаете. Например, методом динамического программирования задача решается стандартно и полно. Есть точные оценки эффективности этого метода по сравнению с полным перебором примерно 10% итераций, и чем больше требуемых заготовок, тем эффективнее метод.
АТ>В том то и дело, что знаю. Причем знаю очень хорошо. Так что бредом, извините, придется назвать Ваше заявление. Во первых, метод динамического программирования не является стандартным методом решения данной задачи. Есть масса других, не менеее "стандартных" методов решения. Во-вторых, ни о какой эффективности решения методм динамического программирования речи, разумеется, быть не может. Задача, как я уже сказал, переборная, и методы типа динамического программирования, "ветвей и границ" и т.п. ничего здесь принципиально поменять не могут. Все это лишь способы более разумной организации перебора. Который, в общем случае, огромен.
Я же написал "стандартных" в КАВЫЧКАХ. Это ВЫ придумали термин Стандартный, а не я.
И продолжаете глупости писать. Любой метод имеет ту или иную эффективность, только разные значения.
Единственно умное изречение — "Все это лишь способы более разумной организации перебора".
Вот метод динамического программировния и позволят сократить перебор в 10 раз, да и при этом еще сокращает количество операций, но этого Вам наверное не понять, раз вы не совсем понимаете, что такое эффективность метода.
Что до динамического програмирования то я эти виходные как раз им и занимался. Взял в библиотеке книгу и смотрел "что это и з чем его едят" поскольку я ещо только студент то сам не во всьом розобрался. Но мне показалось что он больше подходит в случае линейного розкроя и ещо если он и в правду даёт в 10 раз меньше итераций то я тут прикинул что при полном переборе в моей задаче надо перебрать около 10 в 30 степени комбинаций 10% от етого числа будет 10 в 29 степени что в принципе нечего не дает
P.S
Я пока только студент а многие из тех кто принимают участие в обсуждении моего вопроса имеют уже научную степень
Если что-то нето сморозил то заранее прошу меня извинить
Здравствуйте, Delf, Вы писали:
D>Здравствуйте, Gadsky, Вы писали:
G>>Кстати, насчет NP==P, что вы думаете насчет: G>>http://www.tarusa.ru/~mit/ENG/eng.html
D>Что до динамического програмирования то я эти виходные как раз им и занимался. Взял в библиотеке книгу и смотрел "что это и з чем его едят" поскольку я ещо только студент то сам не во всьом розобрался. Но мне показалось что он больше подходит в случае линейного розкроя и ещо если он и в правду даёт в 10 раз меньше итераций то я тут прикинул что при полном переборе в моей задаче надо перебрать около 10 в 30 степени комбинаций 10% от етого числа будет 10 в 29 степени что в принципе нечего не дает
D>P.S D>Я пока только студент а многие из тех кто принимают участие в обсуждении моего вопроса имеют уже научную степень D>Если что-то нето сморозил то заранее прошу меня извинить
Вот уменя вопросец, а как Вы оценивали, что у Вас количество операций в полном переборе 10 в 30?
У меня есть сомнения, что Вы не допустили ошибки.
Здравствуйте, Delf, Вы писали:
D>Спасибо Анониму за ответ я обизатэльно поищу "Оптимальный раскрой листового металла" D>Чтото подобное я правда уже искал D>В инете накопал что эта задача так просто не решается а существуют только алгоритмы решения что дают результат близкий к оптимальному только вот самих этих алгоритмов чтото нигде не видно D>А решить её перебором вобще не возможно(я даже сам сначала пробовал, моя програма перебирала 500 000 комбинацый за секунду но эсли задать больше 30 деталей дохла)
Че-то у меня есть подозрение, что задача из класса NP -> следовательно решается точно только методом полного перебора. Есть замечательная книга:
"Computers and interactability. A Guide to the Theory of NP-Completeness."
(Авторы: Garey & Johnson.)
Там про такие задачи хорошо написано. Если надо, могу кинуть ее электронный вариант. На русском языке.
Здравствуйте, Аноним, Вы писали:
А>>>"Это переборная задача и "стандартного" (и/или эффективного) точного алгоритма для ее решения нет."
А>>>Бред. Еще как есть. Не вводите в заблуждение ежели не знаете. Например, методом динамического программирования задача решается стандартно и полно. Есть точные оценки эффективности этого метода по сравнению с полным перебором примерно 10% итераций, и чем больше требуемых заготовок, тем эффективнее метод.
АТ>>В том то и дело, что знаю. Причем знаю очень хорошо. Так что бредом, извините, придется назвать Ваше заявление. Во первых, метод динамического программирования не является стандартным методом решения данной задачи. Есть масса других, не менеее "стандартных" методов решения. Во-вторых, ни о какой эффективности решения методм динамического программирования речи, разумеется, быть не может. Задача, как я уже сказал, переборная, и методы типа динамического программирования, "ветвей и границ" и т.п. ничего здесь принципиально поменять не могут. Все это лишь способы более разумной организации перебора. Который, в общем случае, огромен.
А>Я же написал "стандартных" в КАВЫЧКАХ. Это ВЫ придумали термин Стандартный, а не я. А>И продолжаете глупости писать. Любой метод имеет ту или иную эффективность, только разные значения.
"Эффективный алгоритм" — это термин, а не просто слово из словара Ожегова. Как Вам уже сообщили, эффективным алгоритмом называется полиномильный алгоритм.
А>Единственно умное изречение — "Все это лишь способы более разумной организации перебора". А>Вот метод динамического программировния и позволят сократить перебор в 10 раз, да и при этом еще сокращает количество операций, но этого Вам наверное не понять, раз вы не совсем понимаете, что такое эффективность метода.
С пониманием как раз таки у Вас дела обстоят не самым лучшим образом.
Здравствуйте, DeaTH FaNG, Вы писали:
DF>Совершенно точно NP-полна. Сам когда-то доказательство разбирал. Если надо дам ссылку, оно совсем несложное....
Здравствуйте, Lonely Dog, Вы писали:
LD>Че-то у меня есть подозрение, что задача из класса NP -> следовательно решается точно только методом полного перебора. Есть замечательная книга: LD>"Computers and interactability. A Guide to the Theory of NP-Completeness." LD>(Авторы: Garey & Johnson.) LD>Там про такие задачи хорошо написано. Если надо, могу кинуть ее электронный вариант. На русском языке.
сказать что надо — это ничего не сказать. чудовищно надо.
кинь пожалуйста либо саму книжку мне на мыло, либо ссылку.
LD>>"Computers and interactability. A Guide to the Theory of NP-Completeness." LD>>Там про такие задачи хорошо написано. Если надо, могу кинуть ее электронный вариант. На русском языке. S>кинь пожалуйста либо саму книжку мне на мыло, либо ссылку.
Кроме того я тогда облазил весь сайт (он был тогда ещё на русском) в поисках доказательства теоремы, ну или хотя-бы полиномиального алгоритма для какой-нибудь NP-трудной задачи, но не нашёл. Нет его там и сейчас... 
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
