Форумы Серверы Суспільство
Игры Серверы VBIOS General Soft & Hard Увлечения А поговорить... Культура Полезная информация Межигір'я Чат

Пользователь Сообщение: С графи        (Тема#72687)
Hac9lJlbHuKe 
BDSM expert. Атуечайу...
Hac9lJlbHuKe
Возраст: 25
: Дніпро
С нами с 09.09.09
Посты: 9189
25.04.13 18:27 Ukraine #1567240
Треба постановочка задачі"
Имеется n населенных пунктов, в каждом из которых живет pi школьников (i=1,...,n). Надо разместить школу в одном из них так, чтобы общее расстояние, проходимое всеми учениками по дороге в школу, было минимальным."
Тут явно треба буде мутити з найменшими відстанями і відповідно будувати дерево,але може в кого був досвід саме з такою ось рпограммою, постановку задачі буду обговорювати з преподом,бо багато всяких пеньків в розумінні того,як це все буде виглядати і від чого відсштовхуватись.
Нехай учні це і,а пункти(школи) n, то відштовхуємось до учнів помножених на шлях(h) потім знайти оптимальний шлях,де це i*n буде мінімальним, сам пункт,де буде розташована школа можна буде прийняти за 0, от тільки як це все хоча-б для початку графічно зообразити,теоретично від кожного n повинна йти дорога до всіх інших n, тобто спочатку буде зв'язний граф,який має перетворитись у дерево. Хто що підскаже з цього приводу?


Отредактировано Hac9lJlbHuKe 25.04.13 18:33. Причина редактирования: Причина не указана.
Nameless 
Maximus - Lite Edition
Nameless
: 404
С нами с 02.11.05
Посты: 21233
26.04.13 08:00 [Re: Hac9lJlbHuKe] Ukraine #1567416
я опять не понимаю, что тебе нужно. Какая постановка задачи?
Задача в лоб решается так: есть граф населенных пунктов, перебираются все вершины, как потенциальное место для школы, из каждого узла высчитывается кратчайший путь до школы, множится на количество учеников, суммируются расстояния от всех вершин до вершины со школой. Из всех узлов выбирается тот, который минимизирует суммарный путь. Как найти наименьшее расстояние от города до школы? Гугл "a * search" и разбирайся. Алгоритм не оптимальный конечно.
Nameless 
Maximus - Lite Edition
Nameless
: 404
С нами с 02.11.05
Посты: 21233
26.04.13 08:08 [Re: Nameless] Ukraine #1567417
с целью оптимизации можно заранее один раз высчитать все кратчайшие расстояния между узлами (не пересчитывая дваджы p(i,j) и p(j,i), где р -- расстояние), сохранить их и использовать для расчета оптимальности расположения школы.
Hac9lJlbHuKe 
BDSM expert. Атуечайу...
Hac9lJlbHuKe
Возраст: 25
: Дніпро
С нами с 09.09.09
Посты: 9189
26.04.13 10:21 [Re: Nameless] Ukraine #1567460
дякую,трохи прояснив для себе. ну вибачте,що не зрозуміло,я тільки вчусь.
Hac9lJlbHuKe 
BDSM expert. Атуечайу...
Hac9lJlbHuKe
Возраст: 25
: Дніпро
С нами с 09.09.09
Посты: 9189
26.04.13 10:26 [Re: Nameless] Ukraine #1567463
  • Nameless :
Из всех узлов выбирается тот, который минимизирует суммарный путь. .
вузлів чи вершин? 0_о
Nameless 
Maximus - Lite Edition
Nameless
: 404
С нами с 02.11.05
Посты: 21233
26.04.13 11:00 [Re: Hac9lJlbHuKe] Ukraine #1567472
какая разница как назвать? node == vertex, etc )
NaCl 
предатель Родины
С нами с 28.08.08
Посты: 24065
26.04.13 11:25 [Re: Nameless] Ukraine #1567483
оффтоп
Nameless 
Maximus - Lite Edition
Nameless
: 404
С нами с 02.11.05
Посты: 21233
26.04.13 11:27 [Re: NaCl] Ukraine #1567484
мая твая не панимать )
Hac9lJlbHuKe 
BDSM expert. Атуечайу...
Hac9lJlbHuKe
Возраст: 25
: Дніпро
С нами с 09.09.09
Посты: 9189
26.04.13 23:50 [Re: Nameless] Ukraine #1567778
Просто вузол і вершина це таки дуже різні речі,ось мене й запутало.
ПО-суті я вирішив - буду втілювати це дійство через массиви,а самі графи записувати як матриці. Але гемору ще багато, треба досконало розібратись як писати массиви, бо в мене з ними практика зовсім примітивна,рядки,стобці , редагування та видалення -"Малавата будет"
KillMachine UA 
генералиссимус
KillMachine UA
Возраст: 39
: Київ
С нами с 10.12.07
Посты: 25376
27.04.13 02:56 [Re: Hac9lJlbHuKe] Ukraine #1567820
двумерный массив - int eklmn [число пунктов][4]
{номер}
{Х, У, число учеников, результат}

