0

私は、要するに、「空の」スペースが0で表される数値の2Dマトリックスを生成するプロジェクトに取り組んでいます。各番号は、ノードのリストによって接続されています。ノードには、数値、数値の X および Y 位置、それに隣接するすべてのスペース (その「隣人」) のリストが含まれます。アルゴリズムは上方向の移動のみを許可するため、ポイントに斜めに隣接するスペースは除きます。 、下、左、右。私が抱えている問題は、タイトルが示すように、スタック オーバーフローの問題が発生していることです。以下にコードを投稿します。誰かが助けてくれれば、とても感謝しています。

CoordList* Puzzle::GeneratePath(CoordList* Path, int GoalX, int GoalY)
{
int CurrX;
int CurrY;

CurrX = Path->NeighborX;
CurrY = Path->NeighborY;

if(CurrX == GoalX && CurrY == GoalY)
{
    return(Path);
}
else
{
    int NewX;
    int NewY;
    double NewDistance;
    int OldX;
    int OldY;
    double OldDistance;
    CoordList* PointNeighbors = NULL;
    CoordList* BestChoice = NULL;

    for(int i = 0; i < NumDirections; i++)
    {
        CoordList* NewNeighbor = new CoordList;
        NewX = CurrX + DirectsX[i];
        NewY = CurrY + DirectsY[i];
        if(IsPossible(NewX, NewY))
        {
            NewNeighbor->NeighborX = NewX;
            NewNeighbor->NeighborY = NewY;

            if(PointNeighbors == NULL)
            {
                NewNeighbor->next = NULL;
                PointNeighbors = NewNeighbor;
            }
            else
            {
                NewNeighbor->next = PointNeighbors;
                PointNeighbors = NewNeighbor;
            }
        }
        //delete NewNeighbor;
    }

    while(PointNeighbors != NULL)
    {
        if(BestChoice == NULL)
        {

            CoordList* AChoice = new CoordList;
            AChoice->next = NULL;
            NewX = PointNeighbors->NeighborX;
            NewY = PointNeighbors->NeighborY;
            AChoice->NeighborX = NewX;
            AChoice->NeighborY = NewY;
            BestChoice = AChoice;
            PointNeighbors = PointNeighbors->next;
            //delete AChoice;
        }
        else
        {
            NewX = PointNeighbors->NeighborX;
            NewY = PointNeighbors->NeighborY;
            NewDistance = DetermineDistance(NewX, NewY, GoalX, GoalY);

            OldX = BestChoice->NeighborX;
            OldY = BestChoice->NeighborY;
            OldDistance = DetermineDistance(OldX, OldY, GoalX, GoalY);

            if(NewDistance < OldDistance)
            {
                BestChoice->NeighborX = NewX;
                BestChoice->NeighborY = NewY;
            }
            PointNeighbors = PointNeighbors->next;
        }
    }
    BestChoice->next = Path;
    Path = BestChoice;
    return(GeneratePath(Path, GoalX, GoalY));
}
}

私は距離測定機能を提供するように求められました。これは、従来の Point Distance 式の単純な実装です。以下に提供します。

double Puzzle::DetermineDistance(int OneX, int OneY, int TwoX, int TwoY)
{
int DifX;
int DifY;
double PointSum;

DifX = (TwoX - OneX);
DifY = (TwoY - OneY);
DifX = (DifX * DifX);
DifY = (DifY * DifY);
PointSum = (DifX + DifY);
return (sqrt(PointSum));
}

次の IsPossible 関数は、X 値と Y 値が可能なグリッド スペース内にあるかどうかを判断します。

bool Puzzle::IsPossible(int x, int y)
{
if(x + 1 > Size - 1 || x - 1 < 0 
    || y + 1 > Size - 1 || y - 1 < 0)
{
    return false;
}
return true;
}
4

1 に答える 1

0

特に観測された発振動作では、再帰ごとに新しいローカル変数を作成するため、スタックオーバーフローを引き起こす無限再帰ループが発生する可能性があります。小さなマトリックスではその問題はないと思います。暗闇の中でのショットです:-)

振動の問題は、すでに 1 つの場所に行ったことがあるかどうかを確認していないことを示していますか?

とにかく、別の経路探索アルゴリズムを使用することを再検討したいかもしれません。エージェントベースのソリューションをお勧めします。私は、似たような構造の迷路を解くために、次の解決策を使用していました: 私はエージェントを開始した場所のスポットの "PositionsList" で開始したので、最初は開始点だけでした。次に、自分の PositionList にないすべての到達可能な位置に自分自身をコピーし、新しい位置をそのリストに追加してから自分自身を破棄しました。最初のエージェントがゴールに到達するまで、すべての新しいエージェントでこのパターンを繰り返します。そうすれば、最適なパスを見つけることが保証されます。しかし、大きな行列の場合、特にゴールに到達するためのさまざまな方法があり、位置ごとに可能な方向が多数ある場合は、メモリがかなり重くなる可能性があります! しかし、他にも非常に優れた経路探索アルゴリズムがたくさんあります。

幸運を！

于 2013-03-21T12:23:21.993 に答える