JP6190773B2 - Problem solving apparatus, method, and program - Google Patents

Description

  The present invention relates to a problem solving apparatus, method, and program, and more particularly, to a problem solving apparatus, method, and program for solving a tree-constrained knapsack problem.

Conventionally, when a knapsack with capacity C and a tree with N nodes corresponding to items are provided for each node, and the capacity and value of the items are c _i and p _i , respectively, a range not exceeding the capacity C of the knapsack There is a known problem of selecting a rooted subtree that maximizes value. This problem is called a tree-constrained knapsack problem, and is used in application technologies such as LATN (Local Access Telecommunication Network), document summarization, and sentence compression.

  The tree-constrained knapsack problem is formulated as the following integer programming problem.

When x _i = 1, it indicates that the i-th item is selected as a node of the rooted subtree. Equation (1) is an objective function for maximizing value, and Equations (2) and (3) are constraints. Equation (2) ensures that the sum of the capacities of the items included in the selected rooted subtree does not exceed the knapsack capacity C. Equation (3) ensures that the selected item is a rooted subtree. Parent (i) is the item ID of the parent of the i-th node. The optimal solution can be obtained using a branch and bound method (using a general-purpose ILP solver) or dynamic programming (Non-Patent Documents 1 and 2).

Lukes, J. A. “Efficient algorithm for the partitioning of trees.” IBM Journal of Research and Development, 18 (3), 217-224. (1974) Morita, H., Sasano, R., Takamura, H. and Okumura, M. “Subtree Extractive Summarization via SubmodularMaximization.” Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, 1023-1032. (2013)

