emu in blogjava

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

import java.util.*;

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

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; //為了方便處理評分，把評分值放大一個(gè)倍數(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)移一個(gè)塊到硬盤上
file[sectorIndex] = newSector;
files[fileIndex] = file;
if (newSector >= 0)
sectorFill[newSector] = true;
else
memoryAvalible--; //轉(zhuǎn)移一個(gè)塊到內(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)計(jì)最多的連續(xù)塊作為這個(gè)文件順序性的評估標(biāo)準(zhǔn)
lastSector = sector;
}
order += (fileOrder + 1) * countRate / fileSectors.length;
// 順序度的評估值，每個(gè)文件最高countRate分，即排序完成。order=文件個(gè)數(shù)×countRate時(shí)全部排序完成。
}
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*算法，其中存在著兩個(gè)基本錯(cuò)誤：
每擴(kuò)展一個(gè)節(jié)點(diǎn)就把它從隊(duì)列中刪掉，造成下次構(gòu)造出相同的狀態(tài)的時(shí)候沒有辦法知道。
用toString來判斷兩個(gè)狀態(tài)是否相同，但是toString里面除了基本的sector數(shù)據(jù)之外還有評分的數(shù)據(jù)，所以不同情況下生成的相同狀態(tài)會被判斷成不同狀態(tài)。

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

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

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




import java.util.*;

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

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; //為了方便處理評分，把評分值放大一個(gè)倍數(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)移一個(gè)塊到硬盤上
file[sectorIndex] = newSector;
files[fileIndex] = file;
if (newSector >= 0)
sectorFill[newSector] = true;
else
memoryAvalible--; //轉(zhuǎn)移一個(gè)塊到內(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)計(jì)最多的連續(xù)塊作為這個(gè)文件順序性的評估標(biāo)準(zhǔn)
lastSector = sector;
}
order += (fileOrder + 1) * countRate / fileSectors.length;
// 順序度的評估值，每個(gè)文件最高countRate分，即整理完成。order=文件個(gè)數(shù)×countRate時(shí)全部排序完成。
}
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);
        // 計(jì)算全部文件占用的扇區(qū)數(shù)
        for (int i = 0; i < fileCount; i++)
            secCount += ((int[]) srcDiskElms[i]).length;
        destDiskElms = new int[fileCount][4];
        //[0]==文件在srcDiskElms中的編號
        //[1]==文件的起始位置
        //[2]==文件的最后一個(gè)扇區(qū)的位置+1
        //[3]==文件和原始狀態(tài)的重合區(qū)塊計(jì)數(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++) {
                // 找到一個(gè)還沒有放進(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]; //上一個(gè)文件結(jié)束的位置+1。
                    int maxOffset = diskSize - secCount + tmpSecCount; //文件起始位置不可能超過這個(gè)位置
                    for (int fileOffset = lastFileEndOffset;
                                          fileOffset <= maxOffset; fileOffset++) {
                        destDiskElms[n][1] = fileOffset;
                        destDiskElms[n][2] = fileOffset + fileSize; //文件的最后一個(gè)扇區(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++) {// 找到第一個(gè)可以放的
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ù)  更多評論
  

呵呵，你跟我前面兩次解此題走的是同樣的方向，其實(shí)都忽略了一點(diǎn)：題目要求的是最少移動(dòng)的次數(shù)，不是具體的移動(dòng)方案。
失敗兩次后我開始認(rèn)為，具體的移動(dòng)方案可能性增長太快，不要說盲目搜索，就是很優(yōu)化的搜索策略也經(jīng)不住增長。其實(shí)我們需要的是找到一個(gè)通用的算法可以直接推算出來需要移動(dòng)的最少次數(shù)，并且從數(shù)學(xué)上保證這個(gè)次數(shù)的方案的存在。我第三次的嘗試走的就是這個(gè)方向，可惜也沒有成功。
如果求具體的移動(dòng)的方案，這也不失為一道非常好的練習(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，也可以通過移動(dòng)7塊得到結(jié)果，可是這個(gè)程序得到的解為-2147483645  回復(fù)  更多評論
  

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

用動(dòng)態(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個(gè)文件的第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)前的移動(dòng)次數(shù)

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

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

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

注意到，下一狀態(tài)并不是唯一的，對于已知的S[i]，所有的S[i+1]中的最小值也不一定就是我們到達(dá)S[n]的一個(gè)必經(jīng)之途，關(guān)鍵問題不在于對一個(gè)已知的S[i]和S[i+1]怎么取得最小操作次數(shù)，而在于，在若干個(gè)S[i+1]狀態(tài)中那個(gè)能讓我們的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個(gè)文件的長度
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個(gè)文件的最后一個(gè)扇區(qū)存放在j的移動(dòng)步數(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個(gè)扇區(qū)，n個(gè)文件的二進(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的實(shí)現(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 的塊 需要移動(dòng)的步數(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; // 不能移動(dòng)

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

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ù)  更多評論