| Автор |
RE: Алгоритми |
berd
Користувач
Повідомлень: 87
Звідки: СЗШ 17 м. Бердичів
Зареєстрований: 11.06.07 |
| Опубліковано 15-07-2008 01:49 |
|
|
|
Oracle написав:
Народ, може хтось має якісь лінки на Венгерський алгоритм? Або може хтось може розказати ідею того алгоритму? Бажано просто ідею - реалізувати то вже не складно, а от зрозуміти як і чому воно працює ніяк не можу... На ТС читав - але там немає ніякого нормального доведення тому, чого той алгоритм все-таки працює...
Даю посилання - скачай архів, у ньому є словесний опис алгоритму і візуалізатор, який показує, як він працює.
http://rain.ifmo.ru/cat/view.php/vis/graph-flow-match/hungarian-1999
Взагалі по алгоритмам то непоганий сайт.
No pasaran !!! |
     
|
| Автор |
RE: Алгоритми |
Oracle
Користувач
Повідомлень: 75
Звідки: LNU FAMI-13
Зареєстрований: 20.02.07 |
| Опубліковано 15-07-2008 10:07 |
|
|
to berd: Дуже дякую, класна інформація
а хтось зможе довести коректність алгоритму? Тобто що він завжди коректно знайде паросполучення мінімальної ваги? |
|
|
| Автор |
RE: Алгоритми |
berd
Користувач
Повідомлень: 87
Звідки: СЗШ 17 м. Бердичів
Зареєстрований: 11.06.07 |
| Опубліковано 15-07-2008 11:44 |
|
|
|
Oracle написав:
to berd: Дуже дякую, класна інформація
а хтось зможе довести коректність алгоритму? Тобто що він завжди коректно знайде паросполучення мінімальної ваги?
Коротко доведення і схема реалізаціїї наведена тут:
http://informatics.mccme.ru/moodle/mod/book/view.php?id=421&chapterid=94
No pasaran !!! |
|
|
| Автор |
RE: Алгоритми |
Oracle
Користувач
Повідомлень: 75
Звідки: LNU FAMI-13
Зареєстрований: 20.02.07 |
| Опубліковано 15-07-2008 13:43 |
|
|
to berd: дякую за інформацію!
Доречі кому цікаво, знайшов також осить непогану статтю про Венгерський метод: http://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf
Змінив(ла) Oracle, 15-07-2008 17:02 |
|
|
| Автор |
RE: Алгоритми |
ZuTa
Користувач
Повідомлень: 43
Звідки: school
Зареєстрований: 29.12.07 |
| Опубліковано 20-07-2008 10:36 |
|
|
ФОРУМЧАНИ!
Потрібна ваша допомога!
Списки + вказівники(1)
Про це все дуже гарно написано в Кормені(всякому разі мені зрозуміло!)
але прикол в тому, що я забув як використовувати (1) в Паскалі 
Майже в усіх МОЇХ книгах приклади використання (1) наведені на С++
Плз порекомендуйте книжку чи сайт...
Чому я згадав про (1) - мені треба представити граф у вигляді списку ребер!!! (бажано щоб це теж було описано в книзі чи на сайті)
Надіюсь на вашу допомогу, дякую! 
Running...Accepted |
|
|
| Автор |
RE: Алгоритми |
berd
Користувач
Повідомлень: 87
Звідки: СЗШ 17 м. Бердичів
Зареєстрований: 11.06.07 |
| Опубліковано 21-07-2008 00:25 |
|
|
ZuTa написав:
...
1. Списки + вказівники(1)
... прикол в тому, що я забув як використовувати (1) в Паскалі
Майже в усіх МОЇХ книгах приклади використання (1) наведені на С++
...
2. Чому я згадав про (1) - мені треба представити граф у вигляді списку ребер!!! (бажано щоб це теж було описано в книзі чи на сайті)
...
1. Посилання викладу (я так зрозумів - мова Паскаль) - книги є, можу також вислати, якщо є потреба (свої всі користуються).
2. Вишли мені умову задачі листом - поки у відпустці підкажу...
No pasaran !!! |
|
|
| Автор |
RE: Алгоритми |
ZuTa
Користувач
Повідомлень: 43
Звідки: school
Зареєстрований: 29.12.07 |
| Опубліковано 21-07-2008 09:09 |
|
|
|
книги є
Якщо можна, то дайте автора - можі в інеті знайду...
Вишли мені умову задачі листом
Да яка там умова?! мені треба записати ребра і навчитися проходити по них(DFS, BFS)
В задачі:
вершин - 10000, а ребер - 50000
Дякую!
Running...Accepted |
|
|
| Автор |
RE: Алгоритми |
berd
Користувач
Повідомлень: 87
Звідки: СЗШ 17 м. Бердичів
Зареєстрований: 11.06.07 |
| Опубліковано 21-07-2008 10:12 |
|
|
Реалізація пошуку в глибину і у ширину на Паскалі викладено тут
http://mateminfo.myff.ru/viewforum.php?id=4.
Там можеш і свої базові додавати, мова (укр., рос.) ролі не грає.
No pasaran !!!
Змінив(ла) berd, 21-07-2008 10:14 |
|
|
| Автор |
RE: Алгоритми |
ZuTa
Користувач
Повідомлень: 43
Звідки: school
Зареєстрований: 29.12.07 |
| Опубліковано 21-07-2008 10:20 |
|
|
та ні!
я знаю ці алгоритми!
мені потрібно ПРЕДСТАВИТИ ГРАФ у вигляді списку ребер (як я розумію,за допомогою ВКАЗІВНИКІВ)
Running...Accepted |
|
|
| Автор |
RE: Алгоритми |
berd
Користувач
Повідомлень: 87
Звідки: СЗШ 17 м. Бердичів
Зареєстрований: 11.06.07 |
| Опубліковано 21-07-2008 11:03 |
|
|
|
ZuTa написав:
та ні!
я знаю ці алгоритми!
мені потрібно ПРЕДСТАВИТИ ГРАФ у вигляді списку ребер (як я розумію,за допомогою ВКАЗІВНИКІВ)
Так ПОГУУГЛИ Інет на російські мові - там цього добра валом, тільки правильно запит для пошуку формулюй. Наприклад, для запиту
"Представление графа списком" в мене у першому ж рядку відразу видало це посилання:
http://it-library.org/articles/?c=12&&a=457
Далі я вже й не дивився - там на Паскалі непогано описано...
No pasaran !!! |
|
|
| Автор |
RE: Алгоритми |
ZuTa
Користувач
Повідомлень: 43
Звідки: school
Зареєстрований: 29.12.07 |
| Опубліковано 21-07-2008 11:18 |
|
|
Дякую!
я подумав може в когось зразу є щось, тому тут і написав...
Running...Accepted |
|
|
Birthday(s):
