Най-добрият алгоритъм за канене на хора на парти

Нов съм тук, но имам въпрос, намерен в моя учебник. За съжаление няма отговори, така че се чудех дали някой може да помогне. Въпросът е:

Получавате задачата да разпространявате покани в рамките на една компания. Имате време да говорите само с определен брой хора, но ви е гарантирано, че ако поканите някого, той ще покани своя шеф, този човек ще покани своя шеф и така нататък, чак до главния изпълнителен директор. Начертали сте цялата йерархия на компанията и сте присвоили стойност на всеки човек, показвайки колко ценно би било да ги поканите. Като се има предвид тази настройка и ограничението за броя на хората, с които можете да говорите, искате да изчислите оптималния набор от хора, които да поканите. Оптимален набор от хора ще увеличи максимално общата стойност на всички лица, поканени, пряко или непряко, от вашия избор.

Ще има точно един човек, главният изпълнителен директор, без шеф в йерархията. Всички други хора в крайна сметка ще отговарят на този човек по командната верига, но не непременно директно.

Гарантирано ви е, че всеки човек ще има най-много един шеф, но този шеф може да има друг на свой ред. Например, лице A може да има шеф B, чийто шеф е C, чийто шеф е D, чийто шеф е CEO. По този начин влиянието върху лице A автоматично ще повлияе на B, C, D и главния изпълнителен директор.

Различни служители може да имат общи шефове в командната верига. Вие НЕ получавате допълнителна стойност за влияние върху човек повече от веднъж. Например, ако A и B отговарят директно на изпълнителния директор и вие влияете и на двамата, ще получите стойност val(A)+val(B)+val(CEO), а не val(A)+val(B) +2val (изпълнителен директор).

Дадено е положително цяло число j, изберете j души, които в крайна сметка ще доведат до най-голямата обща стойност.

Знам, че подходът на груба сила е просто да търсите в списъка максималната стойност j пъти, но това не е много полезно. Мисля, че има подход за динамично програмиране, но опитът ми не винаги дава правилния отговор. Всяка помощ ще бъде оценена!


algorithm hierarchy math tree dynamic-programming
person Agir Mahad    schedule 12.11.2014    source източник
comment
От гледна точка на йерархията е малко по-сложно от избора на най-ниските хора: някои от тях може да имат общ прародител!   -  person Rerito    schedule 12.11.2014
comment
Точно така – Един подход, който опитах, беше да премина през тези служители от най-ниско ниво, да избера максимума и да актуализирам стойностите на другите, но все още е изключително бавен и определено не е оптимален.   -  person Agir Mahad    schedule 12.11.2014
comment
За да изясним, какво е ограничението - броят на хората, които могат да присъстват на партито, или броят на поканите, които можете да напишете? (Не е същото, защото някои хора са поканени индиректно)   -  person Colonel Panic    schedule 17.11.2014
comment
ОП, пробвал ли си алчен алгоритъм? Можете ли да докажете, че е оптимално? Ако не, кога се обърка? Това вдъхновява ли нов алгоритъм?   -  person Colonel Panic    schedule 17.11.2014
comment
Гласувайте да останете отворени - това е добре написан и внимателно дефиниран проблем с алгоритмите. (Въпреки че би било по-добре с пример.)   -  person Colonel Panic    schedule 17.11.2014

Отговори (3)


arrow_upward
5
arrow_downward

Нека V[e, k] е максималната стойност на издаване на k покани до e и преки и непреки подчинени на e, като се игнорира стойността на всички преки и непреки ръководители на e. Ако служител e няма подчинени, тогава основният случай е

V[e, k], k = 0 = 0
V[e, k], k > 0 = val(e).

Ако служител e0 има двама подчинени, e1 и e2, тогава повторението е

V[e0, k], k = 0 = 0
V[e0, k], k > 0 = max over j of val(e0) + V[e1, j] + V[e2, k - j].

Наивната конволюция с повече от двама служители е твърде бавна, така че трябва да конволираме първата двойка и след това да конволираме останалите. Ще пропусна подробностите.

