Архив форума

Процитировано сообщение: Бобрышев Юрий   от 27.01.2009 :: 18:03:09:

 
Ну это как в том анекдоте когда на вопрос «Раскольников, зачем Вы убили старушку всего за 20 копеек?» тот ответил – «А пять бабушек это уже рубль!»  
Если решить одну задачу - то оставшиеся 6 - думаю уже не проблема  

Андрей!
На самом деле критерий проверки прост:
берёте какую-нибудь свою задачу, присылаете нам исходные данные, мы решаем и Вы сравниваете решение со своим.
Чего проще?
Если сделать так раз 100, то ответ нарисуется сам собой.
А МГУ, конечно, аргумент.
 

Скажите пжл тупенькому, в каких таких практических задачах возникает хотя бы 200 точек?

Цитата:
 
1. Если решать ЗК на несимметричном графе, например дорожном, то лобовое сведение несимметричного графа к симметричному удваивает количество вершин. Т.е. нужно объехать сто адресов, а решать удобно задачу с 200-ми точками. Такие "масштабные" проблемы иногда возникают у инкассаторов.
2. Если отвлечься от чисто складских и транспортных вопросов, то, например, задачи пробивки отверстий печатных плат - до нескольких тысяч вершин
3. Всякие хитрые задачи вроде бы небольшого размера, не решаюшиеся лобовым перебором, которые при сведении к ЗК увеличивают размер задачи в разы
и прочая, прочая, прочая...

Цитата:

Конечно! Категоричность терминологии уместна при рекламе шампуня или туалетной бумаги. В нашем же деле уместны оговорки и всяческие уточнения. И практические и терминологические.
...  
И моё предложение совместно что-нибудь посчитать не встретило отклика...  
Пойду на другую ветку, попугаю там народ точными (оптимальными!) решениями!  

Цитата:
 
Да куда уж скромнее...
Только правду.
Но у меня складывается впечатление, что Вы не верите в возможность получить точное решение (точное не в смысле полиномиальности алгоритма, а в смысле оптимальности) ЗК никаким способом, кроме как перебором?  
Все имеющиеся в настоящее время алгоритмы получения точного решения ЗК можно с некоторыми оговорками назвать разновидностями метода ветвей-и-границ. Вопрос только в том, какой подход, или идеологию закладывают авторы при отсечении неверных путей. И таких различных подходов очень, очень мало.  

В простейшем случае задачу о нахождении гамильтонова цикла можно свести к 2^n(имеется ввиду точный алгоритм). Поэтому вариантов будет 2^300. Но полностью с вами согласен, Андрей. Это удивительно =))) По идее машина будет считать это хозяйство 2^300 = 2*(10^90). Т.е. примерно 2^82 секунд. Думаю конец света случится раньше =))))

Я не скептик, напрасно вы, я очень позитивный оптимист   Другие люди в нашей области просто не выживают.  
 
Когда 8 лет назад мы взялись за задачу оптимизации плана загрузки транспорта, нам ученые люди пальчиком крутили у виска и доказывали, что задача не решается.  
 
Когда через 2 года , в 2003 годы мы получили первые успешные решения и выпустили packer3d v1.0 у нас так же как у вас горели глаза и мы были абсолютно уверены, что мы перевернем мир    
 
Но мир устоял, как ни странно   В первой версии (которая до сих пор еще работает бесплатно под видом on-line сервиса на сайте www.old.packer3d.ru)  можно было выставить только ограничения по грузу: тоннаж, зафисксировать высоту, и запрет на установку на коробку сверху. И все. Как оказалось в реальной жизни, довольно редко встречаются погрузки такого простого типа. Обычно надо учитывать множество дополнительных условий и ограничений.  
 
Поэтому потребовалось добавлять функционал: хрупкость, уровни, ряды, нагрузки по осям, группировки, загрузка с разных сторон, порядок загрузки, дозагрузка, паллетирование, затаривание и т.д. и т.п. Полный функционал в картинках на текущий момент можно посмотреть здесь http://www.packer3d.ru/program/features. Ну и геном несколько раз переписывали по-ходу. Вот этим и занимаемся последние 5 лет.  
 
Поэтому оптимизм - это здорово, но настраивайтесь на работу, работу, работу ........
Форум "Общие вопросы задач оптимизации" готов http://www.packer3d.ru/forum/11. Приглашаем всех, кому интересна эта тема.