emu in blogjava

用A*算法來擴(kuò)展?fàn)顟B(tài)樹，當(dāng)問題稍微復(fù)雜一點(diǎn)的時候狀態(tài)樹生長的太厲害，沒有辦法在規(guī)定時間內(nèi)找到解，失??！

import java.util.*;

// 節(jié)點(diǎn)增長方式：
// 1、如果內(nèi)存區(qū)域為空，讀取任一塊數(shù)據(jù)
// 2、如果內(nèi)存區(qū)域非空，寫一個內(nèi)存塊到任意一個空白的位置

public class DiskDefrag {
public static void main(String[] args) {
String[]disk = new String[] {"3 4 5 6 8 9 10", "17 16 15"};
int size = 20;
assertEquals(new DiskDefrag().minMoves(disk, size), 5);

disk = new String[] {"1 2 3 5 4 6 7 8"};
size = 10;
assertEquals(new DiskDefrag().minMoves(disk, size), 2);
/*
disk = new String[] {"1 3 5 7","0 2 4 8","6 9"};
size = 100;
assertEquals(new DiskDefrag().minMoves(disk, size), 7);
*/
System.out.println("All passed!");

}

private static int countRate = 100; //為了方便處理評分，把評分值放大一個倍數(shù)后取整。
private static int memorySector = 2; //內(nèi)存可存放的數(shù)據(jù)
private static void assertEquals(int a, int b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public int minMoves(String[] disk, int size) {
DiskStatus d = new DiskStatus(disk, size);
// System.out.println(d.countSecotrOrder());
int countAim = disk.length * countRate;
if (countAim == d.countSecotrOrder())
return 0;
ArrayList diskStatus = new ArrayList();
diskStatus.add(d);
while (true) {
d = getMostHopefulStatus(diskStatus);
System.out.println(d);
if (d.countSecotrOrder() == countAim)
return d.operationCount / 2;
diskStatus.remove(d);
for (int i = 0; i < d.files.length; i++) {
int[] file = (int[]) d.files[i];
for (int j = 0; j < file.length; j++) {
if (file[j] >= 0) {
if (d.memoryAvalible > 0) {
DiskStatus newStatus = new DiskStatus(d, i, j, -1);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
} else {
for (int k = 0; k < d.sectorFill.length; k++) {
if (!d.sectorFill[k]) {
DiskStatus newStatus = new DiskStatus(d, i, j,
k);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
}
}
}
}
}
}

private boolean checkExist(ArrayList statusList, DiskStatus status) {
String st = status.toString();
for (int i = 0, n = statusList.size(); i < n; i++) {
if (st.endsWith(statusList.get(i).toString()))
return true;
}
return false;
}

private DiskStatus getMostHopefulStatus(ArrayList list) {
// System.out.println(list);
DiskStatus result = (DiskStatus) list.get(0);
for (int i = 1, n = list.size(); i < n; i++) {
DiskStatus tmpStatus = (DiskStatus) list.get(i);
if (result.countStatus() < tmpStatus.countStatus())
result = tmpStatus;
}
return result;
}

class DiskStatus {
// DiskStatus parentStatus;
// boolean expanded = false;
Object[] files;
boolean[] sectorFill;
int order = -1;
int operationCount = 0; //操作次數(shù)記數(shù)
int memoryAvalible = memorySector;
public DiskStatus(DiskStatus d, int fileIndex, int sectorIndex,
int newSector) {
// parentStatus = d;
// d.expanded = true;
files = d.files.clone();
sectorFill = d.sectorFill.clone();
int[] file = ((int[]) files[fileIndex]).clone();
memoryAvalible = d.memoryAvalible;
if (file[sectorIndex] >= 0)
sectorFill[file[sectorIndex]] = false;
else
memoryAvalible++; //轉(zhuǎn)移一個塊到硬盤上
file[sectorIndex] = newSector;
files[fileIndex] = file;
if (newSector >= 0)
sectorFill[newSector] = true;
else
memoryAvalible--; //轉(zhuǎn)移一個塊到內(nèi)存上
order = -1;
operationCount = d.operationCount + 1;
}

public DiskStatus(String[] disk, int size) {
files = new Object[disk.length];
sectorFill = new boolean[size];
for (int i = 0; i < disk.length; i++) {
String[] tmp = disk[i].split(" ");
int[] fileSectors = new int[tmp.length];
for (int j = 0; j < tmp.length; j++) {
int k = Integer.parseInt(tmp[j], 10);
fileSectors[j] = k;
sectorFill[k] = true;
}
files[i] = fileSectors;
}
}

public int countSecotrOrder() {
if (files == null)
return -1;
if (order >= 0)
return order;
order = 0;
for (int i = 0; i < files.length; i++) {
int[] fileSectors = (int[]) files[i];
int lastSector = fileSectors[0];
int fileOrder = 0, orderedSecCount = 0;
for (int j = 1; j < fileSectors.length; j++) {
int sector = fileSectors[j];
if (sector == lastSector + 1)
orderedSecCount++;
else
orderedSecCount = 0;
if (orderedSecCount > fileOrder)
fileOrder = orderedSecCount;
//統(tǒng)計最多的連續(xù)塊作為這個文件順序性的評估標(biāo)準(zhǔn)
lastSector = sector;
}
order += (fileOrder + 1) * countRate / fileSectors.length;
// 順序度的評估值，每個文件最高countRate分，即排序完成。order=文件個數(shù)×countRate時全部排序完成。
}
return order;
}

public int countStatus() {
return countSecotrOrder() - operationCount*2;
}

// public int compareTo(Object o) {
// return ((DiskStatus) o).countSecotrOrder() - countSecotrOrder();
// }

public String toString() {
StringBuffer result = new StringBuffer();
for (int i = 0; i < files.length; i++) {
int[] file = (int[]) files[i];
for (int j = 0; j < file.length; j++) {
if (j > 0)
result.append('.');
result.append(file[j]);
}
result.append("(order:").append(countSecotrOrder()).append(")(count:").append(countStatus()).append(')').append(
'\n');
}
return result.toString();
}
}
}


  回復(fù)  更多評論
  

檢討了上面的A*算法，其中存在著兩個基本錯誤：
每擴(kuò)展一個節(jié)點(diǎn)就把它從隊列中刪掉，造成下次構(gòu)造出相同的狀態(tài)的時候沒有辦法知道。
用toString來判斷兩個狀態(tài)是否相同，但是toString里面除了基本的sector數(shù)據(jù)之外還有評分的數(shù)據(jù)，所以不同情況下生成的相同狀態(tài)會被判斷成不同狀態(tài)。

修正后的A*算法，可以計算出一個比較合理和可行的整理過程，但是沒有辦法保證找到最好的一種（擴(kuò)展過多的可能性會造成運(yùn)算超時）。

理論上說只要修改評估策略（countStatus函數(shù)）就可以保證算法總是朝正確的方向擴(kuò)張，但是創(chuàng)造一個合理的評估函數(shù)本身就是一個難題。

也許A*算法根本就不是這道題的正解。




import java.util.*;

// 節(jié)點(diǎn)增長方式：
// 1、如果內(nèi)存區(qū)域為空，讀取任一塊數(shù)據(jù)
// 2、如果內(nèi)存區(qū)域非空，寫一個內(nèi)存塊到任意一個空白的位置

public class DiskDefrag {
public static void main(String[] args) {

String[] disk = new String[] {"3 4 5 6 8 9 10", "17 16 15"};
int size = 20;
assertEquals(new DiskDefrag().minMoves(disk, size), 5);

disk = new String[] {"1 2 3 5 4 6 7 8"};
size = 10;
assertEquals(new DiskDefrag().minMoves(disk, size), 2);

disk = new String[] {"1 3 5 7", "0 2 4 8", "6 9"};
size = 100;
assertEquals(new DiskDefrag().minMoves(disk, size), 8);

System.out.println("All passed!");

}

private static int countRate = 1000; //為了方便處理評分，把評分值放大一個倍數(shù)后取整。
private static int memorySector = 2; //內(nèi)存可存放的數(shù)據(jù)
private static void assertEquals(int a, int b) {
if (a != b)
throw new RuntimeException("assert failed!! Expected " + b +
" but got " + a);
}

public int minMoves(String[] disk, int size) {
DiskStatus d = new DiskStatus(disk, size);
// System.out.println(d.countSecotrOrder());
int countAim = disk.length * countRate;
if (countAim == d.countSecotrOrder())
return 0;
ArrayList diskStatus = new ArrayList();
diskStatus.add(d);
while (true) {
d = getMostHopefulStatus(diskStatus);
// System.out.println(d);
if (d.countSecotrOrder() == countAim) {
int result = d.operationCount / 2;
System.out.print("-----------------------------------------\n" +
d);
while (d.parentStatus != null) {
d = d.parentStatus;
System.out.print("\n" + d);
}
return result;
}
d.expanded = true;
for (int i = 0; i < d.files.length; i++) {
int[] file = (int[]) d.files[i];
for (int j = 0; j < file.length; j++) {
if (file[j] >= 0) {
if (d.memoryAvalible > 0) {
DiskStatus newStatus = new DiskStatus(d, i, j, -10);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
} else {
for (int k = 0; k < d.sectorFill.length; k++) {
if (!d.sectorFill[k]) {
DiskStatus newStatus = new DiskStatus(d, i, j,
k);
if (!checkExist(diskStatus, newStatus))
diskStatus.add(newStatus);
}
}
}
}
}
}
}

private boolean checkExist(ArrayList statusList, DiskStatus status) {
String map = status.getDiskMap();
for (int i = 0, n = statusList.size(); i < n; i++) {
if (map.equals(((DiskStatus) statusList.get(i)).getDiskMap()))
return true;
}
return false;
}

private DiskStatus getMostHopefulStatus(ArrayList list) {
// System.out.println(list);
DiskStatus result = null;

for (int i = 0, n = list.size(); i < n; i++) {
DiskStatus tmpStatus = (DiskStatus) list.get(i);
if (!tmpStatus.expanded) {
if (result == null) {
result = tmpStatus;
} else {
if (result.countStatus() < tmpStatus.countStatus())
result = tmpStatus;
}
}
}
return result;
}

class DiskStatus {
DiskStatus parentStatus;
boolean expanded = false;
Object[] files;
boolean[] sectorFill;
int order = -1;
int operationCount = 0; //操作次數(shù)記數(shù)
int memoryAvalible = memorySector;
public DiskStatus(DiskStatus d, int fileIndex, int sectorIndex,
int newSector) {
parentStatus = d;
// d.expanded = true;
files = d.files.clone();
sectorFill = d.sectorFill.clone();
int[] file = ((int[]) files[fileIndex]).clone();
memoryAvalible = d.memoryAvalible;
if (file[sectorIndex] >= 0)
sectorFill[file[sectorIndex]] = false;
else
memoryAvalible++; //轉(zhuǎn)移一個塊到硬盤上
file[sectorIndex] = newSector;
files[fileIndex] = file;
if (newSector >= 0)
sectorFill[newSector] = true;
else
memoryAvalible--; //轉(zhuǎn)移一個塊到內(nèi)存上
order = -1;
operationCount = d.operationCount + 1;
}

public DiskStatus(String[] disk, int size) {
files = new Object[disk.length];
sectorFill = new boolean[size];
for (int i = 0; i < disk.length; i++) {
String[] tmp = disk[i].split(" ");
int[] fileSectors = new int[tmp.length];
for (int j = 0; j < tmp.length; j++) {
int k = Integer.parseInt(tmp[j], 10);
fileSectors[j] = k;
sectorFill[k] = true;
}
files[i] = fileSectors;
}
}

public int countSecotrOrder() {
if (files == null)
return -1;
if (order >= 0)
return order;
order = 0;
for (int i = 0; i < files.length; i++) {
int[] fileSectors = (int[]) files[i];
int lastSector = fileSectors[0];
int fileOrder = 0, orderedSecCount = 0;
for (int j = 1; j < fileSectors.length; j++) {
int sector = fileSectors[j];
if (sector == lastSector + 1)
orderedSecCount++;
else
orderedSecCount = 0;
if (orderedSecCount > fileOrder)
fileOrder = orderedSecCount;
//統(tǒng)計最多的連續(xù)塊作為這個文件順序性的評估標(biāo)準(zhǔn)
lastSector = sector;
}
order += (fileOrder + 1) * countRate / fileSectors.length;
// 順序度的評估值，每個文件最高countRate分，即整理完成。order=文件個數(shù)×countRate時全部排序完成。
}
return order;
}

public int countStatus() {
return countSecotrOrder() - operationCount * 20;
}


public String toString() {
StringBuffer result = new StringBuffer();
for (int i = 0; i < files.length; i++) {
int[] file = (int[]) files[i];
for (int j = 0; j < file.length; j++) {
if (j > 0)
result.append('\t');
if (file[j] >= 0)
result.append(file[j]);
else
result.append('*');
}
result.append("\t\t");
}
result.append('\n');
// result.append("(order:").append(countSecotrOrder())
// .append(")(count:").append(countStatus())
// .append(")(operation:").append(operationCount).append(')')
// .append(
// '\n');
return result.toString();
}

private String diskMap = null;
private String getDiskMap() {
if (diskMap != null)
return diskMap;
StringBuffer map = new StringBuffer();
for (int i = 0; i < files.length; i++) {
int[] file = (int[]) files[i];
for (int j = 0; j < file.length; j++) {
map.append(file[j]).append(',');
}
map.append(';');
}
diskMap = map.toString();
return diskMap;
}
}
}
  回復(fù)  更多評論
  

public class DiskDefrag {

    public static void main(String[] args) {
        String[] disk = new String[] {"3 4 5 6 8 9 10", "17 16 15"};
        int size = 20;
        assertEquals(new DiskDefrag().minMoves(disk, size), 5);

        disk = new String[] {"0 1 2 3 5 4 6 7 8 9"};
        size = 10;
        assertEquals(new DiskDefrag().minMoves(disk, size), 2);

        disk = new String[] {"1 3 5 7", "0 2 4 8", "6 9"};
        size = 100;
        assertEquals(new DiskDefrag().minMoves(disk, size), 7);

        disk = new String[] {"31 32 30","27 28 29", "13 24 5",  "19 10 21", "12 3 34",
               "15 6 17", "18 9 0","16 7 8","11 22 23","20 1 2","4 25 26","33 14 35"};
        size = 38;
//        assertEquals(new DiskDefrag().minMoves(disk, size), 17);

        disk = new String[] {"8 0 7 51", "47 22 26 30 46", "41 4 9 10 20",
               "33 5 28 39 42", "31 12 56 57", "13 6 17 24 27 36 54",
               "58 32 34 45", "19 2", "3 11 15 25 38 48", "23 1 18 21 29 44 55",
               "40 16 35 43 49 52 53 59", "37 14 50"};
        size = 60;
//        assertEquals(new DiskDefrag().minMoves(disk, size), 50);
        System.out.println("All passed!");

    }

    private static void assertEquals(int a, int b) {
        if (a != b)
            throw new RuntimeException("assert failed!! Expected " + b +
                                       " but got " + a);
    }

    private int fileCount = 0;
    private int secCount, diskSize;
    private Object[] srcDiskElms;
    private int[][] destDiskElms;
    int maxSuperpositionCount = 0;
    public int minMoves(String[] disk, int size) {
        fileCount = disk.length;
        diskSize = size;
        // 整理String數(shù)據(jù)建立int數(shù)組
        srcDiskElms = getDiskElms(disk);
        // 計算全部文件占用的扇區(qū)數(shù)
        for (int i = 0; i < fileCount; i++)
            secCount += ((int[]) srcDiskElms[i]).length;
        destDiskElms = new int[fileCount][4];
        //[0]==文件在srcDiskElms中的編號
        //[1]==文件的起始位置
        //[2]==文件的最后一個扇區(qū)的位置+1
        //[3]==文件和原始狀態(tài)的重合區(qū)塊計數(shù)

        getMaxSuperpositionCount(0, 0, 0, 0);
        return secCount - maxSuperpositionCount;
    }

    private void getMaxSuperpositionCount(int n, int tmpSecCount,
                                          int tmpSuperpositionCount,
                                          int tmpMoveCount) {
        // 找重合程度最高的文件存儲方式
        if (n < fileCount) {
            for (int i = 0; i < fileCount; i++) {
                // 找到一個還沒有放進(jìn)destDiskElms的文件（的編號）
                int k = 0;
                for (; k < n; k++)
                    if (destDiskElms[k][0] == i)
                        k = fileCount + 1;
                if (k < fileCount) {
                    int[] srcFile = (int[]) srcDiskElms[i];
                    destDiskElms[n][0] = i;
                    int fileSize = srcFile.length;
                    int lastFileEndOffset = (n == 0) ? 0 :
                                            destDiskElms[n - 1][2]; //上一個文件結(jié)束的位置+1。
                    int maxOffset = diskSize - secCount + tmpSecCount; //文件起始位置不可能超過這個位置
                    for (int fileOffset = lastFileEndOffset;
                                          fileOffset <= maxOffset; fileOffset++) {
                        destDiskElms[n][1] = fileOffset;
                        destDiskElms[n][2] = fileOffset + fileSize; //文件的最后一個扇區(qū)的位置+1
                        int superpositionCount = 0;
                        for (int j = 0; j < fileSize; j++)
                            if (srcFile[j] == fileOffset + j)
                                superpositionCount++;
                        int moveCount = fileSize - superpositionCount;
                        if (tmpMoveCount + moveCount<secCount - maxSuperpositionCount){
                            destDiskElms[n][3] = superpositionCount;
                            getMaxSuperpositionCount(n + 1,
                                    tmpSecCount + fileSize,
                                    tmpSuperpositionCount +
                                    superpositionCount,
                                    tmpMoveCount + moveCount);
                        }
                    }
                }
            }
        } else {
            int superpositionCount = 0;
            for (int i = 0; i < n; i++)
                superpositionCount += destDiskElms[i][3];
            if (maxSuperpositionCount < superpositionCount)
                maxSuperpositionCount = superpositionCount;

        }

    }

    private Object[] getDiskElms(String[] disk) {
        Object[] result = new Object[disk.length];
        for (int i = 0; i < disk.length; i++) {
            String[] d = disk[i].split(" ");
            int[] ar = new int[d.length];
            for (int j = 0; j < d.length; j++)
                ar[j] = Integer.parseInt(d[j], 10);
            result[i] = ar;
        }
        return result;
    }

}

  回復(fù)  更多評論
  

敗給這一組數(shù)據(jù)了：
{"8 0 7 51", "47 22 26 30 46", "41 4 9 10 20","33 5 28 39 42", "31 12 56 57", "13 6 17 24 27 36 54","58 32 34 45", "19 2", "3 11 15 25 38 48", "23 1 18 21 29 44 55","40 16 35 43 49 52 53 59", "37 14 50"}
期待結(jié)果：50
  回復(fù)  更多評論
  

簡單的蠻力搜索遞歸算法，很簡單，可以得出正確的結(jié)果，但是隨著問題空間的增長復(fù)雜度成指數(shù)增長，很恐怖。期待更有效率的解法，如果有好的算法給我一份: chuchuns@cn.ibm.com , 謝謝。

import java.util.Enumeration;
import java.util.Hashtable;

import junit.framework.TestCase;

public class DiskDefragmenter extends TestCase {

int min = Integer.MAX_VALUE;

public int minMove(int[][] files, int size) {
Disk _disk = new Disk();
int min = _doMove(_disk, files, size);
return min;
}

int _doMove(Disk disk, int[][] files, int size) {
int min = Integer.MAX_VALUE;
for (int i = 0; i < files.length; i++) {// 找到第一個可以放的
if (disk.containsFile(i))
continue;

for (int j = 0; j < size; j++) {
int moveCount = 0;

if (!disk.canPut(j, j + files[i].length -1))
continue;
if (files[i].length + j > size - 1)
break;

System.out.println("" + (i+1) + ": " + j + "-" + (j + files[i].length -1));

Disk tempDisk = new Disk(disk);
BigSeg one = new BigSeg();
one.low = j;
one.high = j + files[i].length - 1;
tempDisk.insertSeg(i, one);

moveCount += calculateMoveCount(files[i], j);

int t = _doMove(tempDisk, files, size);

moveCount += t;
if (min > moveCount) {
min = moveCount;
}

}

}
if (disk.size() == files.length)
return 0;
return min;

}

int calculateMoveCount(int[] seg, int index) {
int count = 0;
int _index = index;
for (int i = 0; i < seg.length; i++, _index++) {
if (seg[i] != _index)
++count;
}
return count;
}

public static void main(String args[]) {
}

class BigSeg implements Cloneable {
int low, high;

public BigSeg(){}
public BigSeg(BigSeg b) {
low = b.low;
high = b.high;
}
}

class Disk {
/**
* i:BigSeg
*/
Hashtable ht = new Hashtable();

public Disk(){
//
}

public Disk(Disk d) {
Enumeration e = d.ht.keys();
while (e.hasMoreElements()) {
int k = ((Integer) e.nextElement()).intValue();
BigSeg b = new BigSeg((BigSeg) d.ht.get(new Integer(k)));
ht.put(new Integer(k), b);

}

}

public int size() {
return ht.size();
}

boolean contains(int low, int high) {
Enumeration em = ht.elements();
while (em.hasMoreElements()) {
BigSeg e = (BigSeg) em.nextElement();
if ((low <= e.high && low >= e.low)
| (high <= e.high && high >= e.low))
return true;
}

return false;
}

public void insertSeg(int i, BigSeg one) {
ht.put(new Integer(i), one);

}

boolean canPut(int low, int high) {
return !contains(low, high);
}

public boolean containsFile(int i) {
return ht.containsKey(new Integer(i));
}
}

}
  回復(fù)  更多評論
  

呵呵，你跟我前面兩次解此題走的是同樣的方向，其實都忽略了一點(diǎn)：題目要求的是最少移動的次數(shù)，不是具體的移動方案。
失敗兩次后我開始認(rèn)為，具體的移動方案可能性增長太快，不要說盲目搜索，就是很優(yōu)化的搜索策略也經(jīng)不住增長。其實我們需要的是找到一個通用的算法可以直接推算出來需要移動的最少次數(shù)，并且從數(shù)學(xué)上保證這個次數(shù)的方案的存在。我第三次的嘗試走的就是這個方向，可惜也沒有成功。
如果求具體的移動的方案，這也不失為一道非常好的練習(xí)題。盲目搜索沒有多大意義的，我已經(jīng)試過A*了，另外有朋友說他也試過遺傳算法，你有什么其他的想法也不妨再試試看。
  回復(fù)  更多評論
  

bitterlemon(春生)的方案是不是有點(diǎn)問題？

用{"1 3 5 7", "0 2 4 8", "6 9"}, 100這組數(shù)據(jù)測，居然有8千多組解(minimum sectors = 7)

而且同樣這組數(shù)據(jù)、即使磁盤容量為10，也可以通過移動7塊得到結(jié)果，可是這個程序得到的解為-2147483645  回復(fù)  更多評論
  

BitMask/DP  回復(fù)  更多評論
  

用動態(tài)規(guī)劃？具體怎么做呢？
cheapwine是judgeonline過來的??？
  回復(fù)  更多評論
  

2^12種狀態(tài)，硬做。  回復(fù)  更多評論
  

能做到2^12種狀態(tài)就好了。我分析的結(jié)果是12！種狀態(tài)阿，比2^12多了十萬倍以上。  回復(fù)  更多評論
  

@emu

設(shè)當(dāng)前 狀態(tài) 為 [-1,-1] [-1,-1] a1 a2 a3 ... an [-1,-1] ... [-1,-1] b1 b2 .. bk [-1,-1] [-1,-1]
[x,y] 表示第x個文件的第y塊

如{"3 4 5 6 8 9 10","17 16 15"} 20
轉(zhuǎn)變?yōu)?[-1 -1] [-1 -1] [-1 -1] [0 0] [0 1] [0 2] [0 3] [-1 -1] [0 4] [0 5] [0 6] [-1 -1] [-1 -1] [-1 -1] [-1 -1] [1 2] [1 1] [1 0] [-1 -1] [-1 -1]

{"1 3 5 7","0 2 4 8","6 9"} 100
轉(zhuǎn)變?yōu)?[1 0] [0 0] [1 1] [0 1] [1 2] [0 2] [2 0] [0 3] [1 3] [2 1] [-1 -1] [-1 -1] 。。。。

設(shè)S[i] 為當(dāng)前的移動次數(shù)

有兩種方法到達(dá)下一狀態(tài)
1。[-1 -1] 和 一非[-1 -1]交換
2。兩非[-1 -1]交換 （借助2個cache）

則S[i+1] = min ( 方法1+1，方法2+2 )

由于最后還需要順序性和連續(xù)性，交換的時候必須保證 如[p q+1]必須和[p q]之后的塊交換。   回復(fù)  更多評論
  

注意到，下一狀態(tài)并不是唯一的，對于已知的S[i]，所有的S[i+1]中的最小值也不一定就是我們到達(dá)S[n]的一個必經(jīng)之途，關(guān)鍵問題不在于對一個已知的S[i]和S[i+1]怎么取得最小操作次數(shù)，而在于，在若干個S[i+1]狀態(tài)中那個能讓我們的S[n]得到最小值呢？  回復(fù)  更多評論
  

hgw的解答：
#include<stdio.h>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;
int z[100+8][1<<12];
class DiskDefrag
{
public:
static int minMoves(vector<string> disk, int size)
{
int n,i,j,k,now,lx[12][64],my[12],get[12][100+8];
n=disk.size();
for(i=0;i<n;i++) //讀入數(shù)據(jù)
{
my[i]=0; //my[i]表示第i個文件的長度
now=-1;
for(j=0;j<disk[i].size();j++)
if(disk[i][j]>='0'&&disk[i][j]<='9')
{
if(now==-1)
now=disk[i][j]-'0';
else
now=now*10+disk[i][j]-'0';
}
else if(now!=-1)
{
lx[i][my[i]++]=now;
now=-1;
}
if(now!=-1)
lx[i][my[i]++]=now;
}
memset(get,0X10,sizeof(get));
//get[i][j]表示第i個文件的最后一個扇區(qū)存放在j的移動步數(shù)
for(i=0;i<n;i++)
for(j=0;j<size;j++)
if(j+1>=my[i])
{
get[i][j]=0;
for(k=0;k<my[i];k++)
if(lx[i][my[i]-k-1]!=j-k)
get[i][j]++;
}
memset(z,0X10,sizeof(z));
/*
z[i][j]表示到第i個扇區(qū)，n個文件的二進(jìn)制狀態(tài)為j(1表示該文件已搞定，0表示未)的最小步數(shù)
z[i][j]=min{[i-1][j],[i-my[k]][j^(1<<k)]+get[k][i](k=0,1,2,……,n-1且(i&(1<<k))>0)}
*/
for(i=0;i<size;i++)
for(j=0;j<(1<<n);j++)
{
if(i&&z[i-1][j]<z[i][j])
z[i][j]=z[i-1][j];
for(k=0;k<n;k++)
if(j&(1<<k))
{
if(i+1>=my[k])
{
if(i-my[k]<0) //[-1][0]=0的實現(xiàn)
{
if(!(j^(1<<k)))
if(get[k][i]<z[i][j])
z[i][j]=get[k][i];
}
else
{
if(z[i-my[k]][j^(1<<k)]+get[k][i]<z[i][j])
z[i][j]=z[i-my[k]][j^(1<<k)]+get[k][i];
}
}
}
}
return z[size-1][(1<<n)-1];
}
};
int main() //測試數(shù)據(jù)，你blog上的那一組，期望結(jié)果：50
{
vector<string> a;
int b;
a.push_back("8 0 7 51");
a.push_back("47 22 26 30 46");
a.push_back("41 4 9 10 20");
a.push_back("33 5 28 39 42");
a.push_back("31 12 56 57");
a.push_back("13 6 17 24 27 36 54");
a.push_back("58 32 34 45");
a.push_back("19 2");
a.push_back("3 11 15 25 38 48");
a.push_back("23 1 18 21 29 44 55");
a.push_back("40 16 35 43 49 52 53 59");
a.push_back("37 14 50");
b=60;
printf("%d\n",DiskDefrag::minMoves(a,b));
return 0;
}  回復(fù)  更多評論
  

wqb的解答
#include<stdio.h>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<memory>
#include<math.h>
#include<time.h>
#include<string.h>
#include<algorithm>

using namespace std;

#define minx(i,j) ((i)<(j)?(i):(j))
#define maxx(i,j) ((i)>(j)?(i):(j))
#define abxx(i) ((i)>0?(i):(-(i)))
#define eps 1e-9
#define mod (1<<20)

int dp[128][1<<12];
int ro[128][1<<12];
int pr[128][1<<12];
int ll[128][1<<12];
int ax[128][1<<12];

inline bool digit(char i)
{
return i>='0'&&i<='9';
}

class DiskDefrag
{
public:
void dfsoutlujing(int s,int i)
{
if(!i)return ;
while(pr[s][i]!=s)s=pr[s][i];
dfsoutlujing(ll[s][i],i^(1<<(ro[s][i])));
printf("在 %d %d 區(qū)間 放 %d 的塊 需要移動的步數(shù) %d\n",s-ll[s][i],s,ro[s][i],ax[s][i]);
}
int minMoves(vector<string> disk, int size)
{
int s=disk.size();

int len[16];

int sector[16][128];

int i;
int j;
int k;
int t;
int x;

for(i=0;i<s;i++)
{
k=-1;len[i]=0;
for(j=0;disk[i][j];j++)
{
if(digit((char)(disk[i][j])))
{
if(k==-1)k=disk[i][j]-'0';
else k=k*10+disk[i][j]-'0';
}
else if(k!=-1)
{
sector[i][len[i]++]=k;
k=-1;
}
}
if(k!=-1)
sector[i][len[i]++]=k;
}

int sum=0;

for(i=0;i<s;i++)
sum+=len[i];

if(sum>size)return -1; // 不能移動

//////////////////////////////

memset(dp,1,sizeof(dp));

for(i=0;i<128;i++)
dp[i][0]=0;

for(j=0;j<size;j++)
for(i=1;i<(1<<s);i++)
{
t=-1;
for(k=0;k<s;k++)
if(i&(1<<k))
t+=len[k];
if(t>j)
continue;

if(j)
{
dp[j][i]=dp[j-1][i];
pr[j][i]=j-1;
}

for(k=0;k<s;k++)
if(i&(1<<k))
{
t=0; // cost
for(x=0;x<len[k];x++)
if(sector[k][x]!=x+j-len[k]+1)
t++;

if(dp[j-len[k]][i^(1<<k)]+t<dp[j][i]) // 最優(yōu)子結(jié)構(gòu)
{
dp[j][i]=dp[j-len[k]][i^(1<<k)]+t;
ro[j][i]=k;
pr[j][i]=j;
ax[j][i]=t;
ll[j][i]=j-len[k];
}
}
}

dfsoutlujing(size-1,(1<<s)-1); // 打印路徑

if(sum==size&&dp[size-1][(1<<s)-1])
return -1;
else
return dp[size-1][(1<<s)-1];
}
};

int main()
{
int i;

DiskDefrag wqb;

while(scanf("%d",&i)==1)
{
double wqbdf=clock();

int ncase;
vector<string> df;
scanf("%d",&ncase);
for(i=0;i<ncase;i++)
{
int s;
string smy;
bool flag=false;
char str[16];
scanf("%d",&s);
for(int j=0;j<s;j++)
{
if(flag)smy+=' ';
else flag=true;

scanf("%s",str);

for(int k=0;str[k];k++)
smy+=str[k];
}
df.push_back (smy);
}
scanf("%d",&i);
printf("%d\n",wqb.minMoves (df,i));

printf("%lf\n",clock()-wqbdf);
}

return 0;
}






/*

1
2
7
3 4 5 6 8 9 10
3
17 16 15
20
1
1
8
1 2 3 5 4 6 7 8
10
1
3
4
1 3 5 7
4
0 2 4 8
2
6 9
100

1
12
4
8 0 7 51
5
47 22 26 30 46
5
41 4 9 10 20
5
33 5 28 39 42
4
31 12 56 57
7
13 6 17 24 27 36 54
4
58 32 34 45
2
19 2
6
3 11 15 25 38 48
7
23 1 18 21 29 44 55
8
40 16 35 43 49 52 53 59
3
37 14 50
89

1
1
2
0 1
2

*/  回復(fù)  更多評論
  

學(xué)習(xí)了,有點(diǎn)用處,  回復(fù)  更多評論