Since the branch and bound method described in Non-Patent Documents 1 and 2 is a method of enumerating solutions while branch-hunting the search tree, the solution can be efficiently solved depending on the capacity C of the knapsack and the number of nodes (number of items) N of the tree. Can't get. Furthermore, there is a problem that the processing speed varies greatly depending on the ILP solver program to be used. In addition, since the dynamic programming methods proposed so far have a calculation amount of O (NC ² ), there is a problem that calculation efficiency is poor depending on the value of C.

  The present invention has been made to solve the above problems, and an object of the present invention is to provide a problem solving apparatus, method, and program capable of solving a tree-constrained knapsack problem at high speed.

  In order to achieve the above object, the problem solving apparatus according to the first invention selects a rooted subtree that maximizes the value below the capacity limit C, from a tree structure composed of nodes each having value and capacity. A problem solving apparatus that solves a tree-constrained knapsack problem, wherein the nodes constituting the tree structure are rearranged in a depth-first order from the root of the tree structure, and the sorting unit arranges the nodes According to the order of each replaced node, the n-th node is a rooted subtree in which the n-th node can be added to each capacity c (0 ≦ c ≦ C), and the sum of the capacities of the nodes Among the rooted subtrees having the same value as the capacity c, by repeatedly calculating the rooted subtree having the maximum value of the nodes of the rooted subtree, the sum of the values of the nodes of the rooted subtree is maximized. And an optimum value calculation unit that calculates the maximum value of the sum of the values of each node and stores them in the storage unit for the rooted subtree at each growth stage. A rooted portion where the sum of the values of the nodes of the rooted subtree is maximized among the rooted subtrees that are less than or equal to the capacity limit C based on the calculation process repeatedly calculated by the optimum value calculation unit. A backtrack unit that outputs a tree, wherein the optimum value calculation unit is a rooted subtree to which an nth node can be added, and the sum of the capacities of the nodes is equal to the capacity c Among them, when calculating a rooted subtree that maximizes the sum of the values of each node of the rooted subtree, the maximum value of the sum of the values of each node stored in the storage unit for the rooted subtree of each growth stage The A rooted subtree to which an nth node can be added, and a rooted subtree including an (n-1) th node in which the sum of the capacities of each node is equal to the capacity c, and an nth node Among the rooted subtrees that can be added and that do not include the (n-1) th node whose sum of capacities of the nodes is equal to the capacity c, the sum of the values of the nodes of the subtree Recursively computes the rooted subtree for which

  Further, in the problem solving apparatus according to the first invention, the optimum value calculation unit uses the following equation (5) to calculate the combination of the nth node and the capacity c stored in the storage unit: An array for storing the maximum sum S [n] [c] of the value of each node for each is initialized, and the following expression (6) is used for each combination of the nth node and the capacity c. Then, the maximum sum S [n] [c] of the values of the nodes for the combination may be calculated and stored in the array stored in the storage unit.

  However, A [n] represents the nth node, the function cap (A [n]) represents the capacity of the nth node, and p (A [n]) represents the value of the nth node. The function next_undesc (h) represents a function that returns the index of the first node that is not a descendant of the h-th node among the h + 1 and subsequent nodes.

  The problem-solving method according to the first invention solves the tree-constrained knapsack problem of selecting a rooted subtree that maximizes the value below the capacity limit C from a tree structure composed of nodes having value and capacity. A problem solving method in the problem solving apparatus, wherein the sorting unit rearranges each node constituting the tree structure in a depth-first order from the root of the tree structure, and an optimum value calculation unit includes: In accordance with the order of the nodes rearranged by the sorting unit, for the nth node, a rooted subtree that can add the nth node to each capacity c (0 ≦ c ≦ C), and Among the rooted subtrees in which the sum of the capacities of the nodes is equal to the capacity c, the rooted subtree having the maximum sum of the values of the nodes of the rooted subtree is repeatedly calculated, thereby obtaining the rooted subtree. Gradually growing a rooted subtree with the largest sum of node values, calculating a maximum sum of values of each node for the rooted subtree in each growth stage, and storing it in a storage unit; Based on the calculation process in which the backtrack unit is repeatedly calculated by the optimum value calculation unit, among the rooted subtrees that are less than or equal to the capacity limit C, the rooting that maximizes the sum of the values of the nodes of the rooted subtree And outputting the subtree. The step of calculating by the optimum value calculation unit is a rooted subtree to which the nth node can be added, and the capacity of each node is calculated. Among the rooted subtrees whose sum is equal to the capacity c, when calculating the rooted subtree having the maximum value of each node of the rooted subtree, the rooted portion of each growth stage is calculated. N is a rooted subtree that can be added to the nth node by calling the maximum sum of the values of the nodes stored in the storage unit, and the sum of the capacities of the nodes is equal to the capacity c. A rooted subtree including the −1st node and a rooted subtree to which the nth node can be added, and does not include the n−1th node in which the sum of the capacities of the nodes is equal to the capacity c. Among the rooted subtrees, a rooted subtree that maximizes the sum of the values of the nodes of the subtree is recursively calculated.

  In the problem solving method according to the first aspect of the present invention, the step of calculating by the optimum value calculating unit uses the following equation (8) to store the nth node and the capacity stored in the storage unit: For each combination of c, an array storing the maximum sum S [n] [c] of the values of the nodes is initialized, and for each combination of the nth node and the capacity c, the following (9 ) May be used to calculate the maximum sum S [n] [c] of the values of the nodes for the combination and store it in the array stored in the storage unit.

  However, A [n] represents the nth node, the function cap (A [n]) represents the capacity of the nth node, and p (A [n]) represents the value of the nth node. The function next_undesc (h) represents a function that returns the index of the first node that is not a descendant of the h-th node among the h + 1 and subsequent nodes.

  A program according to the first aspect of the present invention is a program for causing a computer to function as each part constituting the problem solving apparatus according to the first aspect of the present invention.

  According to the problem solving apparatus, method, and program of the present invention, for the n-th node, a rooted subtree capable of adding the n-th node to each capacity c (0 ≦ c ≦ C), and Among the rooted subtrees in which the sum of the capacities of the nodes is equal to the capacity c, the value of each node of the rooted subtree is calculated by repeatedly calculating the rooted subtree having the maximum sum of the values of the nodes of the rooted subtree. The rooted subtree with the largest sum is gradually grown, and for the rooted subtree at each growth stage, the maximum sum of the values of each node is calculated and stored in the storage unit, and the rooted part at each growth stage N is a rooted subtree in which the nth node can be added by calling the maximum sum of the values of each node stored in the storage unit for the tree, and the sum of the capacities of the nodes is equal to the capacity c -1st node A rooted subtree including a rooted subtree to which an nth node can be added, and a rooted subtree not including the (n−1) th node in which the sum of the capacities of the nodes is equal to the capacity c, By recursively calculating the rooted subtree that maximizes the sum of the values of the nodes of the subtree, the effect of being able to solve the tree-constrained knapsack problem at high speed is obtained.

