나는 당신이 원하는 것이 무엇인지 확신 할 수 없다. 나는 당신이 염두에 두지 않은 것이 분명하다고 생각하지만 합리적이라고 생각하면 시도해 볼 수도있다.
거리가 단순히 d이고 그 이하 일 수 있기 때문에 욕심이 많은 알고리즘이 여기에서 작동해야하는 것처럼 처음에는 홍당무처럼 보입니다.가능한 한 적은 수의 (1) 가능한 한 기존 줄과 멀리 떨어져 있도록 (2) 항상 다음 줄을 배치하십시오.
이 문제에 대해 최적의 알고리즘이 있다고 가정하고 다음 줄을 마지막 줄의 a <= d에 놓습니다. 그것이 b 선이라고 말하십시오. 우리의 욕심 많은 알고리즘은 b 라인을 넘지 않을 것입니다. (첫 번째 기준은되도록 적게 배치하는 것이기 때문에) b 라인을 배치하면 c을 a <= c <= d으로 배치 할 것입니다. 가능한. 욕심이 알고리즘은 최적의 알고리즘이 한 일을하지 않은 경우
, 그것은 다음 중 한 가지 방법으로 달랐다 :
- 그것은 멀리 동일하거나 더 적은 라인을 배치했다. 최적의 알고리즘이 다음 단계에
a' 거리에 b' 회선을 배치했다고 가정합니다. 그런 다음이 선들은 거리가 a+a'이고 전체적으로 b+b' 선이 있습니다. 그러나 욕심 많은 알고리즘은이 경우 최적의 알고리즘을 b' 줄을 a+a'에 배치하여 c' = (a+a') - c을 선택하여 모방 할 수 있습니다. c > a 및 a' < d이므로 c' < d이며 법적으로 허용됩니다.
더 적은 수의 선을 서로 가깝게 배치했습니다. 이 경우는 실제로 문제가됩니다. 이 위치는 최소한 k 라인을 필요로하고 가장 먼 거리가 더 많은 라인을 필요로하고, (예를 들어) 길이가 d의 배수가되도록 홀의 배열이 선택되는 경우, 불필요한 라인을 k에 배치 할 수 있습니다.
그리드 알고리즘은 경우 2에서 작동하지 않습니다. 그러나 다른 경우에는 그렇지 않습니다. 특히 첫 번째 경우에 대한 우리의 관찰은 매우 유용합니다. 두 개의 게재 위치 (distance, lines) 및 (distance', lines')의 경우 distance >= distance' 및 lines <= lines' 인 경우 첫 번째 게재 위치가 항상 선호됩니다. 이 (start, stop)에 의해 색인 캐시로 결과를 (seq, lines)를 넣어 메모이 제이션에 의해 개선 될 수
PlaceLines(start, stop)
// if we are close enough to the other edge,
// don't place any more lines.
if start + d >= stop then return ([], 0)
// see how many lines we can place at distance
// d from the last placed lines. no need to
// ever place more lines than this
nmax = min_lines_at_distance(start + d)
// see how that selection pans out by recursively
// seeing how line placement works after choosing
// nmax lines at distance d from the last lines.
optimal = PlaceLines(start + d, stop)
optimal[0] = [d] . optimal[0]
optimal[1] = nmax + optimal[1]
// we only need to try fewer lines, never more
for n = 1 to nmax do
// find the max displacement a from the last placed
// lines where we can place n lines.
a = max_distance_for_lines(start, stop, n)
if a is undefined then continue
// see how that choice pans out by placing
// the rest of the lines
candidate = PlaceLines(start + a, stop)
candidate[0] = [a] . candidate[0]
candidate[1] = n + candidate[1]
// replace the last best placement with the
// one we just tried, if it turned out to be
// better than the last
if candidate[1] < optimal[1] then
optimal = candidate
// return the best placement we found
return optimal
: 이것은 다음과 같은 알고리즘을 제안한다. 그렇게하면 이미 평가되었을지도 모르는 과제를 계산하려고 할 때를 알 수 있습니다. 문제 인스턴스에 대해 거칠거나 미세한 이산화 여부를 불문하고이 사례를 많이 가질 것으로 기대합니다.
max_lines_at_distance 및 max_distance_for_lines 기능이 작동하는 방법에 대한 세부 정보는 없지만 이것에 대한 정보는 얻을 수 있습니다.
첫 번째는 지정된 간격 띄우기에서 지오메트리를 확장하는 데 필요한 줄 수를 알려줍니다. 기하학과 유색 구멍을 검은 색으로 픽셀 화 한 경우 표시된 변위에있는 셀의 행을보고 인접한 검은 선 세그먼트를 고려하여 몇 개의 선이 의미하는지 결정해야합니다.
두 번째 줄은 주어진 후보 수의 경우 해당 줄 수를 배치 할 수있는 현재 위치에서 최대 거리를 나타냅니다. 이 번호를 줄 수있는 최대 거리 인 또는을 배치하면이 기능을 향상시킬 수 있습니다.당신은 단지 그때부터, a하지 stop까지 검색 할 필요가
f(start, stop, x) = a 및 y < x 경우;이 개선를 사용하는 경우, 당신은 당신이 n하고를 반복하고 방향을 반전 할 수f(start, stop, x)이 정의되어 있지 않고 y < x 인 경우 더 이상 검색 할 필요가 없습니다. 어디 start와 stop 사이 n 이하의 라인을 배치하는 것은 불가능합니다 경우이 기능은 정의되지 않은 될 수
참고.
반복적 인 조회를 저장하기 위해 이러한 함수에 대해 별도로 외울 수 있습니다. 각 행에 대해 max_lines_at_distance을 사전 계산하여 나중에 사용할 수 있도록 캐시에 저장할 수 있습니다. 그런 다음 max_distance_for_lines은 두 경계 내에서 앞뒤로 캐시를 확인하는 루프가 될 수 있습니다.
고정 간격 *에 행을 배치해야하는 것은 무엇입니까? 분명히, 그것들은 모두 서로 같은 거리를 가지고 있다는 것을 의미하지는 않습니다 (당신의 모범은 이것과 모순이 될 것입니다). 선의 가로 폭에 대한 요구 사항이 있습니까? 나는. 무엇이 모양의 한가운데 만 아주 짧은 줄을 만들지 못하게 막는 것입니까? (이것은 당신에게 최소한의 수를 줄 것입니까?) –
@NicoSchertler 이는 각 행에 대해'y mod I == 0'을 의미합니다. 여기서 y는 행의 Y 좌표입니다. 여기서 제약 조건을 놓치고있는 것이 옳다. 그래서 네 번째를 추가했다. 도형 안의 사용 가능한 각 점은'D/2'보다 선에서 더 멀리있을 수 없다. 나는 주요 질문을 편집했다. 목표는 선이 구멍과 충돌하는 경우 구멍 옆에 놓고 가운데를 자르지 않고 전체 길이를 유지하고자하는 것입니다. 그러므로 라인들의 전체 길이를 최소화하는 대신에'N'을 최소화하는 목적입니다. – farbro
일반적으로 I> D의 보장 된 솔루션이 없습니다. 평행선 사이의 간격이 D보다 클 수 있으며 각 중간에서 D/2보다 큰 중간 점이 나옵니다. – jwimberley