1

誰かが私にこのゲームhttp://puzzle-games.pogo.com/games/poppitを可能な限り少ないステップで解決するための戦略を提案できますか。

私のアイデアは、削除された後、グループの数が最も少ないバルーンのグループ（同じ色の隣人）を見つけることです。

しかし、私の実装は十分ではありません。私が考えることができる唯一のことは、風船のすべてのグループを収集し、それを削除した場合に残っているグループの数をグループごとに確認することです。もちろん、これには、グループを削除した後にバルーンを再配置してから元の順序に戻すことが含まれるため、非常に重い操作を行う必要があります。

誰かが私のアルゴリズムを実装するためのより良い方法や問題への完全に他のアプローチを思いついた場合、私は本当に感謝しています！

4

2 に答える 2

1

このゲームはSameGameの別のバージョンです。最適なソリューションが存在するかどうかの問題は、このペーパーでNP完全であることが示されました。これが意味することは、一般に、最適なソリューションを見つけるのに指数関数的な時間がかかるということです。一方、問題を充足可能性問題のインスタンスに変換すると、SATソルバーを使用して、アドホックアプローチよりも迅速に問題を解決できる場合があります。

于 2012-05-14T00:18:41.807 に答える
0

あなたが言及したのは、バックトラッキングアプローチです。できなくなるまで風船のグループを割ってから、最後の動きを元に戻し、別のことを試みます。ウィキペディアはこれを私がこれまで以上にうまく説明しています。

これは計算量が多いように聞こえますが、最近のコンピューターは問題をかなり迅速に解決できるはずだと思います。

実装に関しては、再帰関数 (自分自身を呼び出す関数) に基づいて、擬似コードは次のようになります。

void main()
{
    setupBoard();
    if(Try())
        print("Found Solution");
}

boolean Try()
{
   if(noballonsLeft)
       return true; //Found solution!
   foreach(Move move in getPossibleMoves())
   {
       doMove(move);
       if(Try())
           return true; //This try found a solution!
       undoMove(move);
   }
   return false; //No solutions found
}

これにより問題の解決策が見つかります。これを拡張して最適な解決策を見つけることは問題ありません;)

于 2012-05-13T23:23:02.410 に答える