It is a block diagram which shows the structure of the problem solving apparatus which concerns on embodiment of this invention. It is a conceptual diagram of the tree structure comprised from each of a node with value and capacity. It is a figure which shows the algorithm which determines each element stored in the two-dimensional array S and B. 3 is a conceptual diagram illustrating an example of each element of a two-dimensional array S. FIG. 3 is a conceptual diagram illustrating an example of each element of a two-dimensional array B. FIG. It is a figure which shows the algorithm of a backtrack. It is a flowchart which shows the problem-solving process routine in the problem-solving apparatus which concerns on embodiment of this invention. It is a flowchart which shows the maximum value calculation process routine in the problem-solving apparatus which concerns on embodiment of this invention. It is a flowchart which shows the sibling element determination processing routine in the problem solving apparatus which concerns on embodiment of this invention. It is a flowchart which shows the backtrack process routine in the problem-solving apparatus which concerns on embodiment of this invention.

  Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.

<Configuration of Problem Solving Device According to Embodiment of the Present Invention>

  The configuration of the problem solving apparatus according to the embodiment of the present invention will be described. As shown in FIG. 1, a problem solving apparatus 100 according to an embodiment of the present invention includes a CPU, a RAM, and a ROM that stores a program and various data for executing a problem solving processing routine described later. Can be configured with a computer. Functionally, the problem solving apparatus 100 includes an input unit 10, a calculation unit 20, and an output unit 50 as shown in FIG.

  The input unit 10 receives, as inputs, a tree structure composed of nodes each having a value and a capacity, with the item as a node, and a capacity limit C.

  The computing unit 20 includes a sorting unit 30, a storage unit 31, an optimum value calculation unit 32, and a backtrack unit 34.

The sorting unit 30 rearranges the nodes constituting the tree structure received by the input unit 10 in the depth-first order from the root of the tree structure. For example, when the sorting unit receives each node constituting the tree structure shown in FIG. 2, the nodes are sorted in a pre-order, and the sorted array A = (v ₉ , v ₁ , v ₂ , v ₅ , v ₃ , v ₄ , V ₆ , v ₇ , v ₈ ) are passed to the optimum value calculation unit 32. Also, the numerical value given to the upper left of each node in FIG. 2 indicates the index of each node.

  The storage unit 31 is a (N + 1) × (C + 1) two-dimensional array, a two-dimensional array S for storing the maximum sum of values of nodes included in the rooted subtree in each element, and a rooted As information for obtaining a subtree, a two-dimensional array B that stores the index and type of each node in each element is stored.

  The optimum value calculator 32 can add a n-th node to each capacity c (0 ≦ c ≦ C) for the n-th node according to the order of the nodes rearranged by the sort unit 30. In addition, among the rooted subtrees in which the sum of the capacities of the nodes is equal to the capacity c, the rooted subtree is repeatedly calculated by repeatedly calculating the rooted subtree having the maximum sum of the values of the nodes in the rooted subtree. The rooted subtree that maximizes the sum of the values of the nodes of the tree is gradually grown, and for the rooted subtree of each growth stage, the maximum sum of the values of the nodes is calculated and the array S of the storage unit 31 is calculated. To remember. Further, among the rooted subtrees in which the nth node can be added and the sum of the capacities of the nodes is equal to the capacity c, the sum of the values of the nodes of the rooted subtree is maximized. When calculating a rooted subtree, a rooted subtree that can add an nth node by calling the maximum sum of values of each node stored in the array S of the storage unit 31 for the rooted subtree of each growth stage. And a rooted subtree including the (n-1) th node in which the sum of the capacities of the nodes is equal to the capacity c, and a rooted subtree to which the nth node can be added, and the capacity of each node Among the rooted subtrees not including the (n−1) th node whose sum is equal to the capacity c, the rooted subtree having the maximum sum of the values of the nodes of the subtree is recursively calculated.

  Specifically, the optimum value calculation unit 32 first calculates the value of each node for each combination of the nth node and the capacity c stored in the storage unit 31 using the following equation (11). An array S for storing the maximum sum S [n] [c] is initialized. However, 1 ≦ n ≦ N + 1 and 0 ≦ c ≦ C. Note that the capacity limit C and the capacity c are both integers. The element S [n] [c] of the two-dimensional array S is a rooted subtree to which the nth node of the array A can be added, and the n−1th node whose capacity is equal to c The maximum value of the rooted subtree where the sum of the values of the nodes of the subtree is maximized is stored.

  Next, the optimum value calculation unit 32 uses, for each combination of the nth node and the capacity c, the maximum value S of the sums of the values of the respective nodes with respect to the combination using the recursive equation of the following expression (12). [N] [c] is calculated and stored in the array stored in the storage unit 31. In the expression (12), with respect to the maximum value of the rooted subtree stored in S [n] [c], (a) the rooted subtree including the (n−1) th node, or (b) the (n−1) th subtree. A rooted subtree that does not contain nodes is selected. (12) The first line of the expression is the sum of the values of the nodes of the rooted subtree including the (n−1) th node, and the second and third lines are rooted subtrees that do not include the (n−1) th node. Corresponds to the score of the sum of the values of each node.

  Here, A [n] represents the nth node, the function cap (A [n]) represents the capacity of the nth node, and p (A [n]) represents the value of the nth node. Represents.

  The function prev (n) is a function that returns an index of the array A in which the value of the function next_undesc () is n, and is defined by the following equation (13).

