| Пользователь |
Сообщение: С графи (Тема#72687) |
Hac9lJlbHuKe
BDSM expert. Атуечайу...
Возраст: 29
 : Дніпро
С нами с 09.09.09
Посты: 9566
|
Треба постановочка задачі"
Имеется n населенных пунктов, в каждом из которых живет pi школьников (i=1,...,n). Надо разместить школу в одном из них так, чтобы общее расстояние, проходимое всеми учениками по дороге в школу, было минимальным."
Тут явно треба буде мутити з найменшими відстанями і відповідно будувати дерево,але може в кого був досвід саме з такою ось рпограммою, постановку задачі буду обговорювати з преподом,бо багато всяких пеньків в розумінні того,як це все буде виглядати і від чого відсштовхуватись.
Нехай учні це і,а пункти(школи) n, то відштовхуємось до учнів помножених на шлях(h) потім знайти оптимальний шлях,де це i*n буде мінімальним, сам пункт,де буде розташована школа можна буде прийняти за 0, от тільки як це все хоча-б для початку графічно зообразити,теоретично від кожного n повинна йти дорога до всіх інших n, тобто спочатку буде зв'язний граф,який має перетворитись у дерево. Хто що підскаже з цього приводу?
Отредактировано Hac9lJlbHuKe 25.04.13 18:33. Причина редактирования: Причина не указана.
|
|
|
|
Nameless
Maximus - Lite Edition
: 404
С нами с 02.11.05
Посты: 21233
|
я опять не понимаю, что тебе нужно. Какая постановка задачи?
Задача в лоб решается так: есть граф населенных пунктов, перебираются все вершины, как потенциальное место для школы, из каждого узла высчитывается кратчайший путь до школы, множится на количество учеников, суммируются расстояния от всех вершин до вершины со школой. Из всех узлов выбирается тот, который минимизирует суммарный путь. Как найти наименьшее расстояние от города до школы? Гугл "a * search" и разбирайся. Алгоритм не оптимальный конечно.
|
|
|
|
Nameless
Maximus - Lite Edition
: 404
С нами с 02.11.05
Посты: 21233
|
|
с целью оптимизации можно заранее один раз высчитать все кратчайшие расстояния между узлами (не пересчитывая дваджы p(i,j) и p(j,i), где р -- расстояние), сохранить их и использовать для расчета оптимальности расположения школы.
|
|
|
|
Hac9lJlbHuKe
BDSM expert. Атуечайу...
Возраст: 29
: Дніпро
С нами с 09.09.09
Посты: 9566
|
|
дякую,трохи прояснив для себе. ну вибачте,що не зрозуміло,я тільки вчусь.
|
|
|
|
Hac9lJlbHuKe
BDSM expert. Атуечайу...
Возраст: 29
: Дніпро
С нами с 09.09.09
Посты: 9566
|
|
Из всех узлов выбирается тот, который минимизирует суммарный путь. .
вузлів чи вершин? 0_о
|
|
|
|
Nameless
Maximus - Lite Edition
: 404
С нами с 02.11.05
Посты: 21233
|
|
какая разница как назвать? node == vertex, etc )
|
|
|
|
NaCl
предатель Родины
С нами с 28.08.08
Посты: 24065
|
оффтоп
я никак не могу понять - неужели они между собой также общаются? говорят кучу слов, каждое из которых по отдельности что-то значит, а вкупе являются набором звуков.
ЗЫ
я не про математику, а внятность изложения мысли.
|
|
|
|
Nameless
Maximus - Lite Edition
: 404
С нами с 02.11.05
Посты: 21233
|
|
|
|
Hac9lJlbHuKe
BDSM expert. Атуечайу...
Возраст: 29
: Дніпро
С нами с 09.09.09
Посты: 9566
|
Просто вузол і вершина це таки дуже різні речі,ось мене й запутало.
ПО-суті я вирішив - буду втілювати це дійство через массиви,а самі графи записувати як матриці. Але гемору ще багато, треба досконало розібратись як писати массиви, бо в мене з ними практика зовсім примітивна,рядки,стобці , редагування та видалення -"Малавата будет"
|
|
|
|
KillMachine UA
генералиссимус
Возраст: 43
: Київ
С нами с 10.12.07
Посты: 25376
|
двумерный массив - int eklmn [число пунктов][4]
{номер}
{Х, У, число учеников, результат}
перебор по номеру, рассчет расстояний по прямой до остальных точек, умноженных на количество учеников в тех точках -> результат (с округлением до целого)
сортировка результатов
|
|
|
|
Nameless
Maximus - Lite Edition
: 404
С нами с 02.11.05
Посты: 21233
|
|
не, если бы так все было просто, то это было бы не задание, а тривиальщина и граф был бы не нужен (и не факт, что даже координаты вершин есть в наличии). Предполагается, что граф связный, но не все вершины связаны между собой напрямую и кратчайшее расстояние -- это не всегда расстояние по прямой, а возможно путь через несколько других вершин, который еще нужно найти. Насяльнике, я правильно понял?
|
|
|
|
KillMachine UA
генералиссимус
Возраст: 43
: Київ
С нами с 10.12.07
Посты: 25376
|
|
поскольку в условии не написано, что школота не может ходить напрямую, то какой смысл усложнять?
|
|
|
|
Nameless
Maximus - Lite Edition
: 404
С нами с 02.11.05
Посты: 21233
|
|
я не усложняю. Если б можно было ходить напрямую, графы тут были бы до одного места.
|
|
|
|
Hac9lJlbHuKe
BDSM expert. Атуечайу...
Возраст: 29
: Дніпро
С нами с 09.09.09
Посты: 9566
|
|
не, если бы так все было просто, то это было бы не задание, а тривиальщина и граф был бы не нужен (и не факт, что даже координаты вершин есть в наличии). Предполагается, что граф связный, но не все вершины связаны между собой напрямую и кратчайшее расстояние -- это не всегда расстояние по прямой, а возможно путь через несколько других вершин, который еще нужно найти. Насяльнике, я правильно понял?
Думаю,ти правий, я ж сказав - зв'іязний графа це озачає що відстань від точок 1-2-3 може бути меншо ніж 1-3. Все вірно.
|
|
|
|
KillMachine UA
генералиссимус
Возраст: 43
: Київ
С нами с 10.12.07
Посты: 25376
|
|
зв'іязний графа це озачає що відстань від точок 1-2-3 може бути меншо ніж 1-3
ты хоть сам понимаешь то, что пишешь?
|
|
|
|
NaCl
предатель Родины
С нами с 28.08.08
Посты: 24065
|
|
|
|
Hac9lJlbHuKe
BDSM expert. Атуечайу...
Возраст: 29
: Дніпро
С нами с 09.09.09
Посты: 9566
|
зв'іязний графа це озачає що відстань від точок 1-2-3 може бути меншо ніж 1-3
ты хоть сам понимаешь то, что пишешь?
А що там не зрозуміло?
ПОчатково граф повинен бути зв'яним,наскільки я розумію.
|
|
|
|
KillMachine UA
генералиссимус
Возраст: 43
: Київ
С нами с 10.12.07
Посты: 25376
|
1. ты пишешь на жутком суржике, причём с кучей опечаток
2. ты вместо чёткого изложения мыслей выдаёшь словесную кашу
|
|
|
|
Форумы
Серверы
Суспільство
