我正在尝试编写一种算法，以便它可以从网格的任何“开始”单元格(例如图片中的第 4 号单元格)开始，并解析一次网格的每个单元格。网格可以是任何大小 3x3、4x4、8x8 等。
以下代码生成这样的路径。并且适用于 8x8 网格中的许多单元格。但对于许多细胞来说，寻找一条路径需要永远。
想知道有没有更好的方案可以引用，以便优化方案。
package
{
import flash.display.MovieClip;
public class Main extends MovieClip
{
private var rand_Num;
public var node0_Mc:MovieClip ,node1_Mc:MovieClip,node2_Mc:MovieClip,node3_Mc:MovieClip,node4_Mc:MovieClip,node5_Mc:MovieClip,node6_Mc:MovieClip,node7_Mc:MovieClip,node8_Mc:MovieClip,node9_Mc:MovieClip,
node10_Mc:MovieClip,node11_Mc:MovieClip,node12_Mc:MovieClip,node13_Mc:MovieClip,node14_Mc:MovieClip,node15_Mc:MovieClip,node16_Mc:MovieClip,node17_Mc:MovieClip,node18_Mc:MovieClip,node19_Mc:MovieClip,
node20_Mc:MovieClip,node21_Mc:MovieClip,node22_Mc:MovieClip,node23_Mc:MovieClip,node24_Mc:MovieClip,node25_Mc:MovieClip,node26_Mc:MovieClip,node27_Mc:MovieClip,node28_Mc:MovieClip,node29_Mc:MovieClip,
node30_Mc:MovieClip,node31_Mc:MovieClip,node32_Mc:MovieClip,node33_Mc:MovieClip,node34_Mc:MovieClip,node35_Mc:MovieClip,node36_Mc:MovieClip,node37_Mc:MovieClip,node38_Mc:MovieClip,node39_Mc:MovieClip,
node40_Mc:MovieClip,node41_Mc:MovieClip,node42_Mc:MovieClip,node43_Mc:MovieClip,node44_Mc:MovieClip,node45_Mc:MovieClip,node46_Mc:MovieClip,node47_Mc:MovieClip,node48_Mc:MovieClip,node49_Mc:MovieClip,
node50_Mc:MovieClip,node51_Mc:MovieClip,node52_Mc:MovieClip,node53_Mc:MovieClip,node54_Mc:MovieClip,node55_Mc:MovieClip,node56_Mc:MovieClip,node57_Mc:MovieClip,node58_Mc:MovieClip,node59_Mc:MovieClip,
node60_Mc:MovieClip, node61_Mc:MovieClip, node62_Mc:MovieClip, node63_Mc:MovieClip;
public const NUM_COLS:Number = 8;
// 3 ;// 4 ;
public const NUM_ROWS:Number = 8;// 3 ;// 4 ;
var chain_Arr:Array = [];
var blockIndex_Arr:Array = [];
var nodearr:Array;
var adjacentNodeArray_Arr:Array = [];
var parsedNodeIndex_Arr:Array = [];
var validNextAdjacentNodeIndexArray_Arr:Array = [];
var validPreviousAdjacentNodeIndexArray_Arr:Array = [];
var savePair_Arr:Array = [];
var countChain_Num:Number = 0;
var saveParent_Arr:Array = [];
public function Main()
{
// constructor code
nodearr = [node0_Mc,node1_Mc,node2_Mc,node3_Mc,node4_Mc,node5_Mc,node6_Mc,node7_Mc,node8_Mc,node9_Mc,node10_Mc,node11_Mc,node12_Mc,node13_Mc,node14_Mc,node15_Mc,node16_Mc,node17_Mc,node18_Mc,node19_Mc,node20_Mc,node21_Mc,node22_Mc,node23_Mc,node24_Mc,node25_Mc,node26_Mc,node27_Mc,node28_Mc,node29_Mc,node30_Mc,node31_Mc,node32_Mc,node33_Mc,node34_Mc,node35_Mc,node36_Mc,node37_Mc,node38_Mc,node39_Mc,node40_Mc,node41_Mc,node42_Mc,node43_Mc,node44_Mc,node45_Mc,node46_Mc,node47_Mc,node48_Mc,node49_Mc,node50_Mc,node51_Mc,node52_Mc,node53_Mc,node54_Mc,node55_Mc,node56_Mc,node57_Mc,node58_Mc,node59_Mc,node60_Mc,node61_Mc,node62_Mc,node63_Mc];
var possibleAdjacentNodeIndex_Arr:Array = [];
initValidNextAdjacentNodeIndexArray();
initValidPreviousAdjacentNodeIndexArray();
savePair_Arr = [];
var startIndex_num:Number = 45;// 0 ;
rand_Num = 62;// randomRange(10, (NUM_COLS * NUM_ROWS) - 1);
getAllChainsFromParamNodeIndexParamParentChain(startIndex_num,[startIndex_num]);
}
function initValidNextAdjacentNodeIndexArray():void
{
for (var index_num = 0; index_num < NUM_COLS*NUM_ROWS; index_num++)
{
validNextAdjacentNodeIndexArray_Arr[index_num] = getValidNodeIndexArrayAdjacentToParamNodeIndex(index_num);
//trace(validNextAdjacentNodeIndexArray_Arr[index_num]);
}
}
function initValidPreviousAdjacentNodeIndexArray():void
{
for (var index_num = 0; index_num < NUM_COLS*NUM_ROWS; index_num++)
{
validPreviousAdjacentNodeIndexArray_Arr[index_num] = getValidNodeIndexArrayAdjacentToParamNodeIndex(index_num);
//trace(validNextAdjacentNodeIndexArray_Arr[index_num]);
}
}
//function getAllChainsFromParamNodeIndexParamParentChain( path_arr:Array,index_param_num:Number ):void
function getAllChainsFromParamNodeIndexParamParentChain( index_param_num:Number, parent_arr:Array ):void
{
var i;
if ( countChain_Num > 15 )
{
return;
}
reinitPath();
var adjacent_arr = getValidNodeIndexArrayAdjacentToParamNodeIndex(index_param_num);
for (i = 0; i < adjacent_arr.length; i++)
{
reinitPath();
if ( ( checkRepeat(chain_Arr)) )
{
continue;
}
chain_Arr.push(adjacent_arr[i]);
//trace("chain starts from", chain_Arr);
var nodeIndex_num:Number = adjacent_arr[i];
var nodeIndexExist_num = 0;
var parentNode_num:Number = parent_arr[parent_arr.length - 1];
var bool:Boolean;
while ( isNaN(nodeIndex_num) == false)
{
//var childNodeIndex_num = manageValidAdjacentIndexArray(parent_arr[parent_arr.length-1], parentNode_num , nodeIndex_num );
var childNodeIndex_num = manageValidAdjacentIndexArray(adjacent_arr[i],parentNode_num,nodeIndex_num);
//var childNodeIndex_num = manageValidAdjacentIndexArray(parentNode_num, parentNode_num , nodeIndex_num );
parentNode_num = nodeIndex_num;
nodeIndex_num = childNodeIndex_num;
if ( ( checkRepeat(chain_Arr)) )
{
break;
}
if ( isNaN(nodeIndex_num) == false)
{
chain_Arr.push(nodeIndex_num);
}
}
if (chain_Arr.length > NUM_COLS * NUM_ROWS - 1)
{
//if ( !( checkRepeat(chain_Arr)) )
{
trace(chain_Arr);
saveParent_Arr[saveParent_Arr.length ] = new Array();
for (var k = 0; k < rand_Num; k++)
{
saveParent_Arr[saveParent_Arr.length - 1].push( chain_Arr[k]);
}
countChain_Num++;
}
}
};
for (i = 0; i < adjacent_arr.length; i++)
{
var arr2:Array = parent_arr.slice();
arr2.push(adjacent_arr[i]);
getAllChainsFromParamNodeIndexParamParentChain( adjacent_arr[i], arr2 );
}
function reinitPath():void
{
chain_Arr = [];
chain_Arr = chain_Arr.concat(parent_arr);
}
}
private function checkRepeat(chain_arr:Array):Boolean
{
var bool:Boolean;
var num = rand_Num;
if (chain_arr.length >= num - 1)
{
for (var i = 0; i < saveParent_Arr.length; i++)
{
//trace( saveParent_Arr[i][0], saveParent_Arr[i][1]);
if (saveParent_Arr[i] != undefined)
{
var z = 0;
for (var j = 0; j < num; j++)
{
if (saveParent_Arr[i][j] == chain_arr[j])
{
z++;
if ( z >= num)
{
bool = true;
break;
}
}
else
{
break;
}
}
if (bool)
{
break;
}
}
}
}
return bool;
}
function randomRange( minNum:Number, maxNum:Number):Number
{
return (Math.floor(Math.random() * (maxNum - minNum + 1)) + minNum);
}
function randomizeArray(arr:Array ):void
{
for (var i = 0; i < arr.length; i++)
{
var random = randomRange(0,arr.length - 1);
var temp = arr[i];
arr[i] = arr[random];
arr[random] = temp;
}
}
//will send NaN if no valid adjacent index array is possible
private function manageValidAdjacentIndexArray(chainStartIndex_num:Number, parentNodeIndex_param_num:Number, nodeIndex_num:Number):Number
{
var num_nan:Number;
var ret_num:Number;
var j;
//var tot:Number = validNextAdjacentNodeIndexArray_Arr[nodeIndex_num].length ;
j = 0;
var arr:Array = validNextAdjacentNodeIndexArray_Arr[nodeIndex_num];// getValidNodeIndexArrayAdjacentToParamNodeIndex(nodeIndex_num) ;
randomizeArray(arr);
while (arr.length > 0 )// && isNaN(ret_num))
{
ret_num = arr[j];//validNextAdjacentNodeIndexArray_Arr[nodeIndex_num][j] ;
//if this index is present in chain then remove it off
if (chain_Arr.indexOf(ret_num) >= 0)
{
//j++ ;
ret_num = num_nan;
}
j++;
if ( j >= arr.length )
{
ret_num = num_nan;
break;
}
}
return ret_num;
}
private function getValidAdjacentIndexToParamNodeIndex(nodeIndex_param_num:Number):Number
{
var adjacentNode_arr:Array = [];
var adjacentRow_arr:Array = [];
var adjacentCol_arr:Array = [];
var allIndex_arr:Array = [];
var r:Number;
var c:Number;
var row_num:Number = int(nodeIndex_param_num / NUM_COLS);
var col_num:Number = (nodeIndex_param_num % NUM_COLS);
allIndex_arr = getAllAdjacentNodeIndexArray(row_num,col_num);
validateIndices(allIndex_arr);
var ret_num:Number;
ret_num = allIndex_arr[0];
return ret_num;
}
function getValidNodeIndexArrayAdjacentToParamNodeIndex(nodeIndex_param_num:Number ):Array
{
var adjacentNode_arr = [];
for (var positionId_num = 0; positionId_num < 8; positionId_num++)
{
var num:Number = getNodeIndexAtParamPositionIdOfParamIndex(positionId_num,nodeIndex_param_num);
if (isNaN(num))
{
}
else
{
adjacentNode_arr.push(num);
}
}
return adjacentNode_arr;
}
private function getAllAdjacentNodeIndexArray(row_num:Number, col_num:Number,within_arr:Array=null):Array
{
var num:Number;
var index_arr:Array = [num,num,num,num,num,num,num,num];
var r:Number;
var c:Number;
if ( row_num > 0 )
{
r = row_num - 1;
c = col_num;
index_arr[0] = r * NUM_COLS + c;
}
if ( col_num < NUM_COLS-1)
{
r = row_num;
c = col_num + 1;
index_arr[1] = r * NUM_COLS + c;
}
if ( row_num < NUM_ROWS-1)
{
r = row_num + 1;
c = col_num;
index_arr[2] = r * NUM_COLS + c;
}
if ( col_num > 0 )
{
r = row_num;
c = col_num - 1;
index_arr[3] = r * NUM_COLS + c;
}
///////////////////////////////////////////
if ( row_num > 0 && col_num > 0)
{
r = row_num - 1;
c = col_num - 1;
index_arr[4] = r * NUM_COLS + c;
}
if ( row_num > 0 && col_num < NUM_COLS-1)
{
r = row_num - 1;
c = col_num + 1;
index_arr[5] = r * NUM_COLS + c;
}
if ( row_num < NUM_ROWS-1 && col_num < NUM_COLS-1)
{
r = row_num + 1;
c = col_num + 1;
index_arr[6] = r * NUM_COLS + c;
}
if ( row_num < NUM_ROWS-1 && col_num > 0 )
{
r = row_num + 1;
c = col_num - 1;
index_arr[7] = r * NUM_COLS + c;
}
return index_arr;
}
//the adjacent node must be present in within_arr, which we splice, one time for variation
function getNodeIndexAtParamPositionIdOfParamIndex( n:Number , nodeIndex_param_num:Number):Number
{
var adjacentNode_arr:Array = [];
var adjacentRow_arr:Array = [];
var adjacentCol_arr:Array = [];
var index_arr:Array = [];
var r:Number;
var c:Number;
var index_num:Number;
var row_num:Number = int(nodeIndex_param_num / NUM_COLS);
var col_num:Number = (nodeIndex_param_num % NUM_COLS);
index_arr = getAllAdjacentNodeIndexArray(row_num,col_num);
validateIndices(index_arr);
var ret_num:Number;
ret_num = index_arr[n];
return ret_num;
}
private function validateIndices(index_arr:Array):void
{
for (var i = 0; i < index_arr.length; i++)
{
if (chain_Arr.indexOf(index_arr[i]) == -1)
{
}
else
{
var num:Number;
index_arr[i] = num;//pushing NaN
}
}
}
}
最佳答案
这是哈密顿路径问题。它是 NP 完全的，据我所知仍然没有有效的解决方案。
检查一下:hamilton paths in grid graphs (pdf)
简短的随机算法解释:Princeton Hamiltonian path problem
或维基百科:Hamiltonian path problem
编辑:
我做了一些更多的研究，对于你的强连接方形网格(nxn 棋盘)的特殊情况，用于寻找骑士之旅的 warndoffs 规则的变体可能会在近线性时间内为你提供解决方案。看这里:A method for finding hamiltonian paths and knight tours (pdf)
关于algorithm - 在网格中查找从单元格 x 到单元格 y 的路径，以便所有单元格都被解析一次，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25960906/