перебор по номеру, рассчет расстояний по прямой до остальных точек, умноженных на количество учеников в тех точках -> результат (с округлением до целого)

сортировка результатов
Nameless 
Maximus - Lite Edition
Nameless
: 404
С нами с 02.11.05
Посты: 21233
27.04.13 11:40 [Re: KillMachine UA] Ukraine #1567934
не, если бы так все было просто, то это было бы не задание, а тривиальщина и граф был бы не нужен (и не факт, что даже координаты вершин есть в наличии). Предполагается, что граф связный, но не все вершины связаны между собой напрямую и кратчайшее расстояние -- это не всегда расстояние по прямой, а возможно путь через несколько других вершин, который еще нужно найти. Насяльнике, я правильно понял?
KillMachine UA 
генералиссимус
KillMachine UA
Возраст: 39
: Київ
С нами с 10.12.07
Посты: 25376
27.04.13 14:19 [Re: Nameless] Ukraine #1567997
поскольку в условии не написано, что школота не может ходить напрямую, то какой смысл усложнять?
Nameless 
Maximus - Lite Edition
Nameless
: 404
С нами с 02.11.05
Посты: 21233
27.04.13 16:36 [Re: KillMachine UA] Ukraine #1568030
я не усложняю. Если б можно было ходить напрямую, графы тут были бы до одного места.
Hac9lJlbHuKe 
BDSM expert. Атуечайу...
Hac9lJlbHuKe
Возраст: 25
: Дніпро
С нами с 09.09.09
Посты: 9189
27.04.13 23:58 [Re: Nameless] Ukraine #1568128
  • Nameless :
не, если бы так все было просто, то это было бы не задание, а тривиальщина и граф был бы не нужен (и не факт, что даже координаты вершин есть в наличии). Предполагается, что граф связный, но не все вершины связаны между собой напрямую и кратчайшее расстояние -- это не всегда расстояние по прямой, а возможно путь через несколько других вершин, который еще нужно найти. Насяльнике, я правильно понял?

Думаю,ти правий, я ж сказав - зв'іязний графа це озачає що відстань від точок 1-2-3 може бути меншо ніж 1-3. Все вірно.
KillMachine UA 
генералиссимус
KillMachine UA
Возраст: 39
: Київ
С нами с 10.12.07
Посты: 25376
28.04.13 00:53 [Re: Hac9lJlbHuKe] Ukraine #1568142
  • Hac9lJlbHuKe :

зв'іязний графа це озачає що відстань від точок 1-2-3 може бути меншо ніж 1-3

ты хоть сам понимаешь то, что пишешь?
NaCl 
предатель Родины
С нами с 28.08.08
Посты: 24065
28.04.13 02:20 [Re: KillMachine UA] Ukraine #1568159
  • KillMachine UA :
  • Hac9lJlbHuKe :

зв'іязний графа це озачає що відстань від точок 1-2-3 може бути меншо ніж 1-3

ты хоть сам понимаешь то, что пишешь?

http://forums.vbios.com/showpost.php?post/1567483/ )))
Hac9lJlbHuKe 
BDSM expert. Атуечайу...
Hac9lJlbHuKe
Возраст: 25
: Дніпро
С нами с 09.09.09
Посты: 9189
28.04.13 19:22 [Re: KillMachine UA] Ukraine #1568325
  • KillMachine UA :
  • Hac9lJlbHuKe :

зв'іязний графа це озачає що відстань від точок 1-2-3 може бути меншо ніж 1-3

ты хоть сам понимаешь то, что пишешь?

А що там не зрозуміло?
ПОчатково граф повинен бути зв'яним,наскільки я розумію.
KillMachine UA 
генералиссимус
KillMachine UA
Возраст: 39
: Київ
С нами с 10.12.07
Посты: 25376
28.04.13 19:58 [Re: Hac9lJlbHuKe] Ukraine #1568338


1. ты пишешь на жутком суржике, причём с кучей опечаток

2. ты вместо чёткого изложения мыслей выдаёшь словесную кашу
Icon Legend Права Настройки темы
Распечатать тему


1051 Просмотры
Реклама
113 сейчас в онлайне
5 пользователей (Арбанов, Lam0, Omanaman, Din0saur, Joshua) и 1 скрытых, а также 107 гостей сейчас онлайн.
     
VBIOS Version 3.0 FINAL | ©1999-2020
Execution time: 0.132 seconds.   Total Queries: 73   Zlib сжатие вкл.
All times are (GMT+3). Current time is 05:08
Top