Ten problem jest trudny NP . Aby to pokazać, najpierw przeformułuję ten problem (optymalizacji) na problem decyzyjny. Następnie przeformułowuję ten problem na równoważny, z którego dość łatwo jest uzyskać redukcję problemu k- kolorowania, który jest NP-trudny dla dowolnego k ≥ 3kk≥3 .
Krótkie sformułowanie problemu jest następujące:
Biorąc pod uwagę n osób i wykres G, który koduje ich relacje „dawanie prezentów”, znajdź minimalną wymaganą liczbę podróży, aby wszystkie prezenty można było kupić bez rujnowania niespodzianek.nG
Jest to jednak problem z optymalizacją. Klasa NP jest zwykle definiowana dla problemów związanych z usuwaniem błędów (gdzie odpowiedź na każde wystąpienie brzmi TAK lub NIE). Wariantem decyzji jest:
Podane n osób i wykres G , który koduje własnej strony „prezentów” stosunki i liczbę całkowitą t , robi co najwyżej t wycieczki wystarczy kupić wszystkie dary bez niszczenia żadnych niespodzianek?nGtt
Problem znalezienia właściwego ukierunkowanego t- wielokolorowegot grafu G = ( V , E ) definiuję jako znalezienie funkcji wielokolorowej c : V → P ( C ), która jest właściwa , gdzie C jest jakimś zestawem t „kolorów” ( tj. | C | = t ), a P ( C ) jest zbiorem mocy C (tj. zbiorem wszystkich podzbiorów CG=(V,E) c:V→P(C)Ct| do| =tP.( C)dodo). Funkcja wielokolorowa jest właściwa wtedy i tylko wtedy, gdy dla każdej krawędzi ( u → v ) ∈ E mamy to c ( u ) ⊈ c ( v ) .( u → v ) ∈ Ec(u)⊈c(v)
Zastrzeżenia patentowe że problem przelot handlowe odpowiada problemu zdecydowania istnienie skierowanej t -multicoloringt na tym samym wykresie G .G
Dowód : jeśli mamy odpowiednio ukierunkowane t - wielokolorowe c dla G , gdzie zmieniamy nazwy kolorów tak, że C = { 1 , … , t }, to rozważmy sekwencję t trip T 1 , … , T t , gdzie wierzchołek v idzie na zakupy w podróży T i wtedy i tylko wtedy, gdy i ∈ c ( v ) . Następnie dla każdej krawędzi ( u → v ) ∈ EtcGC={1,…,t}tT1,…,TtvTii∈c(v)(u→v)∈EMamy że istnieje podróży T i taka, że u ∈ ţ I i V U ) ⊈ C ( v ) . Dlatego wycieczki T iTiu∈Ti∉ T i , ponieważ c (v∉Tic(u)⊈c(v)Ti są wystarczające, aby kupić wszystkie prezenty.
Jeśli mamy sekwencję wyzwalania T 1 , … , T t , to konstruujemy funkcję wielokolorową c na zestawie kolorów C = { 1 , … , t } tak, że c ( u ) = { i ∈ N | U ∈ T I } . Następnie dla każdej krawędzi ( u → v ) ∈ E istnieje trip T i taki, że u ∈T1,…,TtcC={1,…,t}c(u)={i∈N|u∈Ti}(u→v)∈ETi T I i V ∉ T í (ponieważ u można kupić prezent dla vu∈Tiv∉Tiuv o pewien TRIP), co oznacza , że ∈ C ( U ) i I ∉ c ( v ) , to C ( U ) ⊈ C ( v ) . ◻i∈c(u)i∉c(v)c(u)⊈c(v)□
Znalezienie właściwego skierowaną t -multicoloring jest po prostu dziwne przeformułowanie przypadku określonego w k -coloring. Dlatego mogę pokazać wielomianową redukcję czasu od ( ttk⌊ T / 2 ⌋ ) -coloring problemów: Biorąc pod uwagę nieukierunkowane wykresG'=(V',E')najpierw przekształcenia tego wykresu na skierowanej wykresG=(V,E), tak, żeV=V"i(U→v)∈Ewtedy i tylko wtedy, gdy(u,v)∈E′lub(v,u(t⌊t/2⌋)G′=(V′,E′)G=(V,E)V=V′(u→v)∈E(u,v)∈E′ ) ∈E ′(v,u)∈E′ (innymi słowy zmieniamy nieukierunkowane krawędzie na dwie skierowane krawędzie).
Rozważ największy zbiór K ⊂ P ( C ) , taki, że nie ma żadnego a , b ∈ K , a ≠ b , taki, że a ⊂ b . Zbiór wszystkich podzbiorów C o rozmiarze ⌊ t / 2 ⌋ , gdzie t = | C | , jest takim zestawem. Dlatego maksymalny rozmiar takiego podzbioru wynosi ( tK⊂P(C)a,b∈Ka≠ba⊂bC⌊t/2⌋t=|C|⌊t/2⌋)(t⌊t/2⌋).
If a proper tt-multicoloring exists for GG, then there exists a proper coloring that uses no more than (t⌊t/2⌋)(t⌊t/2⌋) unequal elements from P(C) P(C) (*), so this is a valid (t⌊t/2⌋)(t⌊t/2⌋)-coloring for G′G′.
If a proper (t⌊t/2⌋)(t⌊t/2⌋)-coloring exists for G′G′, then there exists a set K⊂P(C)K⊂P(C), |C|=t|C|=t, such that |K|≥(t⌊t/2⌋)|K|≥(t⌊t/2⌋) and there does not exist any a,b∈Ka,b∈K, a≠ba≠b, such that a⊂ba⊂b. So, GG has a proper directed tt-multicoloring.
Therefore, this is a valid polynomial time reduction from (t⌊t/2⌋)(t⌊t/2⌋)-coloring to the present shopping problem with tt trips, which means the present shopping problem is NP-hard. Note that the present shopping problem is NP-complete, since we can verify easily if a given list of at most tt trips allows us to buy all presents without ruining surprises.
(*): If some multi-coloring CC uses more color-sets than a maximal 'non-subset' multi-coloring C∗C∗, we can 'rename' CC such that it is a superset of C∗C∗. CC remains proper, as none of the elements from C∗C∗ being adjacent to a different element from C∗C∗ is a problem and none of the color-set were adjacent to each-other in the original CC. So, without loss of generality, we can assume C∗⊂CC∗⊂C.
Then, note that 'renaming' C∖C∗C∖C∗ to any subset of C∗C∗ does not ruin the edges between nodes of color-sets C∖C∗C∖C∗, since C∗C∗ contains no elements that are a subset of another. The only thing that is left is to ensure that the edges between C∖C∗C∖C∗ and C∗C∗ do not 'ruin' the coloring.
Consider the following relation RR on the color-sets in C∪C∗C∪C∗: two color-sets AA and BB are connected if and only if there exists a pair of vertices a,ba,b such that aa has color-set AA and bb color-set BB and (a,b)∈E(a,b)∈E. This relation can be represented by the undirected graph G=(C∪C∗,R)G=(C∪C∗,R).
First, we can 'reduce' C∖C∗C∖C∗ by replacing any pair that does not have an edge in GG by a single color-set. The coloring remains proper, since changing two colorsets that are not adjacent at all into the same color does not introduce any invalid edges. As a result, we have reduced GG to a complete graph.
This means that if GG has a less or equal amount of color-sets as |C∗||C∗|, the required coloring exists. Otherwise, there exists no proper multi-coloring at all, since C∗C∗ is a largest 'non-subset' set, so we are unable to color this clique. Therefore, the required multi-coloring necessarily exists.
As the complete graph on nn nodes KnKn is color-able if and only if we have at least nn colors, we have that nn people can go shopping presents for each other in tt trips if and only if (t⌊t/2⌋)≥n(t⌊t/2⌋)≥n. This means in particular that, if n≤12870n≤12870, making only 1616 trips is sufficient. If there are fewer presents to buy, more trips won't be needed, so this is a general upper bound on every solution.
Below is my earlier 'answer', which gives a heuristic algorithm that does not guarantee to get the optimum, but can be computed in polynomial time.
Another way to formulate this problem is to find a covering C={(S1,T1),…,(Sm,Tm)}C={(S1,T1),…,(Sm,Tm)} of bipartite graphs on the partitions (Si,Ti)(Si,Ti) for some directed graph GG with nn nodes, such that the amount of partitions (i.e. trips), here mm, is minimal.
First, some observations, partially coming from other answers:
- The greedy strategy, where we pick a (Si,Ti)(Si,Ti) with a bipartite graph where the amount of edges in common with GG is maximal, does not lead to an optimal solution (A strong counter-example is the full graph with 66 nodes, where this strategy fails, no matter which maximum bipartite graph is chosen.).
- The greedy strategy is not optimal for arbitrary acyclic graphs, consider the following graph:
Both for Si={3,5,6}Si={3,5,6} and Si={1,3,6}Si={1,3,6} the bipartite graph removes 44 edges, but only {3,5,6}{3,5,6} is optimal.
- Any (optimal) greedy algorithm cannot prefer the size of the partition chosen over the amount of cycles (of any size) 'removed' by the partition. To see this, consider the graph with n+2n+2 nodes, where there is one cycle of nn nodes and every node in the cycle has 22 additional outgoing edges towards 22 additional nodes A,BA,B, which have no outgoing edges (See figure below for an example where n=4n=4). A greedy choice that prefers to maximize the amount of edges over cycles of length nn will send all vertices in the cycle on the first trip. This is suboptimal, as this does not remove any edges of the cycle and simply ignoring A,BA,B and removing all edges from the cycle removes all edges towards A,BA,B as well. So any greedy choice that prefers the size of the partition over removing a cycle is not optimal.
Based on these observations, I propose the following greedy choice: Pick (Si,Ti)(Si,Ti) such, that the amount of cycles that this trip 'removes' from GG is maximal and in case of ties, choose a partition with maximum overlap with GG among them (i.e. look at the edges not on cycles).
Since this algorithm isn't different from the 'basic' greedy strategy on acyclic graphs (removing a maximum amount of edges on every trip), this greedy algorithm therefore is not optimal. However, the intuition of removing cycles still makes sense and is an improvement over the basic greedy strategy, so it could be a decent heuristic.
I can see how to reduce this problem to Graph Colouring, which gives you a tool for solving the problem (for small instances!), but not yet how to reduce in the other direction (which would establish NP-hardness).
The basic idea is to build a graph that contains a vertex for every purchase, and an edge between any two purchases that cannot occur on the same trip; we then look to group the purchases into the smallest possible number of groups ("trips"), such that no two purchases in the same group would conflict. Specifically, if G=(V,E)G=(V,E) is the original directed graph in which an edge uvuv indicates that person uu needs to buy person vv a gift, then create an undirected graph H=(X,Y)H=(X,Y) in which there is a vertex xuvxuv for each edge uvuv in GG and an (undirected) edge xuvxvwxuvxvw whenever uvuv and vwvw are both (directed) edges in GG (if vv buys some ww a gift during a trip, then no one can buy vv a gift during that same trip). A vertex colouring of HH is a partition of the necessary purchases (vertices in HH ) into trips (colours) that don't conflict (share an edge), and a vertex colouring of minimum size takes the fewest possible trips.
It might be possible to go in the other direction (reduce Graph Colouring, or some other NP-hard problem, to your problem, and thereby establish its NP-hardness), by adapting a reduction from 3SAT to Graph Colouring (as, e.g., detailed on p. 10 of Jeff Erickson's notes), but I haven't attempted this myself.
źródło
It's the kind of problem where I would be very worried if my boss asked my to implement an algorithm that is guaranteed to find an optimal solution in reasonable time.
To find a not necessarily optimal solution: Given any set of people and presents to buy, we can count how many presents a group of people can buy on a shopping trip. So start with an empty group (which can buy 0 presents). For each person not in the group, determine how many presents can be bought if that person is added to the group. If there is any person that we can add without decreasing the number of presents, pick at random one of those that increase the number of presents bought by the maximum amount, until adding any person would reduce the number of presents bought. Then do that shopping trip and start all over until all presents are bought.
I'd repeat a few times, picking different people "at random" in case that finds a better solution.
In the example, five people having to buy a present for each other, this finds a solution in four trips, which is optimal; if we didn't add persons to a trip that leave the number of presents unchanged without improving it, we would have five trips. And 6 people require 5 trips.
źródło
Assume that you order the people based on who they are receiving from (parent), and who they are giving to (child). Since everyone gives one present and receives one present, parent-child function is one-to-one.
You never want to put the parent and the child into the same group. You start with a random person p1 and order everyone accordingly, so child(p1)=p2, etc. You put all podd into one group, and all peven into another group. For the last person pn=parent(p1), so you don't want this person to be in the same group with p1. If n is even, it is not a problem. Else, you need one additional group, that can be just pn by itself, in the simplest case.
This algorithm assumes everyone is connected. But it does not need to be the case. If there are multiple disconnected cycles, in other words, if at some point, pk=parent(p1) where k!=n, then you finish that circle and start with a new one, following the same algorithm. As long as you don't merge the odds and evens of the same cycle, you can merge disconnected cycles.
This algorithm ends up with at most 2 rounds (for even n) and 3 rounds (for odd n).
źródło