|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
25.03.2011, 16:56 | #1 |
Регистрация: 23.03.2011
Сообщений: 6
|
Поиск абсолютной b(p)-медианы графа. алгоритм. или его часть.
подскажите пожалуйста алгоритм, может есть у кого? (не приближенный)
или хотябы поиск числа сочетаний b-элементов из множества n(n=1,2,3...). т.е. все возможные сочетания из b вершин графа это. составная часть основного алгоритма. что ни пытаюсь навоять - получается громоздко и всеравно как надо неработает Последний раз редактировалось havoc; 25.03.2011 в 17:03. |
25.03.2011, 17:11 | #2 | |
Форумчанин
Регистрация: 04.02.2011
Сообщений: 260
|
Цитата:
Код:
Последний раз редактировалось Летучий_СкилетиК; 25.03.2011 в 17:19. |
|
25.03.2011, 17:50 | #3 | |
Регистрация: 23.03.2011
Сообщений: 6
|
Цитата:
про b-медиану попробую сформулировать: дан взвешенный неориентированный граф. 1. задается колличество медиан b<=общему колличеству вершин 2. выбираем произвольно b вершин. 3. все оставшиеся вершины прикрепляем к одной из b выбранных вершин по кратчайшему пути. 4. рассчитываем передаточное число для каждой из b вершин(сумма произведений длины пути(кратчайшего) до прикрепленой вершины на ее вес), при этом каждая часть графа считается отдельно. (т.е. всего b графов, каждый состоит из тех вершин которые мы прикрепили) 5. суммируем b передаточных чисел, запоминаем. 6. проделываем пункты 2-5 пока не переберем все сочетания 7. из получившегося массива выбираем минимальное значение. b-вершины для которых оно получено и будут являться b-медианой графа. как-то так. думаю врятли кто будет заморачиваться, если готового нету. сделаю(надеюсь) - выложу. Последний раз редактировалось havoc; 26.03.2011 в 08:20. |
|
26.03.2011, 08:13 | #4 | |
Регистрация: 23.03.2011
Сообщений: 6
|
хочу записать все сочетания в строки двумерного массива. делаю так:
Код:
Код:
Цитата:
UPD: ошибка найдена, неверно была задана длинна массива Последний раз редактировалось havoc; 26.03.2011 в 12:25. |
|
27.03.2011, 23:06 | #5 |
Регистрация: 23.03.2011
Сообщений: 6
|
как обещал, алгоритм поиска b-медианы:
Код:
надеюсь комунибудь будет полезно Последний раз редактировалось havoc; 27.03.2011 в 23:27. |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Алгоритм обхода графа | helena91 | Паскаль, Turbo Pascal, PascalABC.NET | 1 | 01.03.2011 15:40 |
показать алгоритм в виде графа. | Нина93 | Помощь студентам | 0 | 26.12.2010 14:31 |
Комбинаторный алгоритм и использование графа | DaRy | Помощь студентам | 1 | 08.02.2010 21:50 |
Поиск возможных путей графа | RammFan | Общие вопросы Delphi | 2 | 19.06.2008 10:45 |