XLisp
, Алгорити Прима-Краскала
 |
Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
|
| ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
| [3.145.50.206] |
|
|
Правила раздела
1. Не создавайте несколько одинаковых тем, ибо модератор может расценить их, как спам и удалить все.
2. Для решения задач по GPSS есть отдельная тема. Все задачи по GPSS опубликовывать в этой теме! Перед опубликовыванием вашей задачи просмотрите всю тему, возможно вы сразу найдете решение.
3. Давайте вашим темам ОСМЫСЛЕННЫЕ названия, а также указывайте язык программирования. Пример: [Pascal]:Работа с файлами и записями.
4. Использования тега CODE обязательно при публикации текста программы.
Темы, оформленные с явным игнорированием правил и отсутствием смысла, будут закрыты/удалены!
Вам помогли? Напишите об этом здесь (в портфолио фрилансера)
Фрилансерам:
5. Демпинг цен запрещен (даже если Вы готовы работать бесплатно). Цены обсуждаются в приватном общении. Если вы готовы рещить задачу бесплатно, просто решите ее быстрее, чем возникнет предложение сделать это за деньги.
6. Пользователям, входящим в группу Newbie, запрещается предлагать свои услуги (завуалированно в т.ч.)
7. В посте с предложением выполнить работу, обязательно указывать ссылку на свое портфолио в Отзывы, Благодарности, Портфолио Это правило работает и в том случае, если вы выполняете работу бесплатно.
8. Реклама (даже завуалированная) своих фриланских сайтов запрещена
Нарушение данных пунктов влечет до RO или БАНА (при неоднократом)
2. Для решения задач по GPSS есть отдельная тема. Все задачи по GPSS опубликовывать в этой теме! Перед опубликовыванием вашей задачи просмотрите всю тему, возможно вы сразу найдете решение.
3. Давайте вашим темам ОСМЫСЛЕННЫЕ названия, а также указывайте язык программирования. Пример: [Pascal]:Работа с файлами и записями.
4. Использования тега CODE обязательно при публикации текста программы.
Темы, оформленные с явным игнорированием правил и отсутствием смысла, будут закрыты/удалены!
Вам помогли? Напишите об этом здесь (в портфолио фрилансера)
Фрилансерам:
5. Демпинг цен запрещен (даже если Вы готовы работать бесплатно). Цены обсуждаются в приватном общении. Если вы готовы рещить задачу бесплатно, просто решите ее быстрее, чем возникнет предложение сделать это за деньги.
6. Пользователям, входящим в группу Newbie, запрещается предлагать свои услуги (завуалированно в т.ч.)
7. В посте с предложением выполнить работу, обязательно указывать ссылку на свое портфолио в Отзывы, Благодарности, Портфолио Это правило работает и в том случае, если вы выполняете работу бесплатно.
8. Реклама (даже завуалированная) своих фриланских сайтов запрещена
Нарушение данных пунктов влечет до RO или БАНА (при неоднократом)
Закрыто Arny 21-04-2009: Введите причину закрытия темы здесь
XLisp
, Алгорити Прима-Краскала
|
Сообщ.
#1
,
|
|
|
|
Необходимо разработать задачу реализюющую решение данного алгоритма
сроки месяц-два условие Дана плоская страна и в ней n городов. Нужно соединить все города телефонной связью так, чтобы общая длина телефонных линий была минимальной. Уточнение задачи. В задаче речь идет о телефонной связи, т. е. подразумевается транзитивность связи: если i-й город связан с j-ым, а j-ый с k-ым, то i-й связан с k-ым. Подразумевается также, что телефонные линии могут разветвляться только на телефонной станции, а не в чистом поле. Наконец, требование минимальности (вместе с транзитивностью) означает, что в искомом решении не будет циклов. В терминах теории графов задача Прима-Краскала выглядит следующим образом: Дан граф с n вершинами; заданы длины ребер. Найти остовное дерево минимальной длины. Как известно, дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро надо выбирать жадно (лишь бы ни возникали циклы). Описание алгоритма жадный алгоритм дает точное оптимальное решение. Как известно (это легко доказать по индукции), дерево с n вершинами имеет n-1 ребер. Оказывается, каждое ребро нужно выбирать жадно (лишь бы не возникали циклы). То есть n-1 раз выбирать самое короткое ребро из еще не выбранное ребро при условии, что оно не образует цикла с уже выбранными. А как следить, чтобы новое ребро не образовывало цикла со старыми? Сделать это просто. До построения дерева окрасим каждую вершину i в отличный от других цвет i. При выборе очередного ребра, например (i, j), где i и j имеют разные цвета, вершина j и все, окрашенные в ее цвет (т.е. ранее с ней соединенные) перекрашиваются в цвет i. Таким образом, выбор вершин разного цвета обеспечивает отсутствие циклов. После выбора n-1 ребер все вершины получают один цвет. |
|
Сообщ.
#2
,
|
|
|
|
icq: 44один83зеро147
mail.ru агент: ir-home<gav>bk.ru стучитесь, обсудим. |
|
Сообщ.
#3
,
|
  |
Готов взяться за проект
номер ICQ: 48ноль9644пять6 отзывы тут http://forum.sources.ru/index.php/topic,14760.0.html Благодарность для Mikefreelance |
|
Сообщ.
#4
,
|
|
|
|
за решение взялся Inf-root
тема закрыта |
0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
0 пользователей:
Закрыто Arny 21-04-2009: Введите причину закрытия темы здесь
[ Script execution time: 0,0263 ] [ 15 queries used ] [ Generated: 13.05.24, 19:52 GMT ]