The function next_undesc (h) represents a function that returns the index of the first node that is not a descendant of the h-th node among the h + 1 and subsequent nodes. For example, the partial array A [h + 1,. . . , N] returns the index of the first node that is not a descendant of A [h]. Suppose that the partial array A [h + 1,. . . , N], there is no node that is not a descendant of A [h], then next_undesc (h) = N + 1. For example, in array A, if h = 2, then A [2] = v ₁ , so its descendants are v ₂ , v ₃ , v ₄ , v ₅ . Therefore, A [3,. . . , 9] to delete these offsprings yields (v ₆ , v ₇ , v ₈ ). Therefore, next_undesc (2) returns 7 is an index in the array A _{v 6.} Similarly, next_undesc (4) and next_undesc (6) are also 7, so in the case of prev (7), the h-th node is {2, 4, 6}.

  Here, each element for the two-dimensional array S for storing the maximum sum of the values of the nodes included in the rooted subtree and the two-dimensional array B for storing information for obtaining the rooted subtree is efficiently determined. The algorithm for doing this is shown in Algorithm 1 in FIG.

  In Algorithm 1, first, each node constituting the tree structure is sorted by pre-order in the first line of the algorithm, and stored in the array A. Then, in the 3rd to 35th lines, each element of the (N + 1) × (C + 1) two-dimensional array S and B is determined.

  Specifically, the two-dimensional arrays S and B are initialized (lines 3 to 8 in FIG. 3). Then, the value N + 1 is stacked on the stack siblings (9th line), and the element of S [1] [0] is set to 0 (10th line).

  Next, for n (2 ≦ n ≦ N + 1), the values of the elements of the two-dimensional arrays S and B are determined for 0 ≦ c ≦ C by iterative processing from the 11th row.

  When the capacity of c-cap (A [n-1]) is zero or more and the score of the value of S [n-1] [c-cap (A [n-1])] is zero or more, S If S [n] [c-cap (A [n-1])] + p (A [n-1]) is larger than [n] [c], then S [n] [c] 1] Substitute the value score of [c-cap (A [n-1])] + p (A [n-1]) (13th to 18th lines). Then, a tuple (n−1, DIAGONAL) representing an index and a type is stored in B [n] [c]. When the type is DIAGONAL, a pre-order index composed of nodes 1 to n−1 and having a capacity sum of c and a rooted subtree that maximizes the sum of the values of the nodes Order index n-1 indicates that the first node is used.

  Next, if the top value of the stack siblings is n-1, remove it (20th to 21st lines). Then, let k be the preorder index of the leftmost sibling among the siblings existing on the right side of the node A [n−1]. If there is no sibling on the right side of the node A [n−1], the index stacked at the top of the stack siblings is set to k. Otherwise, k is stacked on the stack siblings (23rd to 28th lines).

  Then, for 0 ≦ c ≦ C, each element of S [k] [c] and B [k] [c] is determined. If S [n−1] [c] is larger than S [k] [c], the value score of S [n−1] [c] is stored in S [k] [c], and B [k] [C] stores a tuple (n-1, UPRIGHT) indicating an index and a type (lines 29 to 34). If the type is UPRIGHT, for a rooted subtree composed of nodes with preorder indices from 1 to k−1 and having a capacity sum equal to c and maximizing the sum of the values of each node, This indicates that the pre-order index n-1st node is not used.

  When the node capacity c and the value p are given as shown in Table 1 for each node constituting the tree structure shown in FIG. 2, assuming that the knapsack capacity limit C = 10, the two-dimensional array S For each combination of the nth node and the capacity c, the maximum sum of the values of the nodes is stored as shown in FIG. Further, when information for obtaining a rooted subtree is stored for each combination of the nth node and the capacity c in the two-dimensional array B, the result is as shown in FIG.

  Based on the calculation process repeatedly calculated by the optimum value calculation unit 32, the backtrack unit 34 has a rooted portion in which the sum of the values of the nodes of the rooted subtree is maximized among the rooted subtrees having a capacity limit C or less. The tree is output to the output unit 50.

  Here, Algorithm 2 of FIG. 6 shows a backtracking algorithm that obtains a rooted subtree that maximizes the sum of the values of items below the capacity limit C using the two-dimensional arrays S and B generated by the optimum value calculation unit. .

  The score of the rooted subtree that maximizes the sum of the values of the nodes below the capacity limit C by calculation by the optimum value calculation unit 32 is stored in the (N + 1) th row of the two-dimensional array S stored in the storage unit 31. Yes. Therefore, first, a column in the (N + 1) th row of S that stores the score of the rooted subtree that maximizes the sum of values below the capacity limit C is determined, and the determined column is set to max_idx (third row). Then, backtracking is performed in order from the N + 1 row and the max_idx column of the two-dimensional array B (9th to 18th rows). If n is a row, m is a column, and the initial position starts from a row where n is N + 1 and m is a max_idx column, and the tuple type stored in B [n] [m] is DIAGONAL, Push index k into array tree. Then, k is substituted for n, and m-cap (A [k]) is substituted for m. If the tuple type is UPRIGHT, substitute k for n. In this way, the node used to determine the value from the B element corresponding to the S element that records the maximum score of the rooted subtree is traced. That is, only when the tuple type is DIAGONAL, the optimal rooted subtree can be obtained by pushing the index into the array.

