問題タブ [breadth-first-search]

私はこのBFSの宿題の問題を解決しています。私がフォローしているロジックは正しいと思いますが、特定できない実装エラーで立ち往生しています。新しいソリューションを提案するのではなく、このソリューションをデバッグするためのヘルプを探しています。

問題文：

子供には、リモートで制御する2台のロボットがあります。どちらのロボットもNxNチェッカーボード上にあり、チェッカーボードの位置AとBに配置する必要があります。

両方のロボットが同時にリモートコントローラーの影響を受け、同じコマンドが両方の状態に影響します。

リモコンは、両方のロボットを一度に時計回りまたは反時計回りに90度回転させるか、両方のロボットに前進させることしかできません。

例： 左端の画像は初期設定を示しています。右向きの矢印は東向きのロボットで、上向きの矢印は北向きのロボットです。位置AとBはロボットの運命です。

中央の画像は、両方のロボットを1歩前進させた結果を示しています。

右の画像は、ロボットを反時計回りに回転させた結果を示しています。

子供は、ロボットを初期位置から目的地まで移動させるために必要な最小動作数を計算したいと考えています。

ロボットが壁を越えて走るように命じられた場合、ロボットは同じ場所に留まります。

同じ場所に移動するように指示された場合、両方のロボットは元の場所に留まります。

図2は、この特殊なケースを示しています。

両方のロボットが同時に異なる運命に到着する必要があります。

入力： 入力はさまざまなテストケースで構成され、最初の行はinputMatrix（チェッカーボード）のサイズN、2 <= N<=25の整数で始まります。

次のN行はチェッカーボードを表しており、それぞれN文字です。

'。' 空の位置を示します。

N、E、S、またはO（スペイン語でOeste = West）は、ロボットの元の位置と向きを示します。

Dはチェッカーボード内のロボットの運命を示し、「*」は障害物を示します。

N=0の場合で入力が終了します。

input.txt

input.txtの正しい出力：

input2.txt：

input2.txtの「正しい」（？）出力：

私の解決策：

問題： 1）最初のinput.txtファイルで、最初のコースの解決策を見つけるための9つの動き（8である必要がある場合）と、2​​番目のコースの解決策を見つけるための6つの動き（3である必要がある場合）が見つかります。最後の（不可能な）コース構成に対して-1を正しく出力します。

2） 2番目のinput.txtファイルで、教授は最初のコースに-1と-1を出力する必要があると言っていますが、私のプログラムは2番目のケースにはもっともらしい解決策を見つけ、最初のケースには奇妙な解決策を見つけます（これは私が思うところです）より経験豊富なデバッガーが役立つ可能性があります。最初のケースで運命の出力が置き換えられた理由を追跡するのに迷っています）。私の教授が提案した成果は正しいですか？私のアルゴリズムも、46を印刷する必要がある場合に行き詰まっています。

Python には、頂点オブジェクトのディクショナリを持つ Graph クラスがあります。各頂点オブジェクトには、エッジのディクショナリがあります (開始ノード、終了ノード、重みで構成されています...移動コストの数値が割り当てられた別のノードを指している矢印の端を想像してください)。

これらのクラスを使用して、飛行機が都市から都市へと飛行するのにかかる時間をグラフにしています。このグラフから、ダイクストラのアルゴリズムを使用して、2 つのノード間の最短経路 (最速経路) を決定することになっています。また、開始頂点から到達可能なすべての頂点を決定することになっています。

グラフで完全にエッジを追加したり、エッジを削除したり (その結果、ノードを追加したり) することができます。しかし、私の人生では、私が作成したデータ構造を使用して、ダイクストラのアルゴリズムまたは幅優先探索 (到達可能な頂点を決定するため) を実装する簡単な方法を理解できないようです。

これらのアルゴリズムを変更または実装して正しく動作させるために何をする必要があるかを誰かが提案できる場合は、助けていただければ幸いです。これは、私が 1 週間近く、1 日に何時間も取り組んできた宿題であり、この壁を乗り越えることができないようです。繰り返しますが、アドバイスや助けをいただければ幸いです。誰かが私のためにコードを書いてくれるとは思っていませんが、疑似コードが役に立ちます (そしてそれを適用します。ウィキペディアから疑似コードをコピーして貼り付けても、私は既にそこにいるので役に立ちません)。

「グラフの幅優先探索を実行し、グラフのアーティキュレーションポイントを一覧表示する」のように聞こえる、無向グラフで問題が発生します。DFSを使用してアーティキュレーション頂点を見つけるアルゴリズムのみを見つけました。BFSでそれらの頂点を見つける方法はありますか？ありがとうございました。

更新：各ノードを削除してから、残りのグラフでBFSを実行するのはどうですか？すべてのノードをカバーしている場合、削除されたノードはアーティキュレーションポイントではありませんでした。非効率的だとは思いますが、大丈夫だと思います。

二分木で幅優先探索のコードを書こうとしています。すべてのデータをキューに保存しましたが、すべてのノードに移動してすべての子を消費する方法がわかりません。

Cでの私のコードは次のとおりです。

すでにルート データをエンキューしましたが、まだ機能していません。誰かが私の間違いを指摘できますか?

BFSを使用して検索を実装したい。アルゴリズムによると、FIFO効果を得るにはキューを使用する必要があります。クリス・オカサキの純粋関数型データ構造の本を読んで、キューを作成する方法を見つけました（F＃を使用して作成しました）：

これをBFSに実装する方法を知っている人はいますか？

そして私はリストからツリーを作るためにこのコードを持っています：

（これら2つのコードを組み合わせたい）

コレクションとデキューを含むBFS コードに出くわしましたが、あまり理解できませんでした。ここの pythonistas の何人かが n00b を助けることができることを願っています。

質問:

1) |= 演算子はビット演算に関連しているようです - BFS とどのように関連しているのかわかりませんが、何かヒントはありますか?

2) popleft()は、私が理解していることから 1 つの値のみを返す必要があるため、ここで親と n を返す方法は?

3)訪問した一連のノードは新しいですか? ノードが必要な場合は、それらをリストに追加し続けますか?

前もって感謝します。

クレイグ

こんにちは私はReflectionに関連する何かをしています、私は私のコードの何が悪いのか理解していません。コードをクリーンアップしようとしましたが、最初のコードはインスタンス値を更新しません。デバッガーをステップスルーすると、「newobj」から正しい結果が表示されますが、「次の」参照は次の結果として失われます。インスタンス値を更新していません。私が行った唯一の変更は、キューに「this」を追加することです。私にとっては違いはありません。誰かがこの背後にある理由を説明できますか？

その他のサポートコード

人々のグループ[たとえば1874人]がいて、全員が世界のさまざまな会社[たとえば236人]を代表しています。私の仕事は、一人一人がどの会社で働いているかを最もよく特定することです。秘訣は、「どこで働いているのか」と単純に聞いて答えを出すことはできないということですが、私が持っているのは、いくつかの質問（たとえば290の質問）と従業員に期待すべき正確な回答を含む質問票です。各社の 答えが同じ会社もあるので、最終的には、どの会社に勤めているのか正確にわからなくても、絞り込んで、その会社に勤めなければならないと言うことができるはずです。

複数の値のマップと他のいくつかのデータ構造を使用して、1つの質問[クエリ]で識別できるすべての会社を特定するところまで行きました。これらのクエリを使用してツリーデータ構造のルートを表すには、他のクエリ/質問をブランチとして使用して残りのツリーを構築し、残りを識別する必要があります。

アドバイス/ヘルプ/提案はありますか？

Web クローラーに関する論文を書く必要があり、この Web クローラーは幅優先でリンクを探索します。

クローラーが探索する方法を示す写真を作成しました。これは正しい幅優先探索ですか?:

（グラフのサイズ）+一定量のメモリのみを使用して、つまり、どのノードがすでにアクセスされているかを記録せずに、幅優先探索を実行することは可能ですか？