java hashcode原理，Poj 1077 eight(BFS+全序列Hash解八數碼問題)

一、題意

????? 經典的八數碼問題，有人說不做此題人生不完整，哈哈。給出一個含數字1~8和字母x的3 * 3矩陣，如：

???????????1? 2? X
?????????? 3 4 ?6
???????????7? 5? 8

???? 現在要你移動x的位置（方向為上、下、左、右），使得這個矩陣為：

java hashcode原理。???????????1? 2? 3?
???????????4? 5? 6
???????????7??8?x

???? 求出最后能得到這個解的移動方案，輸出移動的操作。（不要求最優解，也就是不要求移動次數最少）

二、題解

????? 這個8數碼問題，我們可以把它看成是一個全排列，從一個初始的排列通過移動元素的位置，到達最終的123456789的這種排列，這里的X我們用9代替。

????? 我們知道X有四個選擇移動的方向，但是不一定有四個，如果在左上角就只能右移和下移了，還有很多種限制情況。由于數組是從0開始的，所以他的下標應該是：

poj2106、????? 0? 1? 2

????? 3? 4? 5

????? 6? 7? 8

???? if( id % 3 != 2)如果id不是2,5,8就可以向右移動；
?? ? if (id % 3 != 0) 如果id不是0,3,6就可以向左移動；
?? ? if( id > 2 ) 如果id大于2就可以向上移動；
???? if( id < 6)? 如果id小于6就可以向下移動。
???? 現在我們有了移動的方向了，但是我們知道可能這些選擇中包含著以前就走過的狀態。那怎么辦來避免已經訪問過的狀態呢，這就用到了把全排列轉換成數字的hash函數（這里其實還可以用康托展開），每一個排列都能對應一個數字，如果這個數字出現過就不訪問。這可以用一個Boolean數組實現。

??? 這個hash函數的原理用到了變進制和序數對的知識，詳細信息請參考：http://blog.sina.com.cn/s/blog_6635898a0100p4re.html

??? 接下來就要用到BFS來找到狀態轉換路徑了，每一個狀態用一個類表示，包括前一個狀態到本狀態的操作、本狀態的數、本狀態X所處位置索引、前一個狀態的hash值。

poj1741、??? 遍歷每個狀態從0開始，記錄可以到達的狀態（一次最多可以到達四個），直到num=123456789。例如，0可以到1、2、3，而1可以到4、5,2可以到6、7，...并用

??? q[tail].pre = head記錄之前的的結點，這樣到最后的最終結點往前遍歷就可以了。q[tail].op = op記錄了操作，輸出操作就可以了。這就相當于找到了一條路徑，路徑上的結點記錄了到這一步的操作，輸出操作就行了。但想之前所說的，這不一定是最優解，這是最快到達的，不一定是操作最少的。

三、java代碼

import java.util.Scanner;class Status{char operation;int number, index, previous;
}public class Main{static int Max = 363000;  //總得狀態數量， 9!=362880static Status[] q=new Status[Max];static int head;static int tail;static int factorial[] = {1,1,2,6,24,120,720,5040,40320};static int Pow[] = {100000000,10000000,1000000,100000,10000,1000,100,10,1};static boolean[] vis=new boolean[Max];// 全排列的hash函數。static int permutationToNumberHash(int num){ int i, j;int[] n=new int[10];for(i = 0; i < 9; i ++){n[i] = num % 10;num /= 10;}int c, key = 0;for(i = 1; i < 9; i ++){for(c = 0, j = 0; j < i; j ++)if(n[j] < n[i]) c ++;key += c * factorial[i];}return key;}static void exchangeLocation(int num, int a, int b, char op){ // 操作：第a個數和第b個數交換。int n1, n2;n1 = num / Pow[a] % 10;n2 = num / Pow[b] % 10;num = num - (n1-n2)*Pow[a] + (n1-n2)*Pow[b]; //移動后的數字大小int key = permutationToNumberHash(num);if(!vis[key]){vis[key] = true;q[tail].operation = op;q[tail].number = num;q[tail].previous = head;q[tail ++].index = b;}}static void output(int k){if(q[k].operation != 0){output(q[k].previous);System.out.print( q[k].operation);}}public static void main(String args[]){Scanner sc=new Scanner(System.in);int i, num, id , t;char c;id=-1;//讀入數據，用9代替x,用一個十進制數表示讀入數據。for(num = i = 0; i < 9; i ++){c=sc.next().charAt(0);if(c == 'x'){t = 9;id = i;}else t = c - '0';num = 10 * num + t;//順序存儲}//初始化每一個狀態for(i=0;i<Max;i++){q[i]=new Status();}boolean flag = false;head = 0;tail = 1;//q[0]表示x所在的的id和狀態數q[0].index = id;q[0].number = num;//廣度搜索找出一條路徑，最后的數是123456789./*具體實現：* 遍歷每個狀態從0開始，記錄可以到達的狀態（一次最多可以到達四個）。直到num=123456789。* 例如，0可以到1、2、3，而1可以到4、5,2可以到6、7，...并用 q[tail].pre = head記錄之前的的結點，這樣到最后* 的最終結點往前遍歷就可以了。q[tail].op = op記錄了操作，輸出操作就可以了。* */while(tail > head && !flag){int cnt = tail - head;while(cnt --!=0){num = q[head].number;if(num == 123456789){flag = true; break;}id = q[head].index;//注意這里的移動方向是指數的移動方向，不是X的移動方向//還有id的范圍是0~8/* 0 1 2* 3 4 5* 6 7 8*/if(id % 3 != 2)   //如果id不是2,5,8就可以向右移動exchangeLocation(num, id, id + 1, 'r');if(id % 3 != 0)   //如果id不是0,3,6就可以向左移動exchangeLocation(num, id, id - 1, 'l');if(id > 2)        //如果id大于2就可以向上移動exchangeLocation(num, id, id - 3, 'u');if(id < 6) 	      //如果id小于6就可以向下移動exchangeLocation(num, id, id + 3, 'd');head ++;}}if(flag) output(head);else System.out.println("unsolvable");} 
}

參考：http://blog.sina.com.cn/s/blog_6635898a0100p4sx.html

版權聲明：本文為博主原創文章，未經博主允許不得轉載。