検索に関する質問です.

ツリーの遍歴と同様に、図遍歴操作の定義式は、図中の各ノードにアクセスし、各ノードは1回のみアクセスされる.図の遍歴法は主に2種類ある:1つは深さ優先(DFS)であり,もう1つは広さ優先(BFS)である.
図の遍歴アルゴリズム設計は3つの問題を考慮しなければならない:(1)図の特徴は首尾の区別がないので、アルゴリズムのパラメータはアクセスの最初のノードを指定しなければならない.(2)図の遍歴経路は回路であり、デッドサイクルをもたらす可能性があるため、アルゴリズム設計は遍歴経路に現れるデッドサイクル問題を考慮しなければならない.(3)1つのノードが複数のノードと隣接する接続点である可能性があり、1つのノードのすべての隣接ノードが何らかの順序でアクセスされるようにする.
DFS(図の深さ優先アルゴリズム)は、遍歴時の深さ優先アルゴリズムであり、すなわち、図のすべての隣接ノードにおいて、現在のノードへのアクセスが完了するたびに、現在のノードに最初にアクセスする最初の隣接ノードであり、これは再帰アルゴリズムである.
連通図の深さ優先アルゴリズムは、次のとおりです.
a、ノードvにアクセスし、ノードvをアクセスとしてマークする.
b、ノードvの最初の隣接ノードwを検索する.
c、ノードvの隣接ノードwが存在する場合、実行を継続し、そうでなければアルゴリズムは終了する.
d、ノードwがまだアクセスされていない場合、ノードwに再帰的にアクセスする.
e、ノードvのw隣接ノードの次の隣接ノードwを検索し、ステップcに進む.
BFS(図の広さ優先遍歴アルゴリズム)は階層的探索のプロセスであり、図の広さ探索アルゴリズムは、これらのノードの隣接ノードに順次アクセスするために、アクセスしたノード順序を維持するためにキューを必要とする.連通図の広さ優先アルゴリズムは、次のとおりです.
(1)初期ノードvにアクセスし、ノードvをアクセス済みとマークする.
(2)ノードvがキューに入る;
(3)キューが空でない場合は続行し、そうでない場合はアルゴリズムが終了する.
(4)キューから取り出したヘッダノードu;
(5)ノードuの最初の隣接ノードwを検索する.
(6)ノードuの隣接ノードwが存在しない場合は、ステップ(3)に移行し、そうでない場合は、以下のステップをループ実行する.
(6.1)ノードwがまだアクセスされていない場合、アクセスwはアクセス済みとマークされる.
(6.2)ノードwがキューに入る.
(6.3)ノードuのw隣接ノードの次の隣接ノードを検索し、ステップ(6)に進む.
 
 
poj 3278は典型的な広さ優先検索問題である.
aとb点の横座標を与えて、a,bの最小行動回数を求め、その中で毎回行動するのは以下の2つの状況の1つにすぎない.
(1)左または右に一歩移動する、すなわち横座標に1を加算または1を減算する.
(2)横座標が元の2倍になる.
タイトルから与えられたデータ5 17は,このように行動5->10->9->18->17を行うことができるので,4ステップでbに到達できる.
 
 
最小行動回数を求めるのでBFSでSTLの中のキューを呼び出して実現できる.各デキューヘッダ要素は、b点に到達すると、ステップを出力して探索を終了し、そうでなければ、行動ステップ+1と、それぞれ改点の横座標+1,-1と、×2操作後、解が見つかるまでキューに押し込みます.なお、位置の横座標がb点を超えた場合は右に進むべきであるため、その横座標に対しては−1操作のみであるべきであり、横座標が0である特殊な場合にも注意し、ここでは+1走行のみを行うべきである.最初はタグ配列を小さくしていたので気づかなかった×2が100000を超える場合があるかもしれませんが、コミット時に一度REし、配列をACに変更しました.
コードは次のとおりです.

#include <iostream>
#include <queue>
using namespace std;
const int  Max=100005;

int main()
{
	queue<int> a;
	int n,k;
	cin>>n>>k;
	bool visit[Max];//       
	memset(visit,false,sizeof(visit));
	bool fine=false;
	int step=0;//    
	visit[n]=true;
	a.push(n);
	if (n!=k)
	{
		while (!a.empty()&&!fine)
		{
			int t=a.size();
			step++;
			while (t--)
			{
				int pos,npos[3];
				pos=a.front();
				a.pop();
				npos[0]=pos+1;
				npos[1]=pos-1;
				npos[2]=pos*2;//    
				for (int i=0;i<3;i++)
				{
					if (npos[i]==k)
					{
						fine=true;
						break;
					}
					if (npos[i]>=0&&npos[i]<=10000&&!visit[npos[i]])
					{
						visit[npos[i]]=true;
						a.push(npos[i]);//      
					}
				}

			}
		}
	}
	cout<<step<<endl;
	return 0;
}

検索に関するテーマは続きますが・・・