| Автор |
Алгоритми |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 27-06-2007 17:57 |
|
|
Я думаю: така тема не завадить.
Що таке алгоритм Крускала?.. Може Остап це мені колись мені пояснював, але він стільки всього пояснював, що вмене голова перегрілась... Please help
Pascal not dead! |
    
|
| Автор |
RE: Алгоритми |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 27-06-2007 18:38 |
|
|
Прошу вибачення, що "тоді" так багато пояснював - просто до відбору було дуже мало часу, а треба було багато розказати.
Отже, алгоритм Крускала.
Нехай маємо зважений зв'язний граф (кожному ребру приписана вага і між кожними двома вершинами існує шлях). Алгоритм Крускала дозволяє знайти в графі каркас мінімальної сумарної ваги (сума ваг ребер, що входять в знайдений каркас - мінімально можлива).
Алгоритм полягає в наступному:
1) Спочатку наш каркас пустий (не містить жодного ребра). Будемо послідовно додавати ребра до нього за наступними правилами.
2) Сортуємо всі ребра по вазі.
3) По черзі переглядаємо кожне ребро в відсортованому масиві (від найменшого до найбільшого) і:
3.1) якщо при додаванні поточного ребра до каркасу в ньому не з'явиться цикл, то додаємо його до каркасу.
3.2) якщо при додаванні з'явиться цикл - то НЕ додаємо це ребро.
4) Після того як переглянемо всі ребра, ми отримаємо каркас мінімальної сумарної ваги.
Доведення павильності алгоритму я упускаю, так само, як упускаю реалізацію пункту 3 - "якщо при додаванні поточного ребра до каркасу в ньому не з'явиться цикл" - це окрема задача, для якої також потрібно скористатися одним з класичних алгоритмів.
Не помиляється той, хто нічого не робить! |
|
|
| Автор |
RE: Алгоритми |
Romko
Користувач
Повідомлень: 113
Звідки: mdegree
Зареєстрований: 07.11.06 |
| Опубліковано 27-06-2007 19:33 |
|
|
|
Ostap написав:
Прошу вибачення, що "тоді" так багато пояснював - просто до відбору було дуже мало часу, а треба було багато розказати.
Отже, алгоритм Крускала.
Нехай маємо зважений зв'язний граф (кожному ребру приписана вага і між кожними двома вершинами існує шлях). Алгоритм Крускала дозволяє знайти в графі каркас мінімальної сумарної ваги (сума ваг ребер, що входять в знайдений каркас - мінімально можлива).
Алгоритм полягає в наступному:
1) Спочатку наш каркас пустий (не містить жодного ребра). Будемо послідовно додавати ребра до нього за наступними правилами.
2) Сортуємо всі ребра по вазі.
3) По черзі переглядаємо кожне ребро в відсортованому масиві (від найменшого до найбільшого) і:
3.1) якщо при додаванні поточного ребра до каркасу в ньому не з'явиться цикл, то додаємо його до каркасу.
3.2) якщо при додаванні з'явиться цикл - то НЕ додаємо це ребро.
4) Після того як переглянемо всі ребра, ми отримаємо каркас мінімальної сумарної ваги.
Доведення павильності алгоритму я упускаю, так само, як упускаю реалізацію пункту 3 - "якщо при додаванні поточного ребра до каркасу в ньому не з'явиться цикл" - це окрема задача, для якої також потрібно скористатися одним з класичних алгоритмів.
Чи підходить сюди(пункт 3) якийсь інший алгоритм, окрім union-find?
 |
|
|
| Автор |
RE: Алгоритми |
Ostap
Модератор
Повідомлень: 426
Звідки: ЛНУ, Прикладна, ПМІ-81
Зареєстрований: 03.03.06 |
| Опубліковано 27-06-2007 21:27 |
|
|
|
Чи підходить сюди(пункт 3) якийсь інший алгоритм, окрім union-find?
Можна DFS-ом чи BFS-ом. Правда складність досить висока порівняно з union-find, але в багатьох випадках може пройти.
Не помиляється той, хто нічого не робить! |
|
|
| Автор |
RE: Алгоритми |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 01-07-2007 23:32 |
|
|
2 Ostap:
Ну, не зовсім зрозумів, але прочитав на Вікі про алгоритм Прима й "поняв".
Зацініть - віршик нарив. Називається "Алгорима":
I think that I shall never see
A graph more lovely than a tree.
A tree whose crucial property
Is loop-free connectivity.
A tree which must be sure to span
So packets can reach every LAN.
First the Root must be selected
By ID it is elected.
Least cost paths from Root are traced
In the tree these paths are placed.
A mesh is made by folks like me
Then bridges find a spanning tree.
(http://en.wikipedia.org/wiki/Spanning_tree_protocol#Multiple_Spanning_Tree_Protocol_.28MSTP.29)
Ну, потім і прочитав про Крускала. Щось мені алго. Прима більше сподобався: зрозуміліший якийсь...
Послухайте
If one represents a nondeterministic abstract machine as a graph where vertices describe states and edges describe possible transitions, shortest path algorithms can be used to find an optimal sequence of choices to reach a certain goal state, or to establish lower bounds on the time needed to reach a given state. For example, if vertices represents the states of a puzzle like a Rubik's Cube and each directed edge corresponds to a single move or turn, shortest path algorithms can be used to find a solution that uses the minimum possible number of moves.
Пахне новою задачкою...
Pascal not dead! |
|
|
| Автор |
RE: Алгоритми |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 01-07-2007 23:37 |
|
|
Що там за "union-find"? Наскільки я розумію: потрібно просто перевірити, чи обидві вершини не знаходяться у масиві вже пройдених.
Pascal not dead! |
|
|
| Автор |
RE: Алгоритми |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 01-07-2007 23:50 |
|
|
http://en.wikipedia.org/wiki/Reverse-Delete_algorithm Теж не поганий алгоритм для знаходження каркасу. Щоправда після виконання його, потрібно проходитись по створеному ним, циклу й затерти найважче ребро, тобто пам'ятайте, що він - не завершений.
Pascal not dead! |
|
|
| Автор |
RE: Алгоритми |
Torax
Користувач
Повідомлень: 75
Звідки: ЛНУ
Зареєстрований: 03.03.06 |
| Опубліковано 01-07-2007 23:51 |
|
|
to ibm: ні, ти не правильно зрозумів. алгоритм union-find дозволяє визначити чи знаходяться дві вершини в одній і тій же зв"язній компоненті. Зв"язна компонента - це множина вершин така, що будь-які дві вершини з цієї множини є зв"язані між собою ребрами, не обов"язково безспосередньо - можна і через проміжні вершини. а це вже зовсім не така проста штука, як просто перевірити, чи ми "проходили" вершини, чи ні )
Для чого нам це потрібно? Та якраз для того, щоб визначити чи при додаванні ребра не буде циклу. Якщо ми додамо ребро між двома вершинами з однієї зв"язної компоненти - то обов"язково буде цикл, оскільки до того вже існував якийсь шлях між цими вершинами. З"єднавши ці два шляхи ми утворимо цикл. А цикл нам не потрібний, оскільки він лише додасть лишньої ваги нашому каркасу, не даючи нам нічого корисного. Якщо ж ми додамо ребро між вершинами з різних зв"язних компонент, то ці дві вершини стають членами однієї зв"язної компоненти і в цю компоненту входять тепер також всі ті вершини, які були в відповідних тим двом вершинам компонентах зв"язності.
Надіюся я більш-менш зрозуміло пояснив?... З мене педагог ніякий, так що вибачайте якщо щось |
|
|
| Автор |
RE: Алгоритми |
sem
Модератор
Повідомлень: 65
Звідки: LNU PMI
Зареєстрований: 02.03.06 |
| Опубліковано 02-07-2007 00:39 |
|
|
Це дуже хороша тема. Я буду дуже вдячний, якщо хтось оформить цей алгоритм (Крускала) у вигляді статті і запостить у розділ "Алгоритми на графах".
(Що отримуємо на вході та на виході хай буде як опис статті. Тоді можна буде легко знайти який саме потрібно алгоритм).
| Sem. |
|
|
| Автор |
RE: Алгоритми |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 03-07-2007 12:17 |
|
|
Poor Wenwen (http://acm.tju.edu.cn/toj/showp2244.html) Problem ID in problemset: 2244 з сайту acm.tju.edu.cn, наскільки я зрозумів, робиться методом ітерації:
wenwen=apple+banana+pear+5
apple=banana+pear
banana=pear
pear=10
Зпочатку зануляєм усі змінні (wenwen=0 apple=0 banana=0 pear=0). Далі пробуємо присвоїтизмінним таке значення, як написано
wenwen=0+0+0+5
apple=0+0
banana=0
pear=10
І так стільки ж раз, скільки рівнянь:
wenwen=0+0+10+5
apple=0+10
banana=10
pear=10
wenwen=10+10+10+5
apple=10+10
banana=10
pear=10
wenwen=20+10+10+5
apple=10+10
banana=10
pear=10
Результат:
wenwen=20+10+10+5=45
Якщо після того, як проітерували значення не збігаються - poor wenwen (р-ків неіснує)
Pascal not dead!
Змінив(ла) ibm, 03-07-2007 12:23 |
|
|
| Автор |
RE: Алгоритми |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 03-07-2007 12:42 |
|
|
Коротше, забив я на [TopCoder], пощу вам свій GIF(тільки gif, бо статтю ще не доробив). Все-1-о ніяк не візьмусь то дописувати...
Такщо: ось так, дітки, працює алгоритм Дейкстри
Pascal not dead!
Змінив(ла) ibm, 03-07-2007 12:43 |
|
|
| Автор |
RE: Алгоритми |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 03-07-2007 17:26 |
|
|
Torax написав:
Надіюся я більш-менш зрозуміло пояснив?... З мене педагог ніякий, так що вибачайте якщо щось
Зрозумів з другого разу, але все-таки зрозумів В такому випадку, напевне, можна по створювати матриці, в які записати елементи кожного, тимчасово створеного, куска матриці
типу тут, покищо (бо пройшлось тільки по AD, CE i DF):
існує 2 куски з: 1)A,D,F; 2)C,E;
По ходу випонання, воно усе може і буде об'єднуватись в 1 масив.
Як вам таке?
Pascal not dead!
Змінив(ла) ibm, 29-10-2007 18:39 |
|
|
| Автор |
RE: Алгоритми |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 03-07-2007 18:08 |
|
|
DixonD розказав, як робляться задачі типу (я - оформив)
A Simple Game. Problem ID in problemset: 2193 http://acm.tju.edu.cn/toj/vcontest/showp257_E.html:
Табличний метод (для АСМу може не пройти за обмеженнями):
Нехай ходить першим "+", а другим "-", тоді наступне:
Проходимось змінною а for'ом по масиву, в якому усе записано.
Очевидно, що при
M > a --- виграє "+", тому записуємо в масив "+"-и на проміжку від 1 до М.
Повторювати, доки а < N
Далі: якщо в масиві, на проміжку між [a-k, a-1] знаходяться тільки "+"-и --- ставимо "-". Якщо ні - "+".
Звичайно можна використовувати не масив[N], який може стати досить великим за умовою. Можна просто юзати масивчик на >= M елементів.
Якщо хтось знає кращі варіанти розв'язку - пишіть, не стидайтесь.
Pascal not dead!
Змінив(ла) ibm, 03-07-2007 18:16 |
|
|
| Автор |
RE: Алгоритми |
DixonD
Модератор
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
| Опубліковано 03-07-2007 18:23 |
|
|
|
Ой, ibm, я то тобі розказав, але шось те, шо ти написав не дуже на моє пояснення подібне;-) |
![dixond[злий_пес]acm[на]lviv[на]ua](../themes/Brasil-Fusion/forum/msn.gif)
|
| Автор |
RE: Алгоритми |
DixonD
Модератор
Повідомлень: 167
Звідки: ЛНУ ім. Івана Франка
Зареєстрований: 21.10.06 |
| Опубліковано 03-07-2007 18:37 |
|
|
Давайте я сам розкажу (нічого нового тут немає, звичайна динаміка). Основний принцип такий: ми виграєм, якшо за один хід ставим суперника в програшну позицію. Отже в масив ми записуєм "+", якшо виграшна позиція для того, хто ходить, і "-" в іншому випадку. Тоді треба перебрати всі клітинки, які позначають ситуації, шо можуть виникнути після нашого ходу. Якшо є хоча б один "-", то ми виграєм і ставим "+" в поточну клітинку. Ну, а далі я думаю все ясно...
P.S. Ще раз кажу нічого тут оригінального тут немає, та часом таке канає...
P.P.S. Метод мені показала вчителька математики дуже давно, коли готувала до обласної. Ясна річ, про алгоритми я тоді взагалі нічого не чув:-)
Змінив(ла) DixonD, 03-07-2007 18:42 |
|
|
| Автор |
RE: Алгоритми |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 03-07-2007 22:51 |
|
|
Щось незрозумів... Поясни плз. з прикладом, тощо. В тебе лептоп вже є на це
Тоді треба перебрати всі клітинки, які позначають ситуації, шо можуть виникнути після нашого ходу.
ось ця фраза - взагалі - загадка...
Океан Ельзи - Поясни
А моє пояснення здається мені правильним. Хоча гра тоді виходить абсолютно не об'эктивною. Хоча стривай... Так, в мене - баг. виходить періодичність в М (К)... То як ти хотів?
Pascal not dead!
Змінив(ла) ibm, 03-07-2007 22:56 |
|
|
| Автор |
RE: Алгоритми |
Torax
Користувач
Повідомлень: 75
Звідки: ЛНУ
Зареєстрований: 03.03.06 |
| Опубліковано 03-07-2007 23:20 |
|
|
|
почитайте статтю на топкодері на цю тему: Algorithm Games - http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames |
|
|
| Автор |
RE: Алгоритми |
Torax
Користувач
Повідомлень: 75
Звідки: ЛНУ
Зареєстрований: 03.03.06 |
| Опубліковано 03-07-2007 23:23 |
|
|
to ibm: до речі, за малюнок до дейкстри - респект
скільки ти його малював?... а пояснюю, як можу, а видно ми з Остапом можемо однаково |
|
|
| Автор |
RE: Алгоритми |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 03-07-2007 23:44 |
|
|
Малював десь години 3
На ту статтю вже колись дивився. І коли говорив з DixonD про той алгоритм - теж. Там немає саме тієї задачі. Тільки Німа
Pascal not dead! |
|
|
| Автор |
RE: Алгоритми |
ibm
Користувач
Повідомлень: 422
Звідки: LPML
Зареєстрований: 21.02.07 |
| Опубліковано 04-07-2007 00:04 |
|
|
http://en.wikipedia.org/wiki/Sprague-Grundy_theorem сам ще не дочитав, але багатообіцяюче...
Щось я не зрозумів його... Якщо хтось зрозумів - пишіть... Хоча я й сам догадуюсь що там мало б бути написано Хоча: тільки здогадуюсь. Без формул. То - на задачки типу Шоколаду з якоїсь весняної олімпіади ЛНУ. Доречі, бачу Васі було ліньки навіть змінити назву. Задача називається "Chocolate Squares"
http://www.cut-the-knot.org/Curriculum/Algebra/BreakingChocolateBars.shtml
Гра Грунді
http://www.cut-the-knot.org/Curriculum/Games/Grundy.shtml
Pascal not dead!
Змінив(ла) ibm, 04-07-2007 00:37 |
|
|
Birthday(s):