person David Eisenstat    schedule 12.11.2014
comment
@David - определено е оптимално да изберете служителя с най-голяма пределна стойност. Имате ли някакъв псевдокод, който да покаже, че това може да бъде завършено за по-малко от O(n^k)? Това би бил подход в стил груба сила. - person Agir Mahad; 12.11.2014
comment
@AgirMahad: Ако маркирате вече поканени хора, тогава, за да отбележите конкретен човек, трябва просто да се качите нагоре по дървото, докато не ударите първия вече поканен човек (всеки човек над това също е задължително вече поканен). Това ще отнеме най-много n стъпки и има най-много n души за отбелязване, така че намирането на най-добрия човек за добавяне ще бъде в най-лошия случай O(n^2). Има k стъпки, така че като цяло е O(kn^2). - person j_random_hacker; 12.11.2014
comment
Всъщност @Nemo изглежда е прав. Тази страница в Уикипедия дори споменава проблема с максималното покритие, който е NP-труден и който е само леко обобщение на този проблем. - person j_random_hacker; 12.11.2014
comment
@j_random_hacker Да, не съм буден. Отговорът е напълно пренаписан. - person David Eisenstat; 12.11.2014
comment
@DavidEisenstat - не съм сигурен, че разбирам какво имаш предвид под convolve? Разбирам основните случаи и случая, когато има двама служители, но не съм сигурен какво имате предвид като как да разширите това до множество подчинени (3, 4 или повече). Всяка допълнителна помощ би била страхотна. Благодаря ви, че ми помагате да разбера по-добре. Актуализация: вашето повторение за 2 подчинено O(nk^2) ли е? - person Agir Mahad; 12.11.2014
comment
@AgirMahad Да за вашата актуализация. Наивната 3-подчинена версия би била max over j1, j2 of val(e0) + V[e1, j1] + V[e2, j2] + V[e3, k - j1 - j2], което е O(nk^3). За да предпазим експонентата от взривяване с повече подчинени, пренаписваме на max over j1 of max over j2 of ... и след това куп изчисления за вътрешния макс се споделят. - person David Eisenstat; 13.11.2014
comment
@DavidEisenstat Тогава O(nk^2) най-добрият ли е? Мисля, че може да съм измислил подход O(nk), но не съм сигурен дали работи. Опитвах се да мисля за подход „разделяй и владей“, при който разделям йерархията на подчинени, но няма ясен начин да се определи кой е най-добрият, без първо да достигне дъното на съответния път. Може също да се преобразува в проблем с най-дългия път, но тогава ще бъде приблизително време на изпълнение O(nk^2 + ..). Благодаря ви отново за помощта. - person Agir Mahad; 13.11.2014

arrow_upward
1
arrow_downward

Редактиране: този отговор предполага, че всички стойности за поканване на хора са неотрицателни.

Този проблем може да бъде решен с помощта на алчен алгоритъм. Нека първо обсъдим случая, при който всички стойности са равни, така че просто се опитваме да поканим максимален брой хора. Основното наблюдение е, че във всяко оптимално решение винаги трябва да избирате лицето с най-голям брой преки или непреки началници. Ето кратко обяснение защо: да предположим, че човек X има най-много началници и имате някои селекции, които не включват човек X. Помислете за лицето Y сред вашите избори, което споделя най-много превъзходства с X. Тогава можете да се справите по-добре, като изберете X вместо Y.

Така че в първата стъпка винаги можем алчно да изберем човека с най-много началници. След това проблемът се свежда до същия проблем на няколко по-малки дървета. Да предположим например, че избираме 3 поканени от следното дърво:

       A
   B       C
 D   E   F   G
H I J K L M N O

Първият ни избор ще бъде H, което автоматично ни дава D, B и A. След това, остава да изберете 2 от трите дървета

I   E      C
   J K   F   G
        L M N O

Следващият най-добър избор е L и т.н.

Можем да направим това ефективно, защото просто трябва да следим най-дълбокото дете (не непременно директно дете) на всеки възел, което можем да изчислим предварително. След това се нуждаем от някаква приоритетна структура от данни на опашка, за да изберем най-доброто дърво, от което да изберем. Ако избирате k души от йерархия с размер n, това трябва да даде алгоритъм O(n + k log n).

За да разширите това до случая, когато стойностите може да са неравни, по принцип работи същата идея, освен че вместо дълбочина трябва да изчислите общата стойност на всички висши. За всеки възел X следите дъщерния Y, който има най-голямата обща стойност по пътя между Y и X.

person arghbleargh    schedule 15.11.2014
comment
Мисля, че има проблем с алчния подход, ако стойността на възел може да бъде отрицателна. - person Jason L; 17.11.2014
comment
Добра точка, това работи само ако стойностите са неотрицателни, което предположих, че е така. Но предполагам, че проблемът има смисъл и с отрицателни стойности. - person arghbleargh; 18.11.2014

arrow_upward
0
arrow_downward

Звучи като проблем с графика. Можете да използвате идеята за свързани компоненти, за да реализирате решение за това.

  • Първата итерация ще обхване всички в компанията, където ще определите кой е главният изпълнителен директор и кой е директно под него.
  • Вземете всеки от шефовете директно под главния изпълнителен директор като първоначален набор от компоненти.
  • След това за всеки друг човек ще използвате dfs, за да ги свържете с шеф от 2-ро ниво (Това е динамичният подход).
  • Искате да направите тази последна част по такъв начин, че ако person F е шефът на person E, който от своя страна е шефът на person D, ... чак до person A, тогава искате след dfs да можете да кажете в O(1) време това лице F е шеф на лице A и обратно.

Не забравяйте да поддържате брой за всеки бос, където броят ще бъде сумата от стойностите на всички лица под него и по желание следете броя на хората.

Оптималният случай би бил първо да намерите всички хора по-ниско във веригата, в противен случай алгоритъмът трябва да работи в O(nk), където k е максималната верига отдолу нагоре

person smac89    schedule 15.11.2014