嵌套框算法 - 基于嵌套娃娃但根本不同？
Nested Boxes Algorithm - based on Nested Dolls but fundamentally different?
我试图解决与 SPOJ 嵌套玩偶问题相关的问题，其中使用具有二维底部的盒子而不是在单个比例参数上不同的玩偶。我有一个算法，但我对问题背后的实际理论以及是否存在更好的方法感到非常困惑。任何人都可以帮助我更好地理解问题并找到更好的算法吗？
作为复习，嵌套娃娃问题如下：
给定 N 个不同大小的俄罗斯套娃，找出将这些娃娃最佳嵌套后剩余的最小套娃数量。对于每个嵌套玩偶，如果最外面的玩偶大小为 S，则它要么不包含任何玩偶，要么包含一个大小严格小于 S[=45 的嵌套玩偶=].
我不知道这个问题的全部细节，但通过阅读它，我相信嵌套玩偶问题可以通过增加大小对玩偶进行排序并从中重复提取最长递增子序列 (LIS) 来解决大小序列，通过选择使用最大玩偶的子序列来打破平局。嵌套娃娃的数量将是提取的子序列的数量。我认为这种贪心算法有效是因为：
a) 减少其中一个子序列的长度会引入新的玩偶，这些玩偶无法减少在未来步骤中找到的嵌套玩偶的数量 ("fewer is better")
b) 替换子序列中的一个玩偶必然会将剩余玩偶集中的一个较小的玩偶替换为一个较大的玩偶，这不能减少在未来步骤中找到的嵌套玩偶的数量("smaller is better")
这意味着使用好的 LIS 算法可以在 O(N log N) 内解决该问题。
但是箱子的问题是不同的：
给定 N 个具有不同底部尺寸的开放盒子，找到将盒子最佳地相互嵌套后剩余的最少盒子堆叠数。对于每个盒子堆，如果最外面的盒子的尺寸为 WxH 那么它要么不包含任何盒子，要么包含一个盒子堆，其宽度和高度分别严格小于 W 和 H。
这意味着盒子没有完全排序 - 如果盒子 A 不适合盒子 B，并不意味着盒子 B 的大小与 A 相同，或者它适合盒子 A，这与俄罗斯套娃不同娃娃.
我不知道我是否正确，但我认为通过重复提取 LIS（或者更确切地说，最长的盒子序列相互拟合）可以找到最优解已经不再正确了，主要是因为没有什么好办法断绝关系。如果我们在 1x17 盒子和 5x4 盒子之间进行比较，那么面积较大的盒子最终可能对未来的步骤更有用。尝试所有绑定的 LIS 听起来像是指数运行时间。我是对的，还是真的有一种贪婪的方式来做到这一点？
我只找到了另一个 post 关于这个 (Stacking boxes into fewest number of stacks efficiently?)，它建议使用图论方法来解决问题。我对图论的经验很少，所以我不知道这种方法是如何工作的。我基本上盲目地接受了他们的话来制作一个二分图的盒子，断言盒子堆叠的数量=（盒子的数量 - 最大匹配的大小）。然后我基于伪代码在Java中实现了Fork Fulkerson算法，但没有完全理解它实际上是如何解决问题的。我已尽力用我的思维过程对代码进行注释，但令我恼火的是这种方法与 Nested Dolls 解决方案如此不同，而且当我被要求在 1 小时内完成此操作时需要 150 多行代码。真的没有更简单的方法来解决这个问题吗？
代码：
import java.util.*;
public class NestedBoxes {
private static final int SOURCE_INDEX = -1;
private static final int SINK_INDEX = -2;
private NestedBoxes() {
// Unused
}
public static void main(String args[] ) throws Exception {
// Get box dimensions from user input
Scanner sc = new Scanner(System.in);
int numBoxes = sc.nextInt();
List<Rectangle> boxes = new ArrayList<>();
for (int i = 0; i < numBoxes; i++) {
Rectangle box = new Rectangle(sc.nextInt(), sc.nextInt());
boxes.add(box);
}
// Sort boxes by bottom area as a useful heuristic
Collections.sort(boxes, (b1, b2) -> Integer.compare(b1.width * b1.height, b2.width * b2.height));
// Make a bipartite graph based on which boxes fit into each other, and
// add a source linking to all boxes and a sink linked by all boxes.
// Forward edges go from the left (lower index) nodes to the right (higher index) nodes.
// Each forward edge has a corresponding backward edge in the bipartite section.
// Only one of the two edges are active at any point in time.
Map<Integer, Map<Integer, BooleanVal>> graphEdges = new HashMap<>();
Map<Integer, BooleanVal> sourceMap = new HashMap<>();
graphEdges.put(SOURCE_INDEX, sourceMap);
graphEdges.put(SINK_INDEX, new HashMap<>()); // Empty adjacency list for the sink
for (int i = 0; i < numBoxes; i++) {
// TreeMaps make the later DFS step prefer reaching the sink over other nodes, and prefer
// putting boxes into the smallest fitting box first, speeding up the search a bit since
// log(N) is not that bad compared to a large constant factor.
graphEdges.put(i, new TreeMap<>());
// Each node representing a box is duplicated in a bipartite graph, where node[i]
// matches with node[numBoxes + i] and represent the same box
graphEdges.put(numBoxes + i, new TreeMap<>());
}
for (int i = 0; i < boxes.size(); i++) {
// Boolean pointers are used so that backward edges ("flow") and
// forward edges ("capacity") are updated in tandem, maintaining that
// only one is active at any time.
sourceMap.put(i, new BooleanPtr(true)); // Source -> Node
graphEdges.get(numBoxes + i).put(SINK_INDEX, new BooleanPtr(true)); // Node -> Sink
for (int j = i + 1; j < boxes.size(); j++) {
if (fitsIn(boxes.get(i), boxes.get(j))) {
BooleanVal opening = new BooleanPtr(true);
graphEdges.get(i).put(numBoxes + j, opening); // Small box -> Big box
graphEdges.get(numBoxes + j).put(i, new Negation(opening)); // Small box <- Big box
}
}
}
Deque<Integer> path; // Paths are represented as stacks where the top is the first node in the path
Set<Integer> visited = new HashSet<>(); // Giving the GC a break
// Each DFS pass takes out the capacity of one edge from the source
// and adds a single edge to the bipartite matching generated.
// The algorithm automatically backtracks if a suboptimal maximal matching is found because
// the path would take away edges and add new ones in if necessary.
// This happens when the path zigzags using N backward edges and (N + 1) forward edges -
// removing a backward edge corresponds to removing a connection from the matching, and using extra
// forward edges will add new connections to the matching.
// So if no more DFS passes are possible, then no amount of readjustment will increase the size
// of the matching, so the number of passes equals the size of the maximum matching of the bipartite graph.
int numPasses = 0;
while ((path = depthFirstSearch(graphEdges, SOURCE_INDEX, SINK_INDEX, visited)) != null) {
visited.clear();
Integer current = SOURCE_INDEX;
path.pop();
for (Integer node : path) {
// Take out the edges visited.
// Taking away any backward edges automatically adds back the corresponding forward edge,
// and similarly removing a forward edge adds back the backward edge.
graphEdges.get(current).get(node).setBoolValue(false);
current = node;
}
numPasses++;
}
// Print out the stacks made from the boxes. Here, deleted forward edges / available backward edges
// represent opportunities to nest boxes that have actually been used in the solution.
System.out.println("Box stacks:");
visited.clear();
for (int i = 0; i < numBoxes; i++) {
Integer current = i;
if (visited.contains(current)) {
continue;
}
visited.add(current);
boolean halt = false;
while (!halt) {
halt = true;
System.out.print(boxes.get(current));
for (Map.Entry<Integer, BooleanVal> entry : graphEdges.get(current).entrySet()) {
int neighbor = entry.getKey() - numBoxes;
if (!visited.contains(neighbor) && !entry.getValue().getBoolValue()) {
System.out.print("->");
visited.add(neighbor);
current = neighbor;
halt = false;
break;
}
}
}
System.out.println();
}
System.out.println();
// Let a box-stack be a set of any positive number boxes nested into one another, including 1.
// Beginning with each box-stack being a single box, we can nest them to reduce the box-stack count.
// Each DFS pass, or edge in the maximal matching, represents a single nesting opportunity that has
// been used. Each used opportunity removes one from the number of box-stacks. so the total number
// of box-stacks will be the number of boxes minus the number of passes.
System.out.println("Number of box-stacks: " + (numBoxes - numPasses));
}
private static Deque<Integer> depthFirstSearch(Map<Integer, Map<Integer, BooleanVal>> graphEdges,
int source, int sink, Set<Integer> visited) {
if (source == sink) {
// Base case where the path visits only one node
Deque<Integer> result = new ArrayDeque<>();
result.push(sink);
return result;
}
// Get all the neighbors of the source node
Map<Integer, BooleanVal> neighbors = graphEdges.get(source);
for (Map.Entry<Integer, BooleanVal> entry : neighbors.entrySet()) {
Integer neighbor = entry.getKey();
if (!visited.contains(neighbor) && entry.getValue().getBoolValue()) {
// The neighbor hasn't been visited before, and the edge is active so the
// DFS attempts to include this edge into the path.
visited.add(neighbor);
// Trying to find a path from the neighbor to the sink
Deque<Integer> path = depthFirstSearch(graphEdges, neighbor, sink, visited);
if (path != null) {
// Adds the source onto the path found
path.push(source);
return path;
} else {
// Pretend we never visited the neighbor and move on
visited.remove(neighbor);
}
}
}
// No paths were found
return null;
}
// Interface for a mutable boolean value
private interface BooleanVal {
boolean getBoolValue();
void setBoolValue(boolean val);
}
// A boolean pointer
private static class BooleanPtr implements BooleanVal {
private boolean value;
public BooleanPtr(boolean value) {
this.value = value;
}
@Override
public boolean getBoolValue() {
return value;
}
@Override
public void setBoolValue(boolean value) {
this.value = value;
}
@Override
public String toString() {
return "" + value;
}
}
// The negation of a boolean value
private static class Negation implements BooleanVal {
private BooleanVal ptr;
public Negation(BooleanVal ptr) {
this.ptr = ptr;
}
@Override
public boolean getBoolValue() {
return !ptr.getBoolValue();
}
@Override
public void setBoolValue(boolean val) {
ptr.setBoolValue(!val);
}
@Override
public String toString() {
return "" + getBoolValue();
}
}
// Method to find if a rectangle strictly fits inside another
private static boolean fitsIn(Rectangle rec1, Rectangle rec2) {
return rec1.height < rec2.height && rec1.width < rec2.width;
}
// A helper class representing a rectangle, or the bottom of a box
private static class Rectangle {
public int width, height;
public Rectangle(int width, int height) {
this.width = width;
this.height = height;
}
@Override
public String toString() {
return String.format("(%d, %d)", width, height);
}
}
}
是的，有一个更简单（也更有效）的解决方案。
让我们按宽度对框进行排序（如果两个框的宽度相同，则按高度的倒序排列）。很明显，我们只能将一个盒子嵌套到它后面的盒子中。因此，我们想把它分成多个递增的子序列（现在只考虑高度）。有一个定理说，一个序列可以拆分成的递增子序列的最小个数等于最长非递增子序列（即非严格递减子序列）的长度。
综上所述，解决方案如下：
按宽度对框进行排序。如果宽度相同，则按高度倒序比较
丢掉宽度，只计算最长的非递增高度子序列的长度（按照我们排序后得到的顺序）。这是问题的答案。就是这样。
很明显，如果实施得当，此解决方案可以在 O(N log N) 时间内发挥作用。
我试图解决与 SPOJ 嵌套玩偶问题相关的问题，其中使用具有二维底部的盒子而不是在单个比例参数上不同的玩偶。我有一个算法，但我对问题背后的实际理论以及是否存在更好的方法感到非常困惑。任何人都可以帮助我更好地理解问题并找到更好的算法吗？
作为复习，嵌套娃娃问题如下：
给定 N 个不同大小的俄罗斯套娃，找出将这些娃娃最佳嵌套后剩余的最小套娃数量。对于每个嵌套玩偶，如果最外面的玩偶大小为 S，则它要么不包含任何玩偶，要么包含一个大小严格小于 S[=45 的嵌套玩偶=].
我不知道这个问题的全部细节，但通过阅读它，我相信嵌套玩偶问题可以通过增加大小对玩偶进行排序并从中重复提取最长递增子序列 (LIS) 来解决大小序列，通过选择使用最大玩偶的子序列来打破平局。嵌套娃娃的数量将是提取的子序列的数量。我认为这种贪心算法有效是因为：
a) 减少其中一个子序列的长度会引入新的玩偶，这些玩偶无法减少在未来步骤中找到的嵌套玩偶的数量 ("fewer is better")
b) 替换子序列中的一个玩偶必然会将剩余玩偶集中的一个较小的玩偶替换为一个较大的玩偶，这不能减少在未来步骤中找到的嵌套玩偶的数量("smaller is better")
这意味着使用好的 LIS 算法可以在 O(N log N) 内解决该问题。
但是箱子的问题是不同的： 给定 N 个具有不同底部尺寸的开放盒子，找到将盒子最佳地相互嵌套后剩余的最少盒子堆叠数。对于每个盒子堆，如果最外面的盒子的尺寸为 WxH 那么它要么不包含任何盒子，要么包含一个盒子堆，其宽度和高度分别严格小于 W 和 H。
这意味着盒子没有完全排序 - 如果盒子 A 不适合盒子 B，并不意味着盒子 B 的大小与 A 相同，或者它适合盒子 A，这与俄罗斯套娃不同娃娃.
我不知道我是否正确，但我认为通过重复提取 LIS（或者更确切地说，最长的盒子序列相互拟合）可以找到最优解已经不再正确了，主要是因为没有什么好办法断绝关系。如果我们在 1x17 盒子和 5x4 盒子之间进行比较，那么面积较大的盒子最终可能对未来的步骤更有用。尝试所有绑定的 LIS 听起来像是指数运行时间。我是对的，还是真的有一种贪婪的方式来做到这一点？
我只找到了另一个 post 关于这个 (Stacking boxes into fewest number of stacks efficiently?)，它建议使用图论方法来解决问题。我对图论的经验很少，所以我不知道这种方法是如何工作的。我基本上盲目地接受了他们的话来制作一个二分图的盒子，断言盒子堆叠的数量=（盒子的数量 - 最大匹配的大小）。然后我基于伪代码在Java中实现了Fork Fulkerson算法，但没有完全理解它实际上是如何解决问题的。我已尽力用我的思维过程对代码进行注释，但令我恼火的是这种方法与 Nested Dolls 解决方案如此不同，而且当我被要求在 1 小时内完成此操作时需要 150 多行代码。真的没有更简单的方法来解决这个问题吗？
代码：
import java.util.*;
public class NestedBoxes {
private static final int SOURCE_INDEX = -1;
private static final int SINK_INDEX = -2;
private NestedBoxes() {
// Unused
}
public static void main(String args[] ) throws Exception {
// Get box dimensions from user input
Scanner sc = new Scanner(System.in);
int numBoxes = sc.nextInt();
List<Rectangle> boxes = new ArrayList<>();
for (int i = 0; i < numBoxes; i++) {
Rectangle box = new Rectangle(sc.nextInt(), sc.nextInt());
boxes.add(box);
}
// Sort boxes by bottom area as a useful heuristic
Collections.sort(boxes, (b1, b2) -> Integer.compare(b1.width * b1.height, b2.width * b2.height));
// Make a bipartite graph based on which boxes fit into each other, and
// add a source linking to all boxes and a sink linked by all boxes.
// Forward edges go from the left (lower index) nodes to the right (higher index) nodes.
// Each forward edge has a corresponding backward edge in the bipartite section.
// Only one of the two edges are active at any point in time.
Map<Integer, Map<Integer, BooleanVal>> graphEdges = new HashMap<>();
Map<Integer, BooleanVal> sourceMap = new HashMap<>();
graphEdges.put(SOURCE_INDEX, sourceMap);
graphEdges.put(SINK_INDEX, new HashMap<>()); // Empty adjacency list for the sink
for (int i = 0; i < numBoxes; i++) {
// TreeMaps make the later DFS step prefer reaching the sink over other nodes, and prefer
// putting boxes into the smallest fitting box first, speeding up the search a bit since
// log(N) is not that bad compared to a large constant factor.
graphEdges.put(i, new TreeMap<>());
// Each node representing a box is duplicated in a bipartite graph, where node[i]
// matches with node[numBoxes + i] and represent the same box
graphEdges.put(numBoxes + i, new TreeMap<>());
}
for (int i = 0; i < boxes.size(); i++) {
// Boolean pointers are used so that backward edges ("flow") and
// forward edges ("capacity") are updated in tandem, maintaining that
// only one is active at any time.
sourceMap.put(i, new BooleanPtr(true)); // Source -> Node
graphEdges.get(numBoxes + i).put(SINK_INDEX, new BooleanPtr(true)); // Node -> Sink
for (int j = i + 1; j < boxes.size(); j++) {
if (fitsIn(boxes.get(i), boxes.get(j))) {
BooleanVal opening = new BooleanPtr(true);
graphEdges.get(i).put(numBoxes + j, opening); // Small box -> Big box
graphEdges.get(numBoxes + j).put(i, new Negation(opening)); // Small box <- Big box
}
}
}
Deque<Integer> path; // Paths are represented as stacks where the top is the first node in the path
Set<Integer> visited = new HashSet<>(); // Giving the GC a break
// Each DFS pass takes out the capacity of one edge from the source
// and adds a single edge to the bipartite matching generated.
// The algorithm automatically backtracks if a suboptimal maximal matching is found because
// the path would take away edges and add new ones in if necessary.
// This happens when the path zigzags using N backward edges and (N + 1) forward edges -
// removing a backward edge corresponds to removing a connection from the matching, and using extra
// forward edges will add new connections to the matching.
// So if no more DFS passes are possible, then no amount of readjustment will increase the size
// of the matching, so the number of passes equals the size of the maximum matching of the bipartite graph.
int numPasses = 0;
while ((path = depthFirstSearch(graphEdges, SOURCE_INDEX, SINK_INDEX, visited)) != null) {
visited.clear();
Integer current = SOURCE_INDEX;
path.pop();
for (Integer node : path) {
// Take out the edges visited.
// Taking away any backward edges automatically adds back the corresponding forward edge,
// and similarly removing a forward edge adds back the backward edge.
graphEdges.get(current).get(node).setBoolValue(false);
current = node;
}
numPasses++;
}
// Print out the stacks made from the boxes. Here, deleted forward edges / available backward edges
// represent opportunities to nest boxes that have actually been used in the solution.
System.out.println("Box stacks:");
visited.clear();
for (int i = 0; i < numBoxes; i++) {
Integer current = i;
if (visited.contains(current)) {
continue;
}
visited.add(current);
boolean halt = false;
while (!halt) {
halt = true;
System.out.print(boxes.get(current));
for (Map.Entry<Integer, BooleanVal> entry : graphEdges.get(current).entrySet()) {
int neighbor = entry.getKey() - numBoxes;
if (!visited.contains(neighbor) && !entry.getValue().getBoolValue()) {
System.out.print("->");
visited.add(neighbor);
current = neighbor;
halt = false;
break;
}
}
}
System.out.println();
}
System.out.println();
// Let a box-stack be a set of any positive number boxes nested into one another, including 1.
// Beginning with each box-stack being a single box, we can nest them to reduce the box-stack count.
// Each DFS pass, or edge in the maximal matching, represents a single nesting opportunity that has
// been used. Each used opportunity removes one from the number of box-stacks. so the total number
// of box-stacks will be the number of boxes minus the number of passes.
System.out.println("Number of box-stacks: " + (numBoxes - numPasses));
}
private static Deque<Integer> depthFirstSearch(Map<Integer, Map<Integer, BooleanVal>> graphEdges,
int source, int sink, Set<Integer> visited) {
if (source == sink) {
// Base case where the path visits only one node
Deque<Integer> result = new ArrayDeque<>();
result.push(sink);
return result;
}
// Get all the neighbors of the source node
Map<Integer, BooleanVal> neighbors = graphEdges.get(source);
for (Map.Entry<Integer, BooleanVal> entry : neighbors.entrySet()) {
Integer neighbor = entry.getKey();
if (!visited.contains(neighbor) && entry.getValue().getBoolValue()) {
// The neighbor hasn't been visited before, and the edge is active so the
// DFS attempts to include this edge into the path.
visited.add(neighbor);
// Trying to find a path from the neighbor to the sink
Deque<Integer> path = depthFirstSearch(graphEdges, neighbor, sink, visited);
if (path != null) {
// Adds the source onto the path found
path.push(source);
return path;
} else {
// Pretend we never visited the neighbor and move on
visited.remove(neighbor);
}
}
}
// No paths were found
return null;
}
// Interface for a mutable boolean value
private interface BooleanVal {
boolean getBoolValue();
void setBoolValue(boolean val);
}
// A boolean pointer
private static class BooleanPtr implements BooleanVal {
private boolean value;
public BooleanPtr(boolean value) {
this.value = value;
}
@Override
public boolean getBoolValue() {
return value;
}
@Override
public void setBoolValue(boolean value) {
this.value = value;
}
@Override
public String toString() {
return "" + value;
}
}
// The negation of a boolean value
private static class Negation implements BooleanVal {
private BooleanVal ptr;
public Negation(BooleanVal ptr) {
this.ptr = ptr;
}
@Override
public boolean getBoolValue() {
return !ptr.getBoolValue();
}
@Override
public void setBoolValue(boolean val) {
ptr.setBoolValue(!val);
}
@Override
public String toString() {
return "" + getBoolValue();
}
}
// Method to find if a rectangle strictly fits inside another
private static boolean fitsIn(Rectangle rec1, Rectangle rec2) {
return rec1.height < rec2.height && rec1.width < rec2.width;
}
// A helper class representing a rectangle, or the bottom of a box
private static class Rectangle {
public int width, height;
public Rectangle(int width, int height) {
this.width = width;
this.height = height;
}
@Override
public String toString() {
return String.format("(%d, %d)", width, height);
}
}
}
是的，有一个更简单（也更有效）的解决方案。
让我们按宽度对框进行排序（如果两个框的宽度相同，则按高度的倒序排列）。很明显，我们只能将一个盒子嵌套到它后面的盒子中。因此，我们想把它分成多个递增的子序列（现在只考虑高度）。有一个定理说，一个序列可以拆分成的递增子序列的最小个数等于最长非递增子序列（即非严格递减子序列）的长度。
综上所述，解决方案如下：
按宽度对框进行排序。如果宽度相同，则按高度倒序比较
丢掉宽度，只计算最长的非递增高度子序列的长度（按照我们排序后得到的顺序）。这是问题的答案。就是这样。
很明显，如果实施得当，此解决方案可以在 O(N log N) 时间内发挥作用。