0

背景：私の大学のコースの1つで、チェスを作っています。GUIはすでにコントローラーへのフックで終了しています。私がしなければならないのは、オブジェクトを実装することだけです。従来は、各タイプのオブジェクトに適したネイティブ構造、移動履歴のスタック（サポートされていませんが、やり直しはできません）、ボードの2D配列/ベクトルなどを使用していました。仕様の一部は、ロードする必要があることです。ゲームを特殊なXML形式で保存するので、DOMDocumentを使用してゲーム全体を保存したいと思います。これにより、DOMの読み込み/保存アクションを実装するライブラリがある場合、XMLと構造の間で変換する必要がなくなるため、読み込みと保存が非常に簡単になります。

問題：速度。チェスのすべてのアルゴリズムでは、場所によって多くの選択を行う必要があります。

XML形式（変更不可）：

<board>
        <piece type="rook" color="white" column="0" row="7"/>
        <piece type="knight" color="white" column="1" row="7"/>
        <piece type="bishop" color="white" column="2" row="7"/>
        <piece type="queen" color="white" column="3" row="7"/>
        <piece type="king" color="white" column="4" row="7"/>
        <piece type="bishop" color="white" column="5" row="7"/>
        <piece type="knight" color="white" column="6" row="7"/>
        <piece type="rook" color="white" column="7" row="7"/>
        <piece  color="white" column="3" row="6" type="pawn"/>
        <piece row="6" type="pawn" color="white" column="4" />
</board>

次に、すべてのピース要素を取得し、属性を除外する必要があります。これはO（n）操作です。配列/ベクトルの実装では、単純なインデックス作成であるため、O（1）時間を簡単に達成できます。特に膠着状態を検出する場合、O（n）の価格は高すぎて支払うことができません。

どのように速度を向上させますか？私は基本的にDOMにインデックスを付ける方法を探しています。私はいくつかのアイデアを持っていますが、この問題をどのように解決しますか？

参考までに、私はC ++で開発しており、おそらくXML用のXercesライブラリを使用しますが、実際のコードではなく、主にアイデアを探しています（ただし、それは役に立ちます）。

4

2 に答える 2

1

DOMNodeチェス用のボードは固定寸法であるため、ポインターの2D配列を使用することにしました。これは非常に高速で、コードがいくらか複雑になりますが、問題なく機能します。

私は物事を行う別の方法を知っていたらいいのにと思います。

于 2011-11-15T17:07:38.660 に答える
0

XML構造を使用するように強制することで、速度の障害を自分で作成しました。これはすべて、迅速な保存/読み込みを提供します。これは、実際にゲームをプレイするよりも、ゲーム中に実行される頻度がはるかに少ないものです。したがって、ネイティブ構造を使用して必要な速度を取得し、シリアル化コードを記述してネイティブ構造をXMLにマップすることをお勧めします。

ただし、速度の問題については興味があります。O（n）とO（1）は、nが大きい場合にのみ問題になります。O（n）検索が問題となる部分が本当にたくさんあるのでしょうか。時間計算量は、実行速度の理論上のガイドにすぎません。これが実装されることを覚えておく必要があります。実装では、理論上の最良の選択でなくてもトレードオフは問題ない可能性があります（つまり、O（1）よりもO（n）を選択する）

于 2011-11-09T05:55:12.980 に答える