In the two-dimensional array S of FIG. 4, the maximum sum of the values of the nodes included in the rooted subtree with the capacity limit C = 10 or less is 14. Therefore, backtracking is started from B [10] [10] corresponding to the two-dimensional array B in FIG. Since optimal rooted subtree root with subtrees pre order index of nodes of _{9,8,7,3,2,1, v 1, v 2,} v 6, v 7, v select 8, _{v 9,} the output To the unit 50.

<Operation of Problem Solving Device According to Embodiment of the Present Invention>

  Next, the operation of the problem solving apparatus 100 according to the embodiment of the present invention will be described. When the input unit 10 receives a tree structure composed of each node having value and capacity and the capacity limit C, the problem solving apparatus 100 executes a problem solving process routine shown in FIG.

  First, in step S100, the nodes received by the input unit 10 are sorted, sorted in the order of priority from the root of the tree structure, and rearranged.

  Next, in step S102, the number of each node rearranged in step S100 is set as a value of N.

  In step S104, the two-dimensional array S and the two-dimensional array B stored in the storage unit 31 are initialized.

  In step S106, N + 1 is accumulated as the initial value of the stack siblings.

  In step S108, 0 is stored in the element S [1] [0] of the two-dimensional array S stored in the storage unit 31.

  In step S110, 1 is substituted for n.

  In step S112, it is determined whether n is N or less. If N or less, the process proceeds to step S114, and if not N or less, the process proceeds to step S132.

  In step S114, n + 1 is substituted for n.

  In step S116, for each combination of the nth node and the capacity c, the maximum value S [n] [c] of the sum of the values of the respective nodes is calculated according to the first row of the above equation (12). And stored as each element of the two-dimensional array S stored in the storage unit 31.

  In step S118, it is determined whether or not the top value of the stack siblings is n−1. If n−1, the process proceeds to step S120, and if not n−1, the process proceeds to step S122.

  In step S120, the value stacked at the top of the stack siblings is removed.

  In step S122, the preorder index of the leftmost sibling among the siblings existing on the right side of the node A [n-1] is substituted for k.

  In step S124, it is determined whether k is NULL (whether there is no sibling on the right side of node A [n-1]). If NULL, the process proceeds to step S126, and if not NULL, the process proceeds to step S128. To do.

  In step S126, the index value stacked at the top of the stack siblings is substituted for k.

  In step S128, k is stacked on the stack siblings.

  In step S130, based on k obtained in step S122 or S126, S [k] [c] and B [k] are set for each capacity c according to the second and third lines of the above equation (12). Each element of [c] is determined, and the process returns to step S112 to repeat the process.

  In step S132, a rooted subtree having a maximum sum of the values of the nodes of the rooted subtree among the rooted subtrees that are less than or equal to the capacity limit C is calculated based on the calculation process that is repeatedly calculated by the process of each step. It outputs to the output part 50 and complete | finishes a process.

  Step S116 is realized by the maximum value calculation processing routine shown in FIG.

  According to the maximum value calculation processing routine described below, the maximum sum of the values of the respective nodes for each combination of the nth node and the capacity c is determined according to the recursive expression in the first row of the above expression (12). The value S [n] [c] is calculated and stored in the array stored in the storage unit 31.

  In step S200 of FIG. 8, the value of the capacity c is set to c = 0.

  Next, in step S202, it is determined whether the capacity c is equal to or less than the capacity limit C. If the capacity limit C is equal to or less than the capacity limit C, the process proceeds to step S204.

  In step S204, it is determined whether c-cap (A [n-1]) is 0 or more and S [n] [c-cap (A [n-1])] is 0 or more. If the condition is satisfied, the process proceeds to step S206. If the condition is not satisfied, the process proceeds to step S212.

  In step S206, it is determined whether S [n-1] [c-cap (A [n-1])] + p (A [n-1]) is larger than S [n] [c], and the condition is satisfied. If so, the process proceeds to step S208. If the condition is not satisfied, the process proceeds to step S212.

  In step S208, the value score of S [n-1] [c-cap (A [n-1])] + p (A [n-1]) is substituted into S [n] [c].

  In step S210, a tuple (n-1, DIAGONAL) indicating an index and a type is stored in B [n] [c].

  In step S212, the value of the capacity c is set to c = c + 1, the process returns to step S202, and the process is repeated until the capacity c is not less than or equal to the capacity limit C.

Step S130 is realized by the sibling element determination processing routine shown in FIG.
By the sibling element determination processing routine described below, S [k] [c] is calculated for each of the capacitances c according to the second and third lines of the above equation (12) and stored in the storage unit 31. It stores in the array.

  In step S300 of FIG. 9, the value of the capacity c is set to c = 0.

  Next, in step S302, it is determined whether the capacity c is equal to or less than the capacity limit C. If the capacity limit C is equal to or less than the capacity limit C, the process proceeds to step S304.

  In step S304, it is determined whether S [n-1] [c] is larger than S [k] [c]. If the condition is satisfied, the process proceeds to step S306. If the condition is not satisfied, the process proceeds to step S310. To do.

  In step S306, the value score of S [n−1] [c] stored as an element in the two-dimensional array S stored in the storage unit 31 in the maximum value calculation processing routine is added to S [k] [c]. substitute.

  In step S308, a tuple (n-1, UPLIGHT) indicating an index and a type is stored in B [n] [c].

  In step S310, the value of the capacity c is set to c = c + 1, the process returns to step S302, and the process is repeated until the capacity c is not less than or equal to the capacity limit C.

  Step S132 is realized by the backtrack processing routine shown in FIG.

  Step S400 in FIG. 10 creates an array tree that stores the index of each node of the rooted subtree that maximizes the sum of the values of each node of the rooted subtree, and sets the initial value of row n to N + 1.

  Next, in step S402, a column k in the (N + 1) th row of S that stores the score of the rooted subtree that maximizes the sum of values below the capacity limit C is determined, and the determined k is set to max_idx.

  In step S404, the value score stored in S [N + 1] [max_idx] is stored in max_val.

  In step S406, it is determined whether the value of max_val in which the value score is stored in step S404 is less than 0. If it is less than 0, the process ends. If not less than 0, the process proceeds to step S408.

  In step S408, the value of max_idx is assigned to the column m.

  In step S410, it is determined whether n = 1 and m = 0. If the condition is satisfied, the process proceeds to step S412. If the condition is not satisfied, it is pushed to the array tree by an iterative process described later. Each node of the index is output to the output unit 50 as each node constituting a rooted subtree having the maximum sum of the values of the nodes, and the process is terminated.

  In step S412, the index and type stored in B [n] [m] are assigned to (k, type), respectively.

  In step S414, it is determined whether the type substituted in step S412 is DIAGONAL. If it is DIAGONAL, the process proceeds to step S416, and if not DIAGONAL, the process proceeds to step S422.

  In step S416, the index k substituted in step S412 is pushed to the array tree.

  In step S418, the value of index k is substituted for n.

  In step S420, m-cap (A [k]) is substituted for m, and the process returns to step S410 and is repeated.

  In step S422, k is substituted for n, and the process returns to step S410 to repeat the process.

  As described above, according to the problem solving apparatus according to the embodiment of the present invention, a rooted subtree in which the nth node can be added to each capacity c (0 ≦ c ≦ C) for the nth node. In addition, among the rooted subtrees in which the sum of the capacities of the nodes is equal to the capacity c, the rooted subtree is repeatedly calculated by repeatedly calculating the rooted subtree having the maximum sum of the values of the nodes in the rooted subtree. The rooted subtree that maximizes the sum of the values of the nodes of the tree is gradually grown, and for the rooted subtree of each growth stage, the maximum sum of the values of the nodes is calculated and the array S of the storage unit 31 is calculated. A rooted subtree that can be added to the nth node by calling the maximum sum of the values of the nodes stored in the storage unit 31 for the rooted subtree of each growth stage, and each node The sum of the capacities is the capacity c A rooted subtree including the (n−1) th node to be equal and a rooted subtree to which the nth node can be added, and the sum of the capacities of the nodes is equal to the capacity c. By recursively calculating a rooted subtree that has the maximum value of the nodes of the subtree among the rooted subtrees that are not included, the tree-constrained knapsack problem can be solved at high speed.

  Further, as apparent from Algorithm 1 in FIG. 3, the present invention only prepares N + 1 arrays of capacitors C + 1 and determines the value, so the amount of calculation is O (NC).

  Note that the present invention is not limited to the above-described embodiment, and various modifications and applications are possible without departing from the gist of the present invention.

DESCRIPTION OF SYMBOLS 10 Input part 20 Operation part 30 Sort part 31 Storage part 32 Optimal value calculation part 34 Back track part 50 Output part 100 Problem solving apparatus

Claims (5)

A problem solving apparatus that solves a tree-constrained knapsack problem that selects a rooted subtree that maximizes a value below a capacity limit C from a tree structure composed of nodes having value and capacity,
A sorting unit that rearranges each node constituting the tree structure in a depth-first order from the root of the tree structure;
In accordance with the order of the nodes rearranged by the sorting unit, for the nth node, a rooted subtree that can add the nth node to each capacity c (0 ≦ c ≦ C), and Of the rooted subtrees in which the sum of the node capacities is equal to the capacity c, by repeatedly calculating the rooted subtree having the maximum sum of the values of the nodes in the rooted subtree, An optimal value calculation unit that gradually grows a rooted subtree that maximizes the sum of values, calculates a maximum sum of values of each node for the rooted subtree in each growth stage, and stores the value in a storage unit; ,
Based on a calculation process repeatedly calculated by the optimum value calculation unit, a rooted subtree having a maximum sum of values of the nodes of the rooted subtree among the rooted subtrees having the capacity limit C or less is output. Including a backtrack section,
The optimum value calculation unit is a rooted subtree to which the nth node can be added, and the value of each node of the rooted subtree among the rooted subtrees in which the sum of the capacities of the nodes is equal to the capacity c When the rooted subtree with the largest sum is calculated, the maximum value of the sum of the values of the nodes stored in the storage unit for the rooted subtree in each growth stage can be called to add the nth node A rooted subtree that includes an (n-1) th node whose sum of capacities of each node is equal to the capacity c, and a rooted subtree to which the nth node can be added, and Among the rooted subtrees not including the (n-1) th node whose sum of capacities of the nodes is equal to the capacity c, the rooted subtree having the maximum sum of the values of the nodes of the subtree is recursively. Calculate problem solving equipment Place. The optimum value calculation unit uses the following equation (1) to calculate the maximum value S of the sum of the values of the nodes for each combination of the nth node and the capacity c stored in the storage unit. Initialize an array to store [n] [c];
For each combination of the nth node and the capacity c, the maximum value S [n] [c] of the sum of the values of each node for the combination is calculated using the following equation (2): The problem solving apparatus according to claim 1, wherein the problem solving apparatus stores the data in the array stored in the storage unit.
However, A [n] represents the nth node, the function cap (A [n]) represents the capacity of the nth node, and p (A [n]) represents the value of the nth node. The function next_undesc (h) represents a function that returns the index of the first node that is not a descendant of the h-th node among the h + 1 and subsequent nodes. A problem solving method in a problem solving apparatus for solving a tree-constrained knapsack problem in which a rooted subtree that maximizes a value with a capacity limit C or less is selected from a tree structure composed of nodes each having value and capacity. ,
A step of sorting the nodes constituting the tree structure in a depth-first order from the root of the tree structure;
The optimal value calculation unit is a rooted subtree that can add the nth node for each capacity c (0 ≦ c ≦ C) for the nth node according to the order of the nodes rearranged by the sorting unit. In addition, among the rooted subtrees in which the sum of the capacities of the nodes is equal to the capacity c, the rooted subtree having the maximum sum of the values of the nodes in the rooted subtree is repeatedly calculated, whereby the rooted The rooted subtree that maximizes the sum of the values of each node in the subtree is gradually grown, and the maximum sum of the values of each node is calculated and stored in the storage unit for the rooted subtree in each growth stage. And steps to
Based on the calculation process in which the backtrack unit is repeatedly calculated by the optimum value calculation unit, among the rooted subtrees that are less than or equal to the capacity limit C, the rooting that maximizes the sum of the values of the nodes of the rooted subtree Outputting a subtree,
The step of calculating by the optimum value calculating unit is a rooted subtree to which an nth node can be added, and among the rooted subtrees in which the sum of the capacities of each node is equal to the capacity c, the rooted subtree When calculating a rooted subtree that maximizes the sum of the values of each node, the maximum value sum of the values of each node stored in the storage unit for the rooted subtree of each growth stage is called, A rooted subtree to which nodes can be added, and a rooted subtree including the (n-1) th node in which the sum of the capacities of the nodes is equal to the capacity c, and a rooted subtree to which the nth node can be added. And a rooted subtree in which the sum of the values of the nodes of the subtree is the largest among the rooted subtrees not including the (n−1) th node whose sum of capacities of the nodes is equal to the capacity c. Re Problem-solving method to calculate. The step of calculating by the optimum value calculating unit uses the following equation (4) to sum the value of each node for each combination of the nth node and the capacity c stored in the storage unit: Initialize an array for storing the maximum value S [n] [c] of
For each of the combinations of the n-th node and the capacitance c, the maximum value S [n] [c] of the sum of the values of the nodes for the combination is calculated using the following equation (5): The problem solving method according to claim 3, wherein the problem is stored in the array stored in the storage unit.
However, A [n] represents the nth node, the function cap (A [n]) represents the capacity of the nth node, and p (A [n]) represents the value of the nth node. The function next_undesc (h) represents a function that returns the index of the first node that is not a descendant of the h-th node among the h + 1 and subsequent nodes.   The program for functioning a computer as each part which comprises the problem-solving apparatus of Claim 1 or 2.