0

これが、HashMapを使用して今これを実装している方法です

private int steps=0;
private LinkedList<MazeCell> breadCrumbs = new LinkedList<MazeCell>();
private HashMap<MazeCell, Boolean> visitedCells = new HashMap<MazeCell, Boolean>();
public int stepsToSolveMaze(MazeCell cell)
{       
    if (visitedCells.get(cell) == null)
    {
        visitedCells.put(cell, true);
        breadCrumbs.push(cell);
    }

私は再帰的アルゴリズムを使用して、迷路の終わりまでのステップ数を見つけています。次の「一歩」を踏み出す前に、自分が踏み出す場所にいないことを確認する必要があります。自分がいた場所を除いて、nullでいっぱいのHashMapよりも優れたデータ構造があるように感じますが、実際には手がかりがありません。このためのより良いデータ構造を知っている人はいますか？

4

4 に答える 4

0

現在のデザインは大丈夫です。セルの数が固定されている場合は、セルを配列に保存し、ビットベクトルを使用して訪問したセルを示すことができます。たとえば、32ビット整数は32セルを表すことができます。

于 2013-03-18T15:14:12.933 に答える
0

の代わりに、 HashSetHashMapを使用する必要があります。コードが読みやすくなります。は。に支えられているため、パフォーマンスは同等です。HashSetHashMap<E,Object>

private int steps=0;
private LinkedList<MazeCell> breadCrumbs = new LinkedList<MazeCell>();
private Set<MazeCell> visitedCells = new HashSet<MazeCell>();
public int stepsToSolveMaze(MazeCell cell)
{       
    if (!visitedCells.contains(cell))
    {
        visitedCells.add(cell);
        breadCrumbs.push(cell);
    }   
}

アンHashSet offers constant time performance for the basic operations.

于 2013-03-18T15:13:01.423 に答える
0

boolean[][]マトリックス全体にaを付けるのはどうですか？

大きすぎる行列を扱っていない場合は、おそらくこのオプションを使用します。

1000x1000はそれほど大きくなく、マトリックス全体が約1 MBのストレージを占有します（実装によって異なります）。

読み取り/書き込みのオーバーヘッドは、ハッシュを使用するよりも少なくする必要があります。ハッシュ関数が悪い場合、ハッシュのパフォーマンスがひどくなる可能性があることに注意することも役立ちます。2Dアレイソリューションには、この欠点はありません。

ストレージをあまり必要としないソリューションはBitSet[]、1000x1000マトリックスの場合は約125KBのストレージになります。

ストレージスペースをさらに削減するために、（実装に応じて）空の行/列があるnull場合はどちらの場合でも（boolean[]またはnullにすることができます）値を持つことができることに注意してください。BitSet

免責事項：上記の数値は単なる推定値であり、いくつかのことを無視しました。

于 2013-03-18T15:36:53.357 に答える
0

素集合

これは、この種のデータ構造を実装するための最も効率的な方法です。

一言で言えば、あなたがすることはあなたの迷路を表す整数の2次元配列を作成することです。配列の各行の列は、迷路のx、y座標になります。座標位置に存在する値は、それが含まれる「セット」を表します。

したがって、あなたの場合、ある場所を訪れたことがある場合は、その場所に1を付けてください。

したがって、座標にアクセスしない場合は0が含まれます。

于 2013-03-18T16:23:42.233 に答える