| Предыдущая тема :: Следующая тема |
| Автор |
Сообщение |
Turbo
Site Admin
Зарегистрирован: 19.02.2006
Сообщения: 248
|
 Добавлено: Чт Мар 16, 2006 4:05 pm Заголовок сообщения: |
 |
|
| Андрей Маленков писал(а): | Хотелось бы увидеть среди них задачку с графом  |
Кстати я в свое время её сам лично решал, точнее делал реализацию алгоритма. Эта задача легко решается с помощью правильного поиска статей. =)
Я пользовался алгоритмом описанным вот здесь (сейчас насколько я знаю есть более быстрые модификации): E.Loukakis, C.Tsouros. «An Algorithm for the Maximum Internally Stable Set in a Weighted Graph», Intern. J. Computer Math., 1983, v.13, p.117-129. |
|
| Вернуться к началу |
|
 |
Renat
Зарегистрирован: 21.02.2006
Сообщения: 12
|
| Добавлено: Чт Мар 16, 2006 5:49 pm Заголовок сообщения: |
|
|
Интереснее всего было бы посмотреть решения к задачам ZLIB и к тестовой задаче, а в остальных и так все ясно
Насчет задачи ZMIS, то там проходил, например, такой алгоритм:
рекурсивный перебор, вершины отсортированы по убыванию веса, отсечение по условию (сумма_ранее_выбранных_вершин + 2 * жадное_решение_для_оставшихся_вершин <= лучшее_ранее_найденное решение). |
|
| Вернуться к началу |
|
|
Андрей Маленков
Зарегистрирован: 20.02.2006
Сообщения: 8
|
| Добавлено: Чт Мар 16, 2006 9:56 pm Заголовок сообщения: |
|
|
| Turbo писал(а): | | Андрей Маленков писал(а): | | Хотелось бы увидеть среди них задачку с графом |
Кстати я в свое время её сам лично решал, точнее делал реализацию алгоритма. Эта задача легко решается с помощью правильного поиска статей. =)
Я пользовался алгоритмом описанным вот здесь (сейчас насколько я знаю есть более быстрые модификации): E.Loukakis, C.Tsouros. «An Algorithm for the Maximum Internally Stable Set in a Weighted Graph», Intern. J. Computer Math., 1983, v.13, p.117-129. |
Я много статей нашел Видимо мне попался слишком оптимизированный алгоритм - статья отсылала к другой, другая к третьей, написаной какими то хитрыми китайцами В итоге проленился разбираться. Пожалел об этом только вчера вечером.
при решении ZLIB у меня вообще мозг отказал. наверное я не слишком креативен а может мозг не привык что его f#ck-ают
А вообще конечно было прикольно. К сожалению в школе и универе было мало времени для такого досуга.... |
|
| Вернуться к началу |
|
|
Андрей Маленков
Зарегистрирован: 20.02.2006
Сообщения: 8
|
| Добавлено: Чт Мар 16, 2006 9:59 pm Заголовок сообщения: |
|
|
| Renat писал(а): | Насчет задачи ZMIS, то там проходил, например, такой алгоритм:
рекурсивный перебор, вершины отсортированы по убыванию веса, отсечение по условию (сумма_ранее_выбранных_вершин + 2 * жадное_решение_для_оставшихся_вершин <= лучшее_ранее_найденное решение). |
Спасибо за решение Теперь смогу расслабиться. Я так и думал что должно быть теоретически не совсем правильное, но проходящее решение |
|
| Вернуться к началу |
|
|
Turbo
Site Admin
Зарегистрирован: 19.02.2006
Сообщения: 248
|
| Добавлено: Пт Мар 17, 2006 12:06 am Заголовок сообщения: |
|
|
| Андрей Маленков писал(а): | при решении ZLIB у меня вообще мозг отказал. наверное я не слишком креативен а может мозг не привык что его f#ck-ают
А вообще конечно было прикольно. К сожалению в школе и универе было мало времени для такого досуга.... |
По собственному опыту знаю, что на BF трудно решать первую задачу, потом мозг привыкает использовать некоторые приемы и работать на более высоком уровне. Полезно, если был опыт составления машин Тьюринга.
Да я тоже начал решать уже после института, а жаль. |
|
| Вернуться к началу |
|
|
|
|
Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете голосовать в опросах
|
Powered by phpBB © 2001, 2005 phpBB Group
|
FAQ
Поиск
Пользователи
Группы
Регистрация
Профиль
Войти и проверить личные сообщения
Вход
