2

小さなジャンブラー ゲームを作成したいと考えています。Javaプログラミング言語を使ってこのゲームを作ろうと思っています。以下は、ゲームの小さなスクリーン ショットです。このゲームを含む他のサイトを見つけることができませんでした。

ページの最後にあるゲームのスクリーンショット

このゲームでは、2 つの機能を追加したいと思います。

1. Manually solve the problem.
2. Automatically solve the problem.

問題を手動で解決する

数字を昇順にするための解決策をプレイして見つけることを意味します

問題を視覚的に解決する

とは、解に必要な最小限の動きをコンピューターがグラフィカルに表示することを意味します。つまり、コンピューターが動きをグラフィカルに表示し、最小限の動きで解決策を特定します。

では、このような状況をどのようにプログラムするのでしょうか?

私はインターネットで検索し、線形計画法に関連するチュートリアルを入手しました。このような問題を解決するには、何を勉強すればよいのでしょうか。自動ソリューションを解決する方法がわかりません。物事を簡単に把握できる良いチュートリアルを教えてください。

4

2 に答える 2

1

ハンマーしか持っていないときは、すべてが釘のように見えるので、この種の問題は制約プログラミングを使用して解決できると言えます。しかし、それは私が少し経験したことです。

基本的に、ボード レイアウトがあり、各「ステップ」に少数の有効な動きがあります。目的は、既知のレイアウト (昇順) に移動することです。

これを「自動的に」行うには、プログラムにソリューション パスを検索させる必要があります。これを行う手順は次のようなものです。

  1. 現在のレイアウトから、有効な移動を決定します。
  2. 有効な手札をそれぞれ取った後、レイアウトを計算します。
  3. 計算されたレイアウトのいずれかが解決策であるかどうかを確認します。もしそうなら、あなたは終わっています。
  4. どの手も解決に至らなかった場合は、新たに有効になったすべての手を計算し、1 から繰り返します。

これを行うと、いくつかの問題が発生します。まず、メモリの制約 (ボード レイアウトの無数のコピーを作成しても機能しない可能性があります)。第二に、時間/計算上の制約 (解決策を見つけるのに非常に長い時間がかかる場合があります)。これらの問題による被害を最小限に抑えるためにできることがいくつかあります。

  1. 適切な検索方法を選択してください。たとえば、深さ優先ではなく幅優先です。これにより、ソリューションを見つけるのにかかる時間が短縮され、必要なメモリが減少します。
  2. 一部の動きは「後方」です。たとえば、正方形 A を B に移動し、次に正方形 B を A に移動します (移動の繰り返し)。これらの「ループ」を検索することは無意味であり、リソースを浪費するため、そうしないようにする必要があります。
  3. 検索空間に対称性の可能性があります。私はあなたの特定の問題を解決しておらず、あなたに固有の例を示すことはできませんでしたが、n-queensにはその問題に固有の対称性に関する素晴らしいセクションがあります。見つけようとしている場合は読む価値があるかもしれませんあなたの問題の対称性。

それはあなたにいくつかの情報、または探し始めるための考えを与えるかもしれません.

于 2012-08-01T14:37:35.710 に答える
0

理解しているかどうかわかりません...

最小発生と最小パスは動的計画法の問題です

http://en.wikipedia.org/wiki/Dynamic_programming

非常に簡単に言えば、すべての解を計算し、より良い解を示す必要があります。動的計画法の理解と開発はそれほど単純ではありませんが、試すことはできます...

ただし、それをどのように混合するかを覚えて、その解決策を示すことをお勧めします...

于 2012-08-01T09:46:40.407 に答える