algorithm - 「カバーオール」パスの開始位置と終了位置を見つけて接続します

Question

2dArray の形状は次のようになります (たとえば):

点 A と B (場所はわかりません) と、形状全体をカバーするパス (各セルを通過する必要があります) が存在する必要があることがわかっています。ポイントAとB、そして「カバーオール」パスを決定する方法について助けてもらえますか? そのような場合には、いくつかの既知のアルゴリズムがあるかもしれません。または、疑似コードアルゴリズムの助けになります。前もって感謝します。

Answer 1

のリンクをチェックnhahdthして、一般的な問題が np-hard であることを確認してください。この mathoverflow の記事では、穴のあるグリッド上のグラフの結果を確立する論文を引用しています。より多くの制約を考え出さない限り、ブルート フォースを使用するよりも大幅にうまくいくことはありません。

基になるグリッド セル グラフで次数 1 の頂点を検索することで、開始ノードと終了ノードの少なくとも 1 つを特定できる場合があります。