gpt4 book ai didi

java - 最少穿过 N 条平行线

转载 作者:塔克拉玛干 更新时间:2023-11-02 19:05:15 28 4
gpt4 key购买 nike

假设我们有 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/

28 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com