2

データ構造に対してイテレータが必要です。今のところ、データ構造が何であるかはわかりません.DAG（有向非巡回グラフ）かもしれませんが、連結リストかもしれません。だから私はそれをイテレータにラップしたいのですが、今は特定のデータ構造では考えていません。

再帰的なビジターで DAG を訪問する方法は知っていますが、反復子メソッドnext()とhasNext().

イテレーター内で、現在のノード インスタンスを作成し、すべての子に対して for ループを繰り返してから、親に戻ります。「既に訪問済み」フラグが必要です。だから私DagElementはこれらのより多くの属性を持っています:

DagElement parent
boolean alreadyVisited

これはきれいな解決策ではないと思います。

何かアドバイス？

4

1 に答える 1

1

再帰的ヒューリスティックを反復的ヒューリスティックに変換する手っ取り早い方法は、(LIFO) スタックまたは (LILO) キューを使用して、「通っていない道」 (見つかったがまだ通っていない道) を保持することです。この場合、反復子にはスタックまたはキューのインスタンス変数があります。何かのようなもの：

    class DagIterator<T>
    extends Iterator<T> {

        private Stack<DagNode<T>> nodes;

        private DagIterator(Dag<T> dag) {
            nodes.push(dag.getRootNode());
        }

        public boolean hasNext() {
            return ! nodes.isEmpty();      
        }

        public T next() {
            final DagNode node = nodes.pop();
            for (final DagNode child : node.getChildren()) {
                nodes.push(child);
            }
            return node.getValue();
        }

    }

データ構造 (LIFO または LILO)、子がキューに入れられる順序、およびキューに入れられるタイミングに基づいて、訪問順序を微調整します。一部の訪問オーダーでは、(コンストラクターで) すぐに適切な順序でノードのセット全体をキューに入れる必要がある場合があります。

于 2010-11-15T14:38:27.983 に答える