0

Dijkstra のアルゴリズムを再帰的に記述しようとしています。しかし、私はこれを取得し続けjava.lang.StackOverflowErrorます。

グレースケール値と座標PixelNodeを持つ s を使用します。x,y関数 neighbors は、最大 3PixelNodeを返します。これは、現在のピクセルの 3 ピクセル下にあります。

public PixelNode Dijkstra(PixelNode s, PriorityQueue<PixelNode> leads) {
  s.visited = true;
  if (s.isEndNode) {
    return s;
  }
  ArrayList<PixelNode> nbs = s.neighbors();
  for (PixelNode nb : nbs) {
    if (!nb.visited) {
      float new_distance = s.distance + nb.val();
      if (new_distance < nb.distance) {
        nb.distance = new_distance;
        nb.via = s;
      }
      if (!nb.addedToLeads) {
        nb.addedToLeads=true;
        leads.add(nb);
      } else {
        leads.remove(nb);
        leads.add(nb);
      }
    }
  }
  return Dijkstra(leads.poll(), leads);
}

誰かが私を助けてくれるとしたら、それは大歓迎です！

編集: lead.remove(nb) が機能していません。PixelNode の equals 関数を適切にオーバーライドしませんでした。今、私はそれを適切にオーバーライドしましたが、まだ削除されていません...

編集:再帰の最大深度に達したと思い始めています。画像を本当に小さくトリミングすると、正しいパスが見つかります... 21x19 の画像の場合、374 回の再帰が必要です。おおよそ、画像内のピクセル数。実際の画像は 396x366 です。396x366=144936 回の再帰関数呼び出しが必要だと思います。3257 コールで壊れます。

関数の新しいバージョンは次のとおりです。

public PixelNode dijkstra(PixelNode s, PriorityQueue<PixelNode> leads) {
  s.visited=true;
  if(s.isEndNode) {
    return s;
  }
  ArrayList<PixelNode> nbs = s.neighbors();
  for(PixelNode nb : nbs) {
    if(!nb.visited) {
      float new_distance = s.distance + nb.val();
      if(new_distance < nb.distance) {
        nb.distance = new_distance;
        nb.via = s;
        nb.addedToLeads = true;
        leads.add(nb);
      }
    }
  }
  return dijkstra(leads.poll(), leads);
}
4

1 に答える 1

0

問題を再現するためのソース コードはありませんが、推測する必要があります。

public PixelNode Dijkstra(PixelNode s, PriorityQueue<PixelNode> leads) {
  s.visited = true;
  if (s.isEndNode) {
    return s;
  }
  ArrayList<PixelNode> nbs = s.neighbors();
  for (PixelNode nb : nbs) {
    if (!nb.visited) {
      float new_distance = s.distance + nb.val();
      if (new_distance < nb.distance) {
        if (nb.addedToLeads) {
          // already in leads with higher distance value
          // Note: remove is done before distance update
          leads.remove(nb);
        }
        nb.distance = new_distance;
        nb.via = s;
      } else if (nb.addedToLeads) {
        // already in leads with lower or equal distance value
        continue;
      }
      nb.addedToLeads=true;
      leads.add(nb);
    }
  }
  return Dijkstra(leads.poll(), leads);
}

また、PriorityQueue の Comparator が equals に対して正しい値を返すことを確認してください。

于 2013-10-05T19:03:18.297 に答える