假设我们有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------ | |
| | | | |
-----------------
关于如何找到其背后的模式或逻辑的任何暗示都将是很棒的。
最佳答案
这是一个使用蛮力解决问题的草稿解决方案，假设可以在仅具有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);
}
}
关于java - N条平行线上的最小交叉点，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58316038/