0

このクラスには、次の2つの値を保持する必要があります。

public class Coord {

    public int x; 
    public int y;

    public Coord(int x, int y) { 
        this.x = x; 
        this.y = y; 
    }
}

深さ優先探索アルゴリズムで使用しようとしています。

x = this.move_to_x;
y = this.move_to_y;

Coord stack = new Coord(0, 0);

Stack<Coord> start = new Stack<Coord>();
Stack<Coord> visited = new Stack<Coord>();

start.push(stack);
visited.push(stack);

while (!start.empty()) {
    Coord tmp = (Coord)start.pop();

    int j,k;

    j = tmp.x;
    k = tmp.y;

    // there is only 8 possible ways to go (the neighbors)
    for (int a = -1; a < 2; a++) {
        tmp.x = j + a;

        for (int b = -1; b < 2; b++) {
            if (a == 0 && b == 0) {
                continue;
            }

            tmp.y = k + b;

            if (tmp.x < 0 || tmp.y < 0) {
                continue;
            }

            if (tmp.x > 5 || tmp.y > 5) {
                continue;
            }

            if (tmp.x == x && tmp.y == y) {
                System.out.println("end!");
                return;
            }

            Coord push = new Coord(tmp.x, tmp.y);

            System.out.println("visited: " + visited);

            if (visited.search(push) == -1) {
                System.out.println("added x " + push.x + " y " + push.y
                        + " " + visited.search(push));

                start.push(push);
                visited.push(push);
            } else {
                System.out.println("visited x " + tmp.x + " y " + tmp.y
                        + " index  " + visited.search(push));
            }
        }
    }
}

問題は、visited.searchメソッドが常にを返すこと-1です。ログは次のとおりです。

visited: [Agent.ExampleAgent.Coord@1af6a711]
added x 0 y 1 -1
visited: [Agent.ExampleAgent.Coord@1af6a711, Agent.ExampleAgent.Coord@1c727896]
added x 1 y 0 -1
visited: [Agent.ExampleAgent.Coord@1af6a711, Agent.ExampleAgent.Coord@1c727896, Agent.ExampleAgent.Coord@5fbd8c6e]
added x 1 y 1 -1
visited: [Agent.ExampleAgent.Coord@1af6a711, Agent.ExampleAgent.Coord@1c727896, Agent.ExampleAgent.Coord@5fbd8c6e, Agent.ExampleAgent.Coord@427a8ba4]
added x 0 y 0 -1
visited: [Agent.ExampleAgent.Coord@1af6a711, Agent.ExampleAgent.Coord@1c727896, Agent.ExampleAgent.Coord@5fbd8c6e, Agent.ExampleAgent.Coord@427a8ba4, Agent.ExampleAgent.Coord@262f6be5]
added x 0 y 1 -1
visited: [Agent.ExampleAgent.Coord@1af6a711, Agent.ExampleAgent.Coord@1c727896, Agent.ExampleAgent.Coord@5fbd8c6e, Agent.ExampleAgent.Coord@427a8ba4, Agent.ExampleAgent.Coord@262f6be5, Agent.ExampleAgent.Coord@199d4a86]

訪問先スタックに追加される最初の要素はですが(0,1)、検索されると(0,1)、後でメソッドはを返すことに注意してください-1。

4

2 に答える 2

1

パラメータのxとyがオブジェクトのxとyの値と等しい場合equals()に返されるように、メソッドをオーバーライドする必要があります。true

hashCode()また、メソッドと「一致」するようにメソッドをオーバーライドする必要がありますequals()。

于 2013-03-08T02:49:04.340 に答える
1

（チャットディスカッションでの進捗状況の概要を示す回答を投稿すると考えられます）

Coordクラスの次の状態を想定します。

public class Coord {

    public int x; 
    public int y;

    public Coord(int x, int y) { 
        this.x = x; 
        this.y = y; 
    }

    @Override
    public boolean equals(Object obj){

        if (obj == null)
            return false;
        if (obj.getClass() != Coord.class)
            return false;
        if (obj == this)
            return true;

        Coord a = (Coord)obj;
        return (a.x == this.x && a.y == this.y);
    }

    @Override
    public int hashCode() {
        return x*17 + y*31;
    }

    @Override
    public String toString() {
        return "("+x+", "+y+")";
    }
}

...実装：

  • equals()Javadocによると、これはスタック検索で使用されるものです。
  • hashCode()ベストプラクティスとして、付随するequals()
  • toString()より明確な診断出力のために

アイデアは、残りのコードから分離してスタック検索の機能をテストすることです。スタック検索が適切に機能することを証明できれば、問題は他の場所にあります。

スタック検索が機能することを証明するには、次のようなテストクラスを使用します。

public class CoordTest {

public static void main(String[] args) {
    System.out.println("Running tests...");

    System.out.println("Testing: equals");
    Coord c1a = new Coord(2,3);
    Coord c1b = new Coord(2,3);
    check(c1a.equals(c1b));

    System.out.println("Testing: not equals"); 
    Coord c2a = new Coord(2,3);
    Coord c2b = new Coord(6,8);
    Coord c2c = new Coord(2,8); 
    Coord c2d = new Coord(6,3);
    check(!c2a.equals(c2b));
    check(!c2a.equals(c2c));
    check(!c2a.equals(c2d));

    System.out.println("Testing: not found in empty stack"); 
    Stack<Coord> stack1 = new Stack<Coord>();
    int result1 = stack1.search(c1a);
    check(result1 == -1);

    System.out.println("Testing: not found in non-empty stack"); 
    Stack<Coord> stack2 = new Stack<Coord>();
    stack2.push(new Coord(4,5));
    stack2.push(new Coord(6,7));
    int result2 = stack2.search(c1a);
    check(result2 == -1);

    System.out.println("Testing: found in non-empty stack"); 
    Stack<Coord> stack3 = new Stack<Coord>();
    stack3.push(new Coord(4,5));
    stack3.push(new Coord(3,1));
    stack3.push(new Coord(6,7));        
    int result3 = stack3.search(new Coord(3,1));
    check(result3 == 2);        

    System.out.println("All tests completed successfully.");
}

private static void check(boolean condition) {
    if (!condition) {
        throw new RuntimeException("Condition failed!");
    }
}

}

出力：

Running tests...
Testing: equals
Testing: not equals
Testing: not found in empty stack
Testing: not found in non-empty stack
Testing: found in non-empty stack
All tests completed successfully.
于 2013-03-08T20:14:59.070 に答える