Здравствуйте, Delf, Вы писали:
D>Задача: D>есть набор разних плоских прямоугольных деталей (размеры и количество задаются) D>росположить их на прямоугольных столах розмером M см на N см D>так что бы столов было использовано как можно меньше
Если я не ошибаюсь, не верхнем уровне задача может решаться итеративно в соответствии со следующей стратегией: производим оптимальное размещение имеющихся в наличии деталей на первом столе (оптимальное = площадь непокрытой части стола минимальна), и затем рекурсивно переходим к решению этой же задачи для оставшихся столов и оставшихся деталей.
А вот для каждого конкретного стола мы имеем задачу двумерного раскроя и упаковки. Это переборная задача и "стандартного" (и/или эффективного) точного алгоритма для ее решения нет. Для практического решения этой задачи существуют разноообразные приближенные алгоритмы. В частности, существует довольно простой алгоритм попарного слияния прямоугольников (известный также как алгоритм Ванга). Алгоритм Ванга в чистом виде является переборным алгоритмом, которые дает оптимальное решение среди всевозможных гильотинных размещений (гильотинный раскрой (или размещение) — это раскрой, который может быть получен из исходного куска материала с использованием только "сквозных" разрезов от края до края). С точки зрения исходной задачи такое решение в общем случае оптимальным, разумеется, не будет (несложно построить контрпример), но во многих случаях его качество будет приемлемым. Следует заметить, что даже если мы ограничимся рассмотрением только гильотинных размещений, нахождение оптимального решения все равно будет являться весьма трудоемкой задачей (для большого числа заготовок). Оптимизировать (сократить) перебор можно как такими "беспотерьными" методами, как метод ветвей и границ, так и несложными эвристическими методами.
Здравствуйте, Аноним, Вы писали:
А>Здравствуйте, Андрей Тарасевич, Вы писали:
А>"Это переборная задача и "стандартного" (и/или эффективного) точного алгоритма для ее решения нет."
А>Бред. Еще как есть. Не вводите в заблуждение ежели не знаете. Например, методом динамического программирования задача решается стандартно и полно. Есть точные оценки эффективности этого метода по сравнению с полным перебором примерно 10% итераций, и чем больше требуемых заготовок, тем эффективнее метод.
В том то и дело, что знаю. Причем знаю очень хорошо. Так что бредом, извините, придется назвать Ваше заявление. Во первых, метод динамического программирования не является стандартным методом решения данной задачи. Есть масса других, не менеее "стандартных" методов решения. Во-вторых, ни о какой эффективности решения методм динамического программирования речи, разумеется, быть не может. Задача, как я уже сказал, переборная, и методы типа динамического программирования, "ветвей и границ" и т.п. ничего здесь принципиально поменять не могут. Все это лишь способы более разумной организации перебора. Который, в общем случае, огромен.
D>Большоэ спасибо за такой подробный ответ хотя я и не знаю что такое алгоритм Ванга но обизатильно поищу в нете D>Вобще то я сильно сомневаюсь что оптимальное размещение фигур на первом столе никак не повлияет на оптимальность размещения на остальных столах и на оптимальность в целом. Но честно говоря контрпример не могу привести хотя потратил на это весь вечер.
Зря сомневаешься. Очень даже сильно повлияет. Нередкий случай, когда "удобные" заготовки используются в первую очередь, а потом их уже нет
Пример:
1. Есть Одна Большая Деталь. Настолько большая, что две штуки таких деталей на столе не разместить.
2. Есть куча мелких деталей, причем _все_ они помещаются на стол рядом с большой. Допустим процент выхода при это получается 85%.
3. А вот теперь умножаем задачу, скажем раз в 100.
Какая для нее будет оптимальная раскладка? Правильно, нужно сто раз повторить раскладку первоначального задания.
А как будет поступать вышеуказанный алгоритм? Он выберет мелкие детали и разместит их на одном из листов с выходом 99% (не сомневаюсь, что он это сумеет). Куда положить 100 Больших Деталей теперь? Правильно... на 100 дополнительных листов. Так что результат в конце будет далеко не оптимальный. Причем, как показала моя практика, такие или похожие варианты встречаются нередко.
Конечно, идеального решения быть не может (NP-полнота). Но некоторые эвристики более удачные, некоторые менее. У меня в программе используется следующий алгоритм (правда это гильотинный раскрой):
1. Составляем "базис" из хорошо оптимизированных карт. Грубо говоря это делается так: берется подвыборка деталей и из нее перебором составляется _одна_ карта. Подвыборки формируются так, чтобы карты, полученные из них были _разными_.
После этого у нас есть куча карт (N = ~200-1000), которые оптимальны в некотором роде, но задания они еще не решают.
2. Чтобы решить задание — нужно составить из базиса _решение_. Короче, определить сколько раз какую карту употребить. Употребить можно 0 раз, конечно. Эта задача решается случайным поиском на целочисленном векторе длиной N. Случайный поиск — это случайные изменения целевого вектора, постепенно уменьшающиеся к концу оптимизации. Короче, это та же генетика, но без рекомбинации, а только с мутациями контролируемой силы.
3. Если после шага 2 не все задание исчерпано — переходии к 1 и решаем задачу на остатке...
Теперь по поводу гильотинности. Гильотинность хороша тем, что пространство решения задачи №1 (оптимизация _одной_ карты) резко сужается. Это вследствие того, что работать приходится только с прямоугольниками. А вот вторая часть — целочисленное линейное программирование — остается неизменной и ее можно приспособить и для упаковки.
Если хочешь посравнивать, вот ключевые слова:
Астра-Д, BestCut, Orion, 2D Nesting and Case Packer Optimizer,
Plus 2D, eCutout
Я сравнивал свою программу(ну и алгоритм соответственно eCutout.
Фактически на моем алгоритме достигаются лучшие результаты. К сожалению за это приходится платить временем.
Привет всем
Помогите пожалуйста с алгоритмом решения вот такой задачи
Задача:
есть набор разних плоских прямоугольных деталей (размеры и количество задаются)
росположить их на прямоугольных столах розмером M см на N см
так что бы столов было использовано как можно меньше
Заранее спасибо
Re: Оптимальная упаковка
От:
Аноним
Дата:
14.05.03 22:44
Оценка:
Здравствуйте, Delf, Вы писали:
D>Привет всем D>Помогите пожалуйста с алгоритмом решения вот такой задачи D>Задача: D>есть набор разних плоских прямоугольных деталей (размеры и количество задаются) D>росположить их на прямоугольных столах розмером M см на N см D>так что бы столов было использовано как можно меньше
D>Заранее спасибо
Вообще вспомнить сам алгоритм не смогу, но это стандартный алгоритм, я думаю что во многих учебника по оптимизации он точно есть, называется он что-то типа "Оптимальный раскрой листового металла" или ткани. Вобщем помню только, что минимизировать надо обрезки. Поищи в сети что-нибудь с таким названием. Удачи.
Спасибо Анониму за ответ я обизатэльно поищу "Оптимальный раскрой листового металла"
Чтото подобное я правда уже искал
В инете накопал что эта задача так просто не решается а существуют только алгоритмы решения что дают результат близкий к оптимальному только вот самих этих алгоритмов чтото нигде не видно
А решить её перебором вобще не возможно(я даже сам сначала пробовал, моя програма перебирала 500 000 комбинацый за секунду но эсли задать больше 30 деталей дохла)
Здравствуйте, Delf, Вы писали:
D>В инете накопал что эта задача так просто не решается а существуют только алгоритмы решения что дают результат близкий к оптимальному только вот самих этих алгоритмов чтото нигде не видно
Возможно, задача NP-полная. Тогда ничего, кроме хороших эвристик, предложить нельзя.
D>>В инете накопал что эта задача так просто не решается а существуют только алгоритмы решения что дают результат близкий к оптимальному только вот самих этих алгоритмов чтото нигде не видно
MAG>Возможно, задача NP-полная. Тогда ничего, кроме хороших эвристик, предложить нельзя.
Совершенно точно NP-полна. Сам когда-то доказательство разбирал. Если надо дам ссылку, оно совсем несложное....
... << RSDN@Home 1.0 beta 7a >>
Re[4]: Оптимальная упаковка
От:
Аноним
Дата:
15.05.03 13:08
Оценка:
Здравствуйте, DeaTH FaNG, Вы писали:
DF>Совершенно точно NP-полна. Сам когда-то доказательство разбирал. Если надо дам ссылку, оно совсем несложное....
А какие есть эвристики для произвольных многоугольников (невыпуклых)? Что можно почитать по этому поводу?
Здравствуйте, Delf, Вы писали:
D>Привет всем D>Помогите пожалуйста с алгоритмом решения вот такой задачи D>Задача: D>есть набор разних плоских прямоугольных деталей (размеры и количество задаются) D>росположить их на прямоугольных столах розмером M см на N см D>так что бы столов было использовано как можно меньше
Здравствуйте, DeaTH FaNG, Вы писали:
DF>Совершенно точно NP-полна. Сам когда-то доказательство разбирал. Если надо дам ссылку, оно совсем несложное....
Буду очень признателен если дадите сылку на доказательство
Может ктото ещо знаэт где евристические алгоритмы по етой задачи достать у меня пока есть только вариант с генетическим алгоритмом
D>>>В инете накопал что эта задача так просто не решается а существуют только алгоритмы решения что дают результат близкий к оптимальному только вот самих этих алгоритмов чтото нигде не видно
MAG>>Возможно, задача NP-полная. Тогда ничего, кроме хороших эвристик, предложить нельзя.
DF>Совершенно точно NP-полна. Сам когда-то доказательство разбирал. Если надо дам ссылку, оно совсем несложное....
К этой задаче очевидным образом сводится задача о рюкзаке.
АТ>Если я не ошибаюсь, не верхнем уровне задача может решаться итеративно в соответствии со следующей стратегией: производим оптимальное размещение имеющихся в наличии деталей на первом столе (оптимальное = площадь непокрытой части стола минимальна), и затем рекурсивно переходим к решению этой же задачи для оставшихся столов и оставшихся деталей.
АТ>А вот для каждого конкретного стола мы имеем задачу двумерного раскроя и упаковки. Это переборная задача и "стандартного" (и/или эффективного) точного алгоритма для ее решения нет. Для практического решения этой задачи существуют разноообразные приближенные алгоритмы. В частности, существует довольно простой алгоритм попарного слияния прямоугольников (известный также как алгоритм Ванга). Алгоритм Ванга в чистом виде является переборным алгоритмом, которые дает оптимальное решение среди всевозможных гильотинных размещений (гильотинный раскрой (или размещение) — это раскрой, который может быть получен из исходного куска материала с использованием только "сквозных" разрезов от края до края). С точки зрения исходной задачи такое решение в общем случае оптимальным, разумеется, не будет (несложно построить контрпример), но во многих случаях его качество будет приемлемым. Следует заметить, что даже если мы ограничимся рассмотрением только гильотинных размещений, нахождение оптимального решения все равно будет являться весьма трудоемкой задачей (для большого числа заготовок). Оптимизировать (сократить) перебор можно как такими "беспотерьными" методами, как метод ветвей и границ, так и несложными эвристическими методами.
Большоэ спасибо за такой подробный ответ хотя я и не знаю что такое алгоритм Ванга но обизатильно поищу в нете
Вобще то я сильно сомневаюсь что оптимальное размещение фигур на первом столе никак не повлияет на оптимальность размещения на остальных столах и на оптимальность в целом. Но честно говоря контрпример не могу привести хотя потратил на это весь вечер.
Re: Оптимальная упаковка
От:
Аноним
Дата:
20.05.03 09:34
Оценка:
Здравствуйте, Delf, Вы писали:
D>Привет всем D>Помогите пожалуйста с алгоритмом решения вот такой задачи D>Задача: D>есть набор разних плоских прямоугольных деталей (размеры и количество задаются) D>росположить их на прямоугольных столах розмером M см на N см D>так что бы столов было использовано как можно меньше
D>Заранее спасибо
Как к.т.н. скажу: одним из способов решения задачи оптимального ракроя листового материала на прямоугольные заготовки с различными постановками (прямые задачи, обратные и т.д.) являетя метод динамического программирования (Беллмана). Решение получаешь однозначное. Есть четкие оценки машинных затрат применения этого метода по сравнению с полным перебором.
Смотри книжки по оптимальному раскрою листового и не только листового материала. В инете мало информации реально помогающей. Надо идти в библиотеку, в научную естественно (при ВУЗ-ах или от академии наук).
Re[2]: Оптимальная упаковка
От:
Аноним
Дата:
20.05.03 09:40
Оценка:
Здравствуйте, Андрей Тарасевич, Вы писали:
АТ>Здравствуйте, Delf, Вы писали:
"Это переборная задача и "стандартного" (и/или эффективного) точного алгоритма для ее решения нет."
Бред. Еще как есть. Не вводите в заблуждение ежели не знаете. Например, методом динамического программирования задача решается стандартно и полно. Есть точные оценки эффективности этого метода по сравнению с полным перебором примерно 10% итераций, и чем больше требуемых заготовок, тем эффективнее метод.
Re[5]: Оптимальная упаковка
От:
Аноним
Дата:
20.05.03 09:49
Оценка:
Здравствуйте, DeaTH FaNG, Вы писали:
D>>>>В инете накопал что эта задача так просто не решается а существуют только алгоритмы решения что дают результат близкий к оптимальному только вот самих этих алгоритмов чтото нигде не видно
MAG>>>Возможно, задача NP-полная. Тогда ничего, кроме хороших эвристик, предложить нельзя.
DF>>Совершенно точно NP-полна. Сам когда-то доказательство разбирал. Если надо дам ссылку, оно совсем несложное....
DF>К этой задаче очевидным образом сводится задача о рюкзаке.
К задаче об оптимальной загрузке рюкзака сводится только линейный раскрой. Но направление мысли верное.
D>>>>>В инете накопал что эта задача так просто не решается а существуют только алгоритмы решения что дают результат близкий к оптимальному только вот самих этих алгоритмов чтото нигде не видно
MAG>>>>Возможно, задача NP-полная. Тогда ничего, кроме хороших эвристик, предложить нельзя.
DF>>>Совершенно точно NP-полна. Сам когда-то доказательство разбирал. Если надо дам ссылку, оно совсем несложное....
DF>>К этой задаче очевидным образом сводится задача о рюкзаке.
А>К задаче об оптимальной загрузке рюкзака сводится только линейный раскрой. Но направление мысли верное.
Давай еще заметим, что линейный раскрой — самый простой случай раскроя. Мы же NP-полную задачу сводим к нашей.
Здравствуйте, Аноним, Вы писали:
А>"Это переборная задача и "стандартного" (и/или эффективного) точного алгоритма для ее решения нет."
А>Бред. Еще как есть. Не вводите в заблуждение ежели не знаете. Например, методом динамического программирования задача решается стандартно и полно. Есть точные оценки эффективности этого метода по сравнению с полным перебором примерно 10% итераций, и чем больше требуемых заготовок, тем эффективнее метод.
Во-первых. Метод динамического программирования эффективным не назовёшь (мало того, что экспоненциальное время, да ещё и экспоненциальная память).
Во-вторых. эта задача NP-трудна в сильном смысле (Strongly NP-hard), а отсюда следует, что если твой алгоритм динамического программирования выдаёт точное решение, то P==NP, с чем я тебя и поздравляю.
LCR>Во-вторых. эта задача NP-трудна в сильном смысле (Strongly NP-hard), а отсюда следует, что если твой алгоритм динамического программирования выдаёт точное решение, то P==NP, с чем я тебя и поздравляю.
LCR>Это о теории, а насчёт практики здесь.
Здравствуйте, 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>кинь пожалуйста либо саму книжку мне на мыло, либо ссылку.
eCutout.
quicksort =: (($:@(<#[),(=#[),$:@(>#[)) ({~ ?@#)) ^: (1<#)
