私はこの本から次の問題に取り組んできました。
特定の文字列処理言語は、文字列を 2 つに分割する基本的な操作を提供します。この操作には元の文字列のコピーが含まれるため、カットの場所に関係なく、長さ n の文字列に対して n 単位の時間がかかります。ここで、文字列を多くの断片に分割したいとします。休憩の順序は、総実行時間に影響を与える可能性があります。たとえば、位置 3 と 10 で 20 文字の文字列をカットする場合、位置 3 で最初のカットを行うと 20+17=37 の合計コストが発生しますが、位置 10 を最初に行うと 20+ のコストがかかります。 10=30。
m カットを指定して、文字列を m+1 個にカットする最小コストを見つける動的プログラミング アルゴリズムが必要です。
動的計画法の場合、本当に知っておく必要があるのは、状態空間がどうあるべきか、つまり部分的な問題をどのように表現するかだけです。
ここでは、新しいブレークを作成して、文字列を m+1 個に分割しています。良好な状態空間は (a, b) ペアのセットであると主張します。ここで、a は部分文字列の開始位置、b は同じ部分文字列の終了位置であり、最終的な区切りの数としてカウントされます。切れた弦。各ペアに関連するコストは、それを分割するための最小コストです。b <= a + 1 の場合、挿入するブレークがこれ以上ないため、コストは 0 です。b がそれより大きい場合、その部分文字列の次のブレークの可能な位置は点 a+1、a+2 です。 、... b-1。次のブレークは、どこに配置しても ba のコストがかかりますが、位置 k に配置すると、その後のブレークの最小コストは (a, k) + (k, b) になります。
したがって、動的計画法でこれを解決するには、最小コストの表 (a, b) を作成します。ここで、k - 1 個の可能なブレークを考慮して、文字列のコストを調べることにより、k セクションを持つ文字列のブレークのコストを計算できます。最大 k - 1 セクション。
これを拡張する 1 つの方法は、テーブル T[a, b] を作成し、そのテーブル内のすべてのエントリを無限に設定することから始めることです。次に、テーブルをもう一度調べて、b <= a+1 を T[a,b] = 0 とします。これにより、元の文字列のセクションを表すエントリが埋められ、これ以上カットする必要はありません。次に、テーブルをスキャンし、b > a + 1 の各 T[a,b] について、a < k < b となるすべての可能な k を検討し、min_k ((ブレーク a と b の間の長さ) + T[a,k] + T[k,b]) < T[a,b] T[a,b] をその最小値に設定します。これは、T[a,k] と T[k,b] で表される部分文字列を安価に切り刻む方法を知っている場所を認識しているため、T[a,b] を切り刻むより良い方法が得られます。これを m 回繰り返すと、完了です。標準の動的プログラミング バックトラックを使用して解決策を見つけてください。各 T[a,
分割統治アプローチは、この種の問題に最適なアプローチのように思えます。以下は、アルゴリズムの Java 実装です。
注：配列mは昇順でソートする必要があります（使用Arrays.sort(m);）
public int findMinCutCost(int[] m, int n) {
int cost = n * m.length;
for (int i=0; i<m.length; i++) {
cost = Math.min(findMinCutCostImpl(m, n, i), cost);
}
return cost;
}
private int findMinCutCostImpl(int[] m, int n, int i) {
if (m.length == 1) return n;
int cl = 0, cr = 0;
if (i > 0) {
cl = Integer.MAX_VALUE;
int[] ml = Arrays.copyOfRange(m, 0, i);
int nl = m[i];
for (int j=0; j<ml.length; j++) {
cl = Math.min(findMinCutCostImpl(ml, nl, j), cl);
}
}
if (i < m.length - 1) {
cr = Integer.MAX_VALUE;
int[] mr = Arrays.copyOfRange(m, i + 1, m.length);
int nr = n - m[i];
for (int j=0; j<mr.length; j++) {
mr[j] = mr[j] - m[i];
}
for (int j=0; j<mr.length; j++) {
cr = Math.min(findMinCutCostImpl(mr, nr, j), cr);
}
}
return n + cl + cr;
}
例えば ：
int n = 20;
int[] m = new int[] { 10, 3 };
System.out.println(findMinCutCost(m, n));
印刷します30
**編集**
質問の問題に答えるために、他に2つの方法を実装しました。
このメソッドは、常に最大のチャンクを再帰的にカットします。結果は常に最良の解決策とは限りませんが、最良のコストとの無視できる最小限のカット ロスの違いに対して、無視できないゲイン (私のテストから +100000% のオーダー) を提供します。
public int findMinCutCost2(int[] m, int n) {
if (m.length == 0) return 0;
if (m.length == 1) return n;
float half = n/2f;
int bestIndex = 0;
for (int i=1; i<m.length; i++) {
if (Math.abs(half - m[bestIndex]) > Math.abs(half - m[i])) {
bestIndex = i;
}
}
int cl = 0, cr = 0;
if (bestIndex > 0) {
int[] ml = Arrays.copyOfRange(m, 0, bestIndex);
int nl = m[bestIndex];
cl = findMinCutCost2(ml, nl);
}
if (bestIndex < m.length - 1) {
int[] mr = Arrays.copyOfRange(m, bestIndex + 1, m.length);
int nr = n - m[bestIndex];
for (int j=0; j<mr.length; j++) {
mr[j] = mr[j] - m[bestIndex];
}
cr = findMinCutCost2(mr, nr);
}
return n + cl + cr;
}
最小コストを計算する代わりに、異なるインデックスとバッファーを使用してください。このメソッドは一定時間で実行されるため、常に n を返します。さらに、メソッドは実際に文字列を部分文字列に分割します。
public int findMinCutCost3(int[] m, int n) {
char[][] charArr = new char[m.length+1][];
charArr[0] = new char[m[0]];
for (int i=0, j=0, k=0; j<n; j++) {
//charArr[i][k++] = string[j]; // string is the actual string to split
if (i < m.length && j == m[i]) {
if (++i >= m.length) {
charArr[i] = new char[n - m[i-1]];
} else {
charArr[i] = new char[m[i] - m[i-1]];
}
k=0;
}
}
return n;
}
注: この最後のメソッドは、 setString strの代わりに引数を受け取り、 from から配列を返すように簡単に変更できます。nn = str.length()String[]charArr[][]
パイソンコード:
mincost(n, cut_list) =min { n+ mincost(k,left_cut_list) + min(n-k, right_cut_list) }
import sys
def splitstr(n,cut_list):
if len(cut_list) == 0:
return [0,[]]
min_positions = []
min_cost = sys.maxint
for k in cut_list:
left_split = [ x for x in cut_list if x < k]
right_split = [ x-k for x in cut_list if x > k]
#print n,k, left_split, right_split
lcost = splitstr(k,left_split)
rcost = splitstr(n-k,right_split)
cost = n+lcost[0] + rcost[0]
positions = [k] + lcost[1]+ [x+k for x in rcost[1]]
#print "cost:", cost, " min: ", positions
if cost < min_cost:
min_cost = cost
min_positions = positions
return ( min_cost, min_positions)
print splitstr(20,[3,10,16]) # (40, [10, 3, 16])
print splitstr(20,[3,10]) # (30, [10, 3])
print splitstr(5,[1,2,3,4,5]) # (13, [2, 1, 3, 4, 5])
print splitstr(1,[1]) # (1, [1]) # m cuts m+1 substrings
これは c++ の実装です。DP を使用した O(n^3) 実装です。カット配列がソートされていると仮定します。そうでない場合、ソートに O(n^3) 時間がかかるため、漸近的な時間の複雑さは変わりません。
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <limits.h>
using namespace std;
int main(){
int i,j,gap,k,l,m,n;
while(scanf("%d%d",&n,&k)!=EOF){
int a[n+1][n+1];
int cut[k];
memset(a,0,sizeof(a));
for(i=0;i<k;i++)
cin >> cut[i];
for(gap=1;gap<=n;gap++){
for(i=0,j=i+gap;j<=n;j++,i++){
if(gap==1)
a[i][j]=0;
else{
int min = INT_MAX;
for(m=0;m<k;m++){
if(cut[m]<j and cut[m] >i){
int cost=(j-i)+a[i][cut[m]]+a[cut[m]][j];
if(cost<min)
min=cost;
}
}
if(min>=INT_MAX)
a[i][j]=0;
else
a[i][j]=min;
}
}
}
cout << a[0][n] << endl;
}
return 0;
}