Предагаем поупражнятсья в написании простенькой программы. Приглашаются все желающие. Выбор языка программирования за вами — хотите, пишите на Clojure, Scala, JavaScript или Python, а хотите — пишите на Brainf*ck, нам всё равно 🙂 Оцениваться будет элегантность и простота решения, так что не стоит заморачиваться на супер-пупер-оптимальный алгоритм.
Итак, задание:
Дано дерево (структура данных такая), вершины которого имеют некий вес (размер) в условных единицах (у.е). Подразумевается, что дерево это надо переслать из системы А в систему Б по «трубе», пропускная способность коей ограничена заданной величиной. Задача состоит в том, чтобы разбить это дерево на поддеревья, так чтобы максимально эффективно использовать канал передачи данных с возможностью сборки изначального дерева на стороне получателя.
Иллюстрация к заданию
Исходное дерево:
Обратите внимание что дерево никак, не отсортировано — такое условие задачи!
buffer=40 означает, что пропускная способность канала будет 40 у.е., тем самым разбитое на части дерево будет выглядеть примерно так:
Таким образом, мы видим, что при разбивке получилось 3 дерева, размер которых не привышает 40 у.е.
Решения предлагаем присылать ссылкой на код в http://pastebin.com. Ждём ваших решений! Решившим респект и уважуха, а лучшему решению (по очень субъективным оценкам) — приз!
Кому лень придумывать свои данные для проверки, вот вам вариант для проб, копируйте как есть:
| buffer=40 A,8,- B,9,A C,1,A D,14,B E,4,D F,7,D G,11,F H,22,F I,17,C |
Андрей Филимонов
Боюсь показаться нетактичным, но, прочитав задание N раз, я так и не смог понять что всетаки требуется сделать 🙁
Нада «упаковать рюкзак» заданного размера любыми елементами набора, затем переслать, убедившись что все елементы набора дошли? Ведь очевидно что для восстановления такого дерева не важно связаны ли елементы в поднаборах, и в каком порядке они идут, если они все дойдут. Это ж самодостаточные элементы.
Или же всетаки важно упаковывать так, чтобы елементы в поднаборах были связанными деревьями имеющщими самостоятельную ценность? Мол инкрементально восстанавливать (рисовать) дерево после прихода каждого нового куска? В таком случае алгоритм будет крутоват 🙂
Пожалуйста уточните.
(или я, дурак, все не так понял?)
Антон Архипов
Самостоятельными элементами они быть не могут потому, что в задании сказано что в точке Б мы должны получить точно такое же дерево как и в точке А. Если ты будешь собирать куски в произвольном порядке, разве получишь идентичный результат?
Всё же просто! 🙂 Тебе дано дерево. Надо его переслать кусочками. Для этого тебе надо его разбить на части так, чтобы на другой стороне его можно было его снова собрать. Просто кусочки могут дойти до получателя вразнобой, второй кусок обгонит первый, например.
сделаем допущение, что налету собирать дерево не надо, что куски ТОЧНО придут все, но порядок негарантирован.
Артем
Давайте и я дураком поработаю 🙂
Правильно ли я понял из задания, что вес служебной информации равен 1 уе, соответственно вес вершины не может превышать 39 уе?
Антон Архипов
отличный вопрос! сделаем поправочку — у.е. это байты. Т.е. если ты сможешь уложить служебную инфу в 1 байт, то будет примерно как ты сказал, да 🙂
для большей правдоподобности можно бы использовать в дереве вместо «веса» например строки, тогда надо будет для каждой вершины вес подсчитывать. В задании какбы вес каждой вершины уже посчитан..
Андрей Филимонов
Почему не могут? В исходных данных задания у каждого элемента есть однозначная ссылка на родителя. Как по другому это можно трактовать? Как их не собирай, они соберутся единственным способом, в каком порядке их не посылай.
A,8,-
B,9,A
У элемента B с весом 9 всегда родитель — елемент А. Когда и куда бы он не пришел, и в каком порядке. Эго позиция в очереди не имеет значения, это связаный список. Как же так?
Рассмотрим вариант, когда елементы пришли в другом порядке.
B,9,A
A,8,-
Ничего не изменилось. У елемента В по-прежнему родитель А. И в дерево он встанет единственным образом.
Следовательно все что нам нужно — убедиться что все елементы были переравлены. А если это счтитать за данное — я вообще растерян. Задача сводится к решению тривиальной задачи «укладки рюкзака», так как мы вправе набирать «пакет» из абсолютно любых елементов набора, удовлетворяющих единственному критерию — критерию размера.
Что там с весами — значения не имеет. Нада ли оставлять буфер для контрольной информации или нет — детали. Я так понимаю что это все сильная абстракция какой-то реальной проблемы, которая имела место 🙂 but i digress
Неужели я не понимаю сути? Пожалуйста объясните, я серьезно не понимаю.
Антон Архипов
хмм. а ты прав! 🙂
Ну тем проще, не задо заморачиваться на служебную информацию и можно просто делить дерево по тем оценкам в соответствии с данным буфером 🙂 Я собственно даже уберу тогда условия эти из задания, т.к. в таком случае безсмысленны.
VLD
иногда в деревьях важно в какую сторону идёт ветка в «1», или в «0».
т.е. у каждого из детей помимо вершины родителя, должен присутствовать флаг («1» или «0»).
а максимально эффективно, я так понял, это за минимальное количество пакетов.
Антон Архипов
совершенно верно — за минимальное количество пакетов
VLD
у меня похожая проблема: есть ~140 SDA-шных папок общим размером около 115Гб.
и я это хочу скинуть на двд-рки с «пропускной способносью» 4.7Гб. 🙂
проблема усугубляется личными предпочтениями 🙁
Андрей Филимонов
«иногда в деревьях важно в какую сторону идёт ветка в “1″, или в “0″.
т.е. у каждого из детей помимо вершины родителя, должен присутствовать флаг (“1″ или “0″).»
Подкрепите, если не трудно, примером 🙂
VLD
SSBDD (Structurally synthesized binary decision diagrams)
помнится даже дипломную работу писал…
там каждая вершина несла информацию лишь о том инвертирована ли она
, и дерево кодировалась как
A: B, C
B: D, 0
C: 0, I
…
Антон Архипов
да, было, но это не имеет отношения к заданию в данный момент, как мы выяснили выше 🙂
Евгений Голобородько
Тоже не понимаю задачу 🙂
Можно получить ответы на следующие вопросы:
1. Обязательно чтоб отсылались в пакете именно поддеревья? Или это могут быть отдельные элементы?
2. Мы считая размер пакета оцениваем только вес всех вершин дерева? Количество служебной информации не важно (идентификатор вершины, идентификатор парента, если я ещё захочу поля добавить например левое или правое расположение)?
Если это так, то задача сводится всего лишь к тому чтоб разобрать дерево на поддеревья так, чтоб уложить в минимальное количество пакетов.
Антон Архипов
«Если это так, то задача сводится всего лишь к тому чтоб разобрать дерево на поддеревья так, чтоб уложить в минимальное количество пакетов.»
ты всё правильно понял. + дерево надо собрать на 2й стороне. задание простое, для того чтобы было меньше кода — так интересней оценивать экзотические решения
Aleksandr Motsjonov
На питоне правда. =) На жаве не интересно. Всё прямолинейно. http://pastebin.com/XaUJeJHc
Андрей Филимонов
Поскольку спам развел я, не буду избегать ответственности 🙂
Вот мое решение — «1D bin packing first-fit» алгоритм на скорую руку. http://pastebin.com/Zw1CFE3w
http://www.nodi.ee/devclub/homework.html — живая демострация. В кнопку можно тыкать много раз. Прошу прощения за вульгарное оформление.
Антон Архипов
Демонстрация — отпад! Спасибо!
не удержусь от комментария по коду:
for ( j in buffer_data_array ) { // пробегаем по всем буферам
за такой коммент в коде получишь кликуху «капетан очевидность» 🙂
Андрей Филимонов
Ха-ха, ну воот 🙂
Я просто пытался комментировать последовательно, как диктует алгоритм.
Кста… в демонстрацию можно запихать и свои данные через консоль фаербага или там хром. Я не стал делать интерфейс.
Демонстрацию я комментировать тоже не стал, там ничего интересного нет, только декорации.
Удивительно, но етот простой алгоритм довольно еффективно пакует. Я стал на ету тему гуглить — все современные «бин пакинг» алгоритмы в «научных бумагах» — за деньги. Аж грустно стало. Фик самостоятельно что сделаешь, если хочешь модно и бесплатно — сделаешь наверняка топор 🙁
Sergei Kirjanov
Разбиваю на поддеревья, как показано в задании.
Отрезаю максимальную влезающую в канал, свободную ветку.
Повторяю.
>> дерево надо собрать на 2й стороне
не понял. входные данные слишком абстрактны
http://pastebin.com/y6ivdCGd