N条平行线上的最小交叉

Question

假设我们有n个不相交的水平双杠。然后，我们需要用垂直线连接每对条形图，因此共有sum(n,...,1)线数。如果两个条之间的这些连接中的任何一条与其他条交叉p次，那么我们说成本为p。问题是找到n条的最低总成本。

n=1, p=0:     n=2, p=0:     n=3, p=0  n=4, p=0: 

                              ---        -----
                              | |        | | |
---          ---            --- |      --- | |
               |              | |      | | | |
               ---            ---      | --- |
                                       |   | |
                                       ------- 

n=6, p=3:
-------------
| |     | | | 
| ----- | | |
| | | | | | | 
| | | --- | |
| | | | | | | 
--*-*-- | | |
  | |   | | | 
  | ----*-- |
  | |   |   | 
  -----------

n=7, p=6:
---------------
| | |     | | | 
| --*---- | | |
| | | | | | | | 
| | | --*-- | |
| | | | | | | | 
| | --- | | | |
| | | | | | | | 
| | | --*-*-- |
| | | | | |   | 
--*-*---- |   |
  | |     |   | 
  -------------

n=8, p=11
-------------------
| | | |       | | | 
| --1-1------ | | |
| | | |     | | | | 
| | --2---- | | | |
| | | | | | | | | | 
| | | | | --1-- | |
| | | | | | | | | | 
| | | --1-- | | | |
| | | | |   | | | | 
| | | | ----1-1-- |
| | | | |   | |   | 
--1-1-1------ |   |
  | | |       |   | 
  -----------------

关于如何找到其背后的模式或逻辑的任何提示都将是很棒的。

Answer 1

这是使用蛮力解决问题的草案解决方案，假设可以在仅具有 n+1 列的网格中找到 n 个条的最佳解决方案（这个假设至少对于 n>=8 来说似乎是错误的。通过更改参数，搜索可以可以扩展，最坏的情况是 sum(n-1, ... 1)，但这会进一步减慢搜索速度，主要是通过添加冗余解决方案）。

该算法具有指数复杂度，并且只会在有用的时间内给出非常低的数字的结果。正如我在评论中所说，可以通过减少搜索空间来稍微改进这种方法，只允许具有沙钟形状的条形组合（外部长条形，内部短条形，最外面的条形最长，覆盖相同的空间，以及所有其他条形）条可以放置在最外面的列内）。然而到目前为止，我没有发现其他有用的属性可以使用。请注意，可能存在某些仅适用于某些最佳解决方案的属性，例如中心条的长度为 2。

更好的方法可能是完全使用 sum(n-1, ... 1) 列，每个连接都有自己的列，变体的数量实际上可能会更少。

我不知道是否存在有用的动态规划解决方案。

public class BarConnection {

    static class Bar {
        int start, end;
        private final int maxlength, minlength;

        Bar(int maxlength, int minlength) {
            this.maxlength = maxlength;
            this.minlength = minlength;
            reset();
        }

        public boolean next() {
            start++;
            if (start > 0) {
                return reset((end - start) + 2);
            }
            end++;
            return true;
        }

        public void reset() {
            reset(minlength);
        }

        public boolean reset(int length) {
            if (length > maxlength) {
                return false;
            }
            start = -length;
            end = 0;
            return true;
        }
    }

    static class Solution {
        private Bar[] bars;
        private int globalmin, globalmax, cost;

        Solution(int n) {
            bars = new Bar[n];
            for (int i = 0; i < n; i++) {
                bars[i] = new Bar(/* maxlength */ n, /* minlength */ 1);
            }
        }

        private boolean connect(final int maxcost) {
            cost = Integer.MAX_VALUE;
            int sumcost = 0;
            for (int i = 0; i < (bars.length - 1); i++) {
                for (int j = i + 1; j < bars.length; j++) {
                    final int pairCost = minCostBetween(i, j);
                    if (pairCost == 0) {
                        continue;
                    }
                    sumcost += pairCost;
                    if (sumcost > maxcost) {
                        return false;
                    }

                }
            }
            cost = sumcost;
            return true;
        }

        boolean nextSolution(final int maxcost) {
            while (true) {
                while (bars[0].next()) {
                    if (connect(maxcost)) {
                        return true;
                    }
                }
                bars[0].reset();
                for (int i = 1; i < bars.length; i++) {
                    if (bars[i].next()) {
                        break;
                    }
                    if (i == bars.length - 1) {
                        return false;
                    }
                    bars[i].reset();
                }
                if (connect(maxcost)) {
                    return true;
                }
            }
        }

        private int minCostBetween(final int i, final int j) {
            int minConnectionCost = -1;
            for (int k = Math.max(bars[i].start, bars[j].start); k <=
                    Math.min(bars[i].end, bars[j].end); k++) {
                // calculate cost for connecting at column k
                int newcost = 0;
                for (int l = i + 1; l < j; l++) {
                    final Bar midbar = bars[l];
                    if ((k >= midbar.start) && (k <= midbar.end)) {
                        newcost++;
                        if ((minConnectionCost >= 0) && (newcost >=
                                minConnectionCost)) {
                            break;
                        }
                    }
                }
                if ((minConnectionCost < 0) || (newcost < minConnectionCost)) {
                    minConnectionCost = newcost;
                    if (newcost == 0) {
                        break;
                    }
                }
            }
            return minConnectionCost;
        }
    }


    public static void main(String[] args) {
        int n = 6
        final Solution searchState = new Solution(n);
        int minCost = Integer.MAX_VALUE;
        while(true) {
            if (!searchState.nextSolution(minCost - 1)) {
                break;
            }
            minCost = searchState.cost, minCost;
            if (minCost == 0) {
                break;
            }
        }

        System.out.println("n=" + n + ", p=" + minCost);
    }
}