擬似コード
擬似コード
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/05/02 06:29 UTC 版)
「トライ (データ構造)」の記事における「擬似コード」の解説
以下の擬似コードは与えられた文字列がトライ木にあるかどうかを判定する汎用のアルゴリズムを示したものである。ここで、children は子ノード群の配列であり、terminal ノードとは格納された単語に対応するノードを意味する。 function find(node, key) { if (key is an empty string) { # 基本ケース。キーが空文字列の場合 return is node terminal? } else { # 再帰ケース c = first character in key # キーが空でないので、その1文字目を取り出す tail = key minus the first character # 1文字目を除いた文字列 child = node.children[c] # 文字コードが配列キーとなる if (child is null) { # 子がないので再帰できないがキーは空になっていない return false } else { return find(child, tail) } }}
※この「擬似コード」の解説は、「トライ (データ構造)」の解説の一部です。
「擬似コード」を含む「トライ (データ構造)」の記事については、「トライ (データ構造)」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2012/12/11 12:50 UTC 版)
「Winged-Edgeデータ構造」の記事における「擬似コード」の解説
ここにWinged-Edgeを表現するのに適したデータ構造を載せる。"WE"という略称は"Winged Edge"を表わす。 class WE_Edge { WE_Vertex vert1, vert2; WE_Face aFace, bFace; WE_Edge aPrev, aNext, bPrev, bNext; // 時計回り WE_EdgeDataObject data;}class WE_Vertex { List
※この「擬似コード」の解説は、「Winged-Edgeデータ構造」の解説の一部です。
「擬似コード」を含む「Winged-Edgeデータ構造」の記事については、「Winged-Edgeデータ構造」の概要を参照ください。
擬似コード（木構造の場合）
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/11/08 04:34 UTC 版)
「深さ制限探索」の記事における「擬似コード（木構造の場合）」の解説
EXPAND(node) ノード展開関数：探索候補の集合を返す。 IS_GOAL(node) ノード探索終了判定関数：ゴールに到達したかどうか。 function DLS(node, depth) if (IS_GOAL(node)) then return node if (depth > 0) then for each (child in EXPAND(node)) found = DLS(child, depth - 1) if (found != NULL) then return found return NULL
※この「擬似コード（木構造の場合）」の解説は、「深さ制限探索」の解説の一部です。
「擬似コード（木構造の場合）」を含む「深さ制限探索」の記事については、「深さ制限探索」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/12/06 02:42 UTC 版)
「反復深化深さ優先探索」の記事における「擬似コード」の解説
EXPAND(node) ノード展開関数：探索候補の集合を返す。 IS_GOAL(node) ノード探索終了判定関数：ゴールに到達したかどうか。 DLS は深さ制限探索。 function IDDFS(node) for (depth = 0; ; depth++) found = DLS(node, depth) if (found != NULL) then return found function DLS(node, depth) if (IS_GOAL(node)) then return node if (depth > 0) then for each (child in EXPAND(node)) found = DLS(child, depth - 1) if (found != NULL) then return found return NULL
※この「擬似コード」の解説は、「反復深化深さ優先探索」の解説の一部です。
「擬似コード」を含む「反復深化深さ優先探索」の記事については、「反復深化深さ優先探索」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/06/13 18:04 UTC 版)
以下にノームソートのPascalベースの擬似コードを示す。 procedure gnomeSort(a[0..size-1]); begin i := 1; while i < size do if a[i-1] <= a[i] then // 降順にソートする場合は>= で比較する begin i := i + 1; // 正順なので次に進む end else begin swap(a[i-1], a[i]); // 逆順なので交換する i := i - 1; // 交換したので前に戻る if i = 0 then i := i + 1; // 端なので次に進む end end; 実施例として4、2、7、3という並びを昇順にソートする場合にループ内で起きていることを示す。 4273 （初期状態） 4273 （逆順なので交換する） 2473 （交換したので前に戻る） 2473 （端なので次に進む） 2473 （正順なので次に進む） 2473 （正順なので次に進む） 2473 （逆順なので交換する） 2437 （交換したので前に戻る） 2437 （逆順なので交換する） 2347 （交換したので前に戻る） 2347 （正順なので次に進む） 2347 （正順なので次に進む） 2347 （正順なので次に進む） 2347（最後まで調べたので終了）
※この「擬似コード」の解説は、「ノームソート」の解説の一部です。
「擬似コード」を含む「ノームソート」の記事については、「ノームソート」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/01/31 05:26 UTC 版)
「テスト・アンド・セット」の記事における「擬似コード」の解説
ブーリアン値によるテスト・アンド・セット命令は以下の関数のように動作する。この関数全体が必ずアトミックに実行される。つまり、他のプロセスがこの関数の実行中に割り込むことは出来ず、関数実行途中の状態を観測することはできない。これはテスト・アンド・セットがどのように働くのかを示すものであって、ハードウェアのサポートなしにアトミック性は実現できないし、このような単純な関数だけで正しく動作することはない。 function TestAndSet(boolean lock) { boolean initial = lock lock = true return initial} （上記コード中でlockは参照型であることに注意） ミューテックスはこれを利用すると以下のように実装できる。 boolean lock = falsefunction Critical(){ while TestAndSet(lock) skip //ロックが獲得されていたらスピンする。 critical section //一度にひとつのプロセスだけがここに到達できる。 lock = false //クリティカルセクションが終了したらロックを解放する。} この関数は複数のプロセスから呼び出すことができるが、クリティカルセクションに入ることができるのは一度にひとつのプロセスだけであることが保証される。この方式は実際のマルチプロセッサマシンでは効率的ではない（定期的にロックを読み書きするため、キャッシュコヒーレンシ問題が発生する）。テスト・アンド・テストアンドセット（後述）がより効率的な解決策となる。ここで示した例はスピンロックであり、whileループでロック獲得をスピンしながら待つようになっている。
※この「擬似コード」の解説は、「テスト・アンド・セット」の解説の一部です。
「擬似コード」を含む「テスト・アンド・セット」の記事については、「テスト・アンド・セット」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/09/03 13:47 UTC 版)
大文字で書かれた関数は以下の通り。全て引数にノードをとる。 EVAL(node) ノード評価関数：ヒューリスティクスとしてノードからゴールまでの近さの数値を返す関数。EVAL(node1, node2) という形で node1 と node2 のどちらがゴールに近いかを判定する関数でも良い。 EXPAND(node) ノード展開関数：探索候補の集合を返す。 IS_GOAL(node) ノード探索終了判定関数：ゴールに到達したかどうか。 function 最良優先探索(startNode) visited = 訪問済みノードを管理する集合 queue = ノード評価関数(EVAL)で自動的にソートするノードの優先度付きキュー startNode を visited と queue に追加 while queue が空ではない do node = queue の先頭から取り出す if IS_GOAL(node) then return node for each child in EXPAND(node) do if child が visited に含まれない then child を visited と queue に追加 return 探索失敗 A* の論文では、上記の visited を CLOSED、queue を OPEN と呼ぶ。
※この「擬似コード」の解説は、「最良優先探索」の解説の一部です。
「擬似コード」を含む「最良優先探索」の記事については、「最良優先探索」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/09/03 13:46 UTC 版)
大文字で書かれた関数は以下の通り。全て引数にノードをとる。 COST(node1, node2) 辺のコスト関数：node1 から node2 への辺の重み。 EXPAND(node) ノード展開関数：探索候補の集合を返す。 IS_GOAL(node) ノード探索終了判定関数：ゴールに到達したかどうか。 function 均一コスト探索(startNode) visited = 訪問済みノードを管理する集合 queue = ノード評価値で自動的にソートするノードの優先度付きキュー startNode の評価値 = 0 startNode を visited と queue に追加 while (queue が空ではない) node = queue の先頭から取り出す if (IS_GOAL(node)) then return node for each (child in EXPAND(node)) evalValue = node の評価値 + COST(node, child) if (child が visited に含まれない) then child の評価値 = evalValue child を queue に追加 else if (evalValue < child の評価値) then child の評価値 = evalValue child を queue から削除して追加し直す return 探索失敗 表 話 編 歴 アルゴリズムソート 比較ソート バブルソート 選択ソート 挿入ソート シェルソート クイックソート マージソート ヒープソート シェーカーソート コムソート ノームソート 図書館ソート イントロソート 奇偶転置ソート 線形時間ソート 鳩の巣ソート 基数ソート バケットソート 並行ソート ソーティングネットワーク バッチャー奇偶マージソート シェアソート 非効率的 ボゴソート ストゥージソート グラフ トポロジカルソート 探索 リスト 線型探索 二分探索 木・グラフ 幅優先探索最良優先探索 均一コスト探索 A* 深さ優先探索反復深化深さ優先探索 深さ制限探索 双方向探索 分枝限定法 文字列 クヌース–モリス–プラット法 ボイヤー-ムーア法 エイホ–コラシック法 ラビン-カープ法 Bitap法 最短経路問題 ダイクストラ法 ベルマン–フォード法 ワーシャル–フロイド法 最小全域木 プリム法 クラスカル法 最大フロー問題最小カット問題 フォード・ファルカーソン法 エドモンズ・カープ法 線型計画問題 シンプレックス法 カーマーカー法 順序統計量 選択アルゴリズム 中央値の中央値 種類 近似アルゴリズム 乱択アルゴリズム その他 分割統治法 動的計画法 貪欲法 カテゴリ
※この「擬似コード」の解説は、「均一コスト探索」の解説の一部です。
「擬似コード」を含む「均一コスト探索」の記事については、「均一コスト探索」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2017/09/21 06:16 UTC 版)
下記は2次元の場合の擬似コード。S は凸包を計算する点の配列。あらかじめ凸包の頂点に来ないことが確実な点は除去しておくと計算量が減る。L は可変長配列で、ここに凸包の頂点の座標が入る。A, B, C は点。|AB| は AB の距離。2次元の外積は x 1 y 2 − x 2 y 1 {\displaystyle x_{1}y_{2}-x_{2}y_{1}} で計算する。 A = S の内、最もy座標が小さい点の集合から、その中で最もx座標が小さい点do { L に A を追加 B = S[0] for i = 1 to S の大きさ - 1 { C = S[i] if (B == A) { B = C } else { v = AB と AC の外積 if (v > 0 または (v == 0 かつ |AC| > |AB|)) { B = C } } } A = B} while (A != L[0])
※この「擬似コード」の解説は、「ギフト包装法」の解説の一部です。
「擬似コード」を含む「ギフト包装法」の記事については、「ギフト包装法」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/10/07 04:57 UTC 版)
以下は、Stout-Warren の論文で示された、基本的なDSWアルゴリズムの擬似コードである。3 つのサブルーチンと 1 つのメインルーチンからなる。メインルーチンは以下で与えられる。 「擬似根ノード」となるノードを作成し、その右の子を木の実際の根にする。 引数として擬似根ノードを与えて tree-to-vine を呼ぶ。 擬似根ノードおよび木のサイズ(要素数)で vine-to-tree を呼ぶ。 木の実際の根を擬似根ノードの右の子に等しくする。 擬似根ノードを破棄する。 サブルーチンは以下のように定義される。 routine tree-to-vine(root) // Convert tree to a "vine", i.e., a sorted linked list, // using the right pointers to point to the next node in the list tail ← root rest ← tail.right while rest ≠ nil if rest.left = nil tail ← rest rest ← rest.right else temp ← rest.left rest.left ← temp.right temp.right ← rest rest ← temp tail.right ← temp routine vine-to-tree(root, size) leaves ← size + 1 − 2⌊log2(size + 1))⌋ compress(root, leaves) size ← size − leaves while size > 1 compress(root, ⌊size / 2⌋) size ← ⌊size / 2⌋ routine compress(root, count) scanner ← root for i ← 1 to count child ← scanner.right scanner.right ← child.right scanner ← scanner.right child.right ← scanner.left scanner.left ← child
※この「擬似コード」の解説は、「DSWアルゴリズム」の解説の一部です。
「擬似コード」を含む「DSWアルゴリズム」の記事については、「DSWアルゴリズム」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/04/30 15:36 UTC 版)
ダイクストラ法の擬似コードは以下の通りである。 Q {\displaystyle Q} は頂点の集合（もしくは優先度付きキュー）。 u {\displaystyle u} , v {\displaystyle v} は頂点。 d ( v ) {\displaystyle d(v)} はスタートとなる頂点からの最短経路の長さ。 prev ( v ) {\displaystyle \operatorname {prev} (v)} は最短経路をたどる際の前の頂点。 グラフ G = ( V , E ) {\displaystyle G=(V,E)} 、スタートとなる頂点 s {\displaystyle s} 、および u {\displaystyle u} から v {\displaystyle v} への辺の長さ length ( u , v ) {\displaystyle {\text{length}}(u,v)} を入力として受け取る// 初期化 各頂点 v ∈ V {\displaystyle v\in V} に対し、 d ( v ) ← ( v = s {\displaystyle d(v)\leftarrow (v=s} ならば 0 {\displaystyle 0} 、それ以外は ∞ ) {\displaystyle \infty )} 各頂点 v ∈ V {\displaystyle v\in V} に対し、 prev ( v ) ← {\displaystyle \operatorname {prev} (v)\leftarrow } 「無し」 Q {\displaystyle Q} に V {\displaystyle V} の頂点を全て追加// 本計算while ( Q {\displaystyle Q} が空ではない ) u ← Q {\displaystyle u\leftarrow Q} から d ( u ) {\displaystyle d(u)} が最小である頂点を取り除く for each ( u {\displaystyle u} からの辺がある各頂点 v ∈ V {\displaystyle v\in V} ) if ( d ( v ) > d ( u ) + length ( u , v ) {\displaystyle d(v)>d(u)+{\text{length}}(u,v)} ) d ( v ) ← d ( u ) + length ( u , v ) {\displaystyle d(v)\leftarrow d(u)+{\text{length}}(u,v)} prev ( v ) ← u {\displaystyle \operatorname {prev} (v)\leftarrow u} 「 u ← Q {\displaystyle u\leftarrow Q} から d ( u ) {\displaystyle d(u)} が最小である頂点を取り除く」の部分は、オリジナルは単純に集合内を探索するアルゴリズムだが、 Q {\displaystyle Q} を優先度付きキュー（フィボナッチヒープ）にすることで、より計算量が減る。ただしその場合、 Q {\displaystyle Q} に関する部分を少し変更する必要がある。下記は優先度付きキューを用いたことを想定し上記を書き換えたダイクストラ法の擬似コードである。 // 初期化 for ( v ← V {\displaystyle v\leftarrow V} ) d ( v ) ← ( v = s {\displaystyle d(v)\leftarrow (v=s} ならば 0 {\displaystyle 0} 、それ以外は ∞ ) {\displaystyle \infty )} p r e v ( v ) ← {\displaystyle prev(v)\leftarrow } 「無し」 Q ( v ) ← d ( v ) {\displaystyle Q(v)\leftarrow d(v)} // 本計算while ( Q {\displaystyle Q} が空集合ではない ) Q {\displaystyle Q} から Q ( u ) {\displaystyle Q(u)} が最小である頂点 u {\displaystyle u} を取り出す for each ( u {\displaystyle u} からの辺がある各 v ∈ V {\displaystyle v\in V} ) a l t ← d ( u ) + length ( u , v ) {\displaystyle alt\leftarrow d(u)+{\text{length}}(u,v)} if ( d ( v ) > a l t {\displaystyle d(v)>alt} ) d ( v ) ← a l t {\displaystyle d(v)\leftarrow alt} p r e v ( v ) ← u {\displaystyle prev(v)\leftarrow u} Q ( v ) ← a l t {\displaystyle Q(v)\leftarrow alt} 「for each ( u {\displaystyle u} からの辺がある各頂点 v ∈ V {\displaystyle v\in V} )」の部分は「for each ( u {\displaystyle u} からの辺がある各頂点 v ∈ Q {\displaystyle v\in Q} )」でも同じ結果が得られるが、 Q ⊂ V {\displaystyle Q\subset V} ではあるものの、逆に計算量が増えてしまう場合もあり得ることに注意。 GCC の C++ の priority_queue はペアリングヒープを使用しているため、これを使うとフィボナッチヒープと同等の計算量のコードが簡単に実装できる。
※この「擬似コード」の解説は、「ダイクストラ法」の解説の一部です。
「擬似コード」を含む「ダイクストラ法」の記事については、「ダイクストラ法」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/25 05:54 UTC 版)
proc rebalance(A, begin, end) r ← end w ← end * 2 while r >= begin A[w+1] ← gap A[w] ← A[r] r ← r - 1 w ← w - 2 proc sort(A) n ← length(A) S ← new array of n gaps for i ← 1 to floor(log2(n) + 1) for j ← 2^i to 2^(i+1) ins ← binarysearch(S, 2^(i-1)) insert A[j] at S[ins] ここで binarysearch(A, k) は配列 A の最初の k 個の要素に二分探索を適用する。ただし隙間は無視する。挿入は要素が詰まったところより隙間を優先する。
※この「擬似コード」の解説は、「図書館ソート」の解説の一部です。
「擬似コード」を含む「図書館ソート」の記事については、「図書館ソート」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/10 17:55 UTC 版)
1 function Kruskal(G) 2 for each vertex v in G do 3 Define an elementary cluster C(v) ← {v}. 4 Initialize a priority queue Q to contain all edges in G, using the weights as keys. 5 Define a tree T ← Ø //T は最終的に最小全域木の辺を含む。 6 // n は全頂点数 7 while T has fewer than n-1 edges do 8 // 辺 u,v は v にとって重みが最小の経路である。 9 (u,v) ← Q.removeMin()10 // T に閉路が含まれないようにする。T に既に u と v を結ぶ経路がない場合のみ u,v を追加する。11 // つまり、u と v が違うクラスター（木）に属する場合のみ u,v を追加する。13 Let C(v) be the cluster containing v, and let C(u) be the cluster containing u.14 if C(v) ≠ C(u) then15 Add edge (v,u) to T.16 Merge C(v) and C(u) into one cluster, that is, union C(v) and C(u).17 return tree T
※この「擬似コード」の解説は、「クラスカル法」の解説の一部です。
「擬似コード」を含む「クラスカル法」の記事については、「クラスカル法」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/09/18 15:27 UTC 版)
分割統治法を擬似コードによって表現すると、以下のような再帰呼出しを使ったものとなる。また、分割統治法になっている何らかのアルゴリズムを実装すると、その基本的な骨組みがこのようになる。 function conquer(x) is if xは簡単にconquerできる then return conquerの結果 else (x1, x2, ...) := divide(x) // 複数の小さな副問題に分割 (y1, y2, ...) := (conquer(x1), conquer(x2), ...) // 再帰 return synthesize(y1, y2, ...) // 各副問題の解を合成（最大値を選ぶ、等） 具体的なアルゴリズムのサンプルとしては、マージソートの記事などを参照。
※この「擬似コード」の解説は、「分割統治法」の解説の一部です。
「擬似コード」を含む「分割統治法」の記事については、「分割統治法」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/07/20 15:01 UTC 版)
v は頂点。 function 幅優先探索(v) Q ← 空のキュー v に訪問済みの印を付ける v を Q に追加 while Q が空ではない do v ← Q から取り出す v を処理する for each v に接続している頂点 i do if i が未訪問 then i に訪問済みの印を付ける i を Q に追加
※この「擬似コード」の解説は、「幅優先探索」の解説の一部です。
「擬似コード」を含む「幅優先探索」の記事については、「幅優先探索」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 07:59 UTC 版)
擬似コードを以下に示す。この擬似コードでは EVAL(node) の極大値を探索している。 EVAL(node) node の評価値を返す関数 NEIGHBORS(node) node の近傍の集合を返す関数 bestNode 探索した中での最良解 function 山登り法(startNode) bestNode = startNode bestEval = EVAL(bestNode) 無限ループ nextNode = NULL nextEval = 負の無限大 for each (x in NEIGHBORS(currentNode)) if (nextEval < EVAL(x)) nextEval = EVAL(x) nextNode = x if (nextEval <= bestEval) return bestNode bestNode = nextNode
※この「擬似コード」の解説は、「山登り法」の解説の一部です。
「擬似コード」を含む「山登り法」の記事については、「山登り法」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/12/10 07:49 UTC 版)
以下の擬似コードは、焼きなまし法を実装したもので、これまで述べたように、状態 startState から開始して maxIter を上限としてステップを繰り返し、エネルギー状態が goalE 以下になる解が見つかるまで動作する。 EVAL(state) 状態 state の評価値（エネルギー状態）。 NEIGHBOUR(state) 状態 state の近傍をランダムに1つ生成する。 TEMPERATURE(r) 焼きなましスケジュール。使用すべき温度を返す。ここではある定数 α {\displaystyle \alpha } のべき乗としている。 0 < α < 1 {\displaystyle 0<\alpha <1} 。 PROBABILITY(e1, e2, t) 温度 t の元 e1 から e2 へ遷移する確率。 random() 0以上1以下の乱数を返す。 function 焼きなまし法(startState, maxIter, goalE) state = startState e = EVAL(state) bestState = state bestE = e for (iter = 0; iter < maxIter; iter++) nextState = NEIGHBOUR(state) nextE = EVAL(nextState) if nextE < bestE then bestState = nextState bestE = nextE if bestE <= goalE then return bestState if random() <= PROBABILITY(e, nextE, TEMPERATURE(iter / maxIter)) then state=nextState e=nextE return bestState function PROBABILITY(e1, e2, t) if e1>= e2 then return 1 else return e e 1 − e 2 t {\displaystyle e^{\frac {e1-e2}{t}}} function TEMPERATURE(r) return α r {\displaystyle \alpha ^{r}}
※この「擬似コード」の解説は、「焼きなまし法」の解説の一部です。
「擬似コード」を含む「焼きなまし法」の記事については、「焼きなまし法」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/25 06:33 UTC 版)
アルファ・ベータ法の擬似コードを以下に示す。alphabeta関数がアルゴリズムの実装であり、minimax関数はミニマックス法とインタフェースを揃えるためのラッパーである。 function minimax(node, depth) return alphabeta(node, depth, -∞, +∞)function alphabeta(node, depth, α, β) if node が終端ノード or depth = 0 return node の評価値 if node が自分のノード foreach child of node α = max(α, alphabeta(child, depth-1, α, β)) if α ≥ β break // βカット return α else node が対戦者のノード foreach child of node β := min(β, alphabeta(child, depth-1, α, β)) if α ≥ β break // αカット return β αとβが表しているのは関心のある値の範囲である。例えば max(min(...), min(...), ..., min(...)) の値を調べるときに、最初の min の値が3だったとすると、3以下の値は max により選ばれることはなくなる。つまり関心の下限(=α)が3となる。そして2つめの min の中に3以下の値が現れればminの値は必ず3以下となるが、その値には興味がないので、3以下の値が現れた時点で探索をやめる(カット)。同じようにβは関心の上限を表し、max の中で値が関心の上限を超えると分かるとカットとなる。 上記のalphabeta関数はより簡単化できる。（ネガアルファ法） function alphabeta(node, depth, α, β) if node が終端ノード or depth = 0 return node の評価値 foreach child of node α := max(α, -alphabeta(child, depth-1, -β, -α)) if α ≥ β return α // カット return α ただしネガアルファ法では node の評価値の符号を手番によって変える必要がある。
※この「擬似コード」の解説は、「アルファ・ベータ法」の解説の一部です。
「擬似コード」を含む「アルファ・ベータ法」の記事については、「アルファ・ベータ法」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/03/21 15:11 UTC 版)
クイックソートの内部で呼び出す分割関数（partition）とヒープソート（heapsort）は既に実装されているものとすると、イントロソートは以下のように簡潔に書ける： from typing import Anyfrom collections.abc import MutableSequence# ソート関数# 内部で introsort を呼び出す。## @param seq - ソートする配列# @param keyFn - 配列のキー値を計算する関数def sort(seq: MutableSequence[Any], keyFn: Callable[[Any], int]): from math import log2, floor n = len(seq) maxDepth = floor(2 * log2(n)) introsort(seq, keyFn, 0, n - 1, maxDepth)# イントロソート# 再帰が指定した深さに達するまでクイックソートし、# ソートが完了するまでヒープソートする。## @param seq - ソートする配列# @param keyFn - 配列のキー値を計算する関数# @param first - ソート範囲の開始インデックス# @param last - ソート範囲の終端インデックス# @param maxDepth - 再帰の最大深さdef introsort(seq: MutableSequence[Any], keyFn: Callable[[Any], int], first:int, last:int, maxDepth: int): if last <= first: return elif maxDepth == 0: heapsort(seq, keyFn, first, last) else: pivotIndex = partition(seq, keyFn, first, last) introsort(seq, keyFn, first, pivotIndex - 1, maxDepth - 1) introsort(seq, keyFn, pivotIndex + 1, last, maxDepth - 1) なお sort 内で最大深さ（maxDepth）として配列の長さの対数に 2 を掛けたものを選んでいるが、この係数は任意の値でよい。
※この「擬似コード」の解説は、「イントロソート」の解説の一部です。
「擬似コード」を含む「イントロソート」の記事については、「イントロソート」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/27 09:10 UTC 版)
「ランポートのパン屋のアルゴリズム」の記事における「擬似コード」の解説
// 広域変数の宣言と初期値 Enter, Number: array [1..N] of integer = {0}; 1 Thread(i) { 2 while (true) { 3 Enter[i] = 1; 4 Number[i] = 1 + max(Number[1], ..., Number[N]); 5 Enter[i] = 0; 6 for (j = 1; j <= N; j++) { 7 while (Enter[j] != 0) { 8 // スレッド j が番号を得るまで待つ 9 } 10 while ((Number[j] != 0) && ((Number[j], j) < (Number[i], i))) { 11 // 小さい番号を持つスレッドや自分と同じだが高い優先順位の 12 // スレッドが処理を終えるのを待つ 13 } 14 } 15 // クリティカルセクション... 16 Number[i] = 0; 17 // 非クリティカルセクション... 18 } 19 } 注:スレッドはクリティカルセクションに入る前に自分自身も含めてチェックしているが、その場合の条件は常に false となるので、遅延は発生しない。
※この「擬似コード」の解説は、「ランポートのパン屋のアルゴリズム」の解説の一部です。
「擬似コード」を含む「ランポートのパン屋のアルゴリズム」の記事については、「ランポートのパン屋のアルゴリズム」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/12/28 02:27 UTC 版)
MD5ハッシュは、以下の擬似コードで書いたアルゴリズムで算出される。値はすべてリトルエンディアンとする。 function md5 (message : array[0..*] of bit) returns array[0..15] of unsignedInt8 is //左ローテート関数 function leftRotate (x : unsignedInt32, c : integer range 0..31) returns unsignedInt32 is begin leftRotate := (x leftShift c) bitOr (x rightShift (32-c)) end ; function makeK (i : integer range 0..63) returns unsignedIt32 is begin makeK := floor(232×abs(sin(i + 1))) end ;begin//注: すべての変数は符号なし32ビット値で、桁があふれた時は232を法として演算されるものとする。//ラウンドごとのローテート量 sを指定するconst s : array[0..63] of unsignedInt32 := { 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 7, 12, 17, 22, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 5, 9, 14, 20, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 4, 11, 16, 23, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21, 6, 10, 15, 21 } ;//整数ラジアンのときの三角関数からKの値を生成するconst K : array[0..63] of unsignedInt32 := range 0..63 map makeK ;//（Kを事前に計算して、テーブルとしておくこともできる）////const K : array[0..63] of unsignedInt32 :=// {// D76AA478(16進数), E8C7B756(16進数), 242070DB(16進数), C1BDCEEE(16進数),// F57C0FAF(16進数), 4787C62A(16進数), A8304613(16進数), FD469501(16進数),// 698098D8(16進数), 8B44F7AF(16進数), FFFF5BB1(16進数), 895CD7BE(16進数),// 6B901122(16進数), FD987193(16進数), A679438E(16進数), 49B40821(16進数),// F61E2562(16進数), C040B340(16進数), 265E5A51(16進数), E9B6C7AA(16進数),// D62F105D(16進数), 02441453(16進数), D8A1E681(16進数), E7D3FBC8(16進数),// 21E1CDE6(16進数), C33707D6(16進数), F4D50D87(16進数), 455A14ED(16進数),// A9E3E905(16進数), FCEFA3F8(16進数), 676F02D9(16進数), 8D2A4C8A(16進数),// FFFA3942(16進数), 8771F681(16進数), 6D9D6122(16進数), FDE5380C(16進数),// A4BEEA44(16進数), 4BDECFA9(16進数), F6BB4B60(16進数), BEBFBC70(16進数),// 289B7EC6(16進数), EAA127FA(16進数), D4EF3085(16進数), 04881D05(16進数),// D9D4D039(16進数), E6DB99E5(16進数), 1FA27CF8(16進数), C4AC5665(16進数),// F4292244(16進数), 432AFF97(16進数), AB9423A7(16進数), FC93A039(16進数),// 655B59C3(16進数), 8F0CCC92(16進数), FFEFF47D(16進数), 85845DD1(16進数),// 6FA87E4F(16進数), FE2CE6E0(16進数), A3014314(16進数), 4E0811A1(16進数),// F7537E82(16進数), BD3AF235(16進数), 2AD7D2BB(16進数), EB86D391(16進数)// } ;//A、B、C、Dの初期値var a0 : unsignedInt32 := 67452301(16進数) ; // Avar b0 : unsignedInt32 := EFCDAB89(16進数) ; // Bvar c0 : unsignedInt32 := 98BADCFE(16進数) ; // Cvar d0 : unsignedInt32 := 10325476(16進数) ; // D//パディング処理: 1ビットのデータ「1」を追加するmessage[message.length] = (bit) 1 ;//注: 入力のバイト値は、最高位ビットが先のビットであるビット列として解釈するものとする。const initial_message_length : integer := message.length ;//パディング処理: 残りは「0」で埋めるrepeat message[message.length] := (bit) 0until (message.length mod 512) ＝ 448 ; //448 ＝ 512 － 64message[message.length .. message.length+63] := split (initial_message_length mod 264, 1bit) ;//入力を512ビットのブロックに切って、順次処理する//chunk のバイトオーダーは message のバイトオーダーのままであるvar chunk : bits512 ;for each chunk of split (message, 512bit) do var M : array [0..15] of unsignedInt32 := split (chunk, 32bit) ;//内部状態の初期化 var A : unsignedInt32 := a0 ; var B : unsignedInt32 := b0 ; var C : unsignedInt32 := c0 ; var D : unsignedInt32 := d0 ;//メインループ var F : unsignedInt32 ; var g : integer range 0..15 ; for i from 0 to 63 switch case 0 ≦ i ≦ 15 do F := (B bitAnd C) bitOr ((bitNot B) bitAnd D) ; g := i end case case 16 ≦ i ≦ 31 do F := (D bitAnd B) bitOr ((bitNot D) bitAnd C) ; g := (5×i + 1) mod 16 end case case 32 ≦ i ≦ 47 do F := (B bitXor C) bitXor D ; g := (3×i + 5) mod 16 end case case 48 ≦ i ≦ 63 do F := C bitXor (B bitOr (bitNot D)) ; g := (7×i) mod 16 end case end switch F := F + A + K[i] + M[g] ; (D, C, A) := (C, B, D) ; B := B + leftRotate(F, s[i]) ; end for ;//今までの結果にこのブロックの結果を足す a0 := a0 + A ; b0 := b0 + B ; c0 := c0 + C ; d0 := d0 + Dend for ;//16個の8ビット符号なし整数型データ列がMD5値である。//リトルエンディアンでの出力md5[ 0.. 3] := split (a0, 8bit) ;md5[ 4.. 7] := split (b0, 8bit) ;md5[ 8..11] := split (c0, 8bit) ;md5[12..15] := split (d0, 8bit) ;end. なお、RFC 1321 にある本来の式に代えて、以下のように計算するほうが効率的な場合がある（高級言語で書いている場合、コンパイラの最適化に任せるほうがよい。NANDとANDが並行して計算できる環境であれば、並列演算のできない以下の式に比べて、元のままのほうが速いことも多々ある）。 ( 0 ≦ i ≦ 15): F := D bitXor (B bitAnd (C bitXor D))(16 ≦ i ≦ 31): F := C bitXor (D bitAnd (B bitXor C))
※この「擬似コード」の解説は、「MD5」の解説の一部です。
「擬似コード」を含む「MD5」の記事については、「MD5」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2019/05/18 13:51 UTC 版)
以下の擬似コードでは荷物の数を n とし、荷物 i の容量と価値はそれぞれ w[i]、c[i] に格納されているとする。評価値は e[i] ナップサックの現在の容量は W 最大容量は max に格納されており、返すコストを C とする。 for i := 1 .. n e[i] := c[i] / w[i]e[i] の値を降順にソートして、 c[i], w[i] をそれに合わせて並び替える。C := 0; W := 0for i := 1 .. n if w[i] + W < max then W := W + w[i] C := C + c[i]return C 表 話 編 歴 数理最適化 • 最適化問題 : メソッド • ヒューリスティクス非線形(無制約) … 関数 黄金分割探索 直線探索 ネルダー–ミード法 連続放物線補間（英語版） 勾配法 収束性（英語版） 信頼領域 ウルフ条件（英語版） 準ニュートン法 BFGS法 ブロイデン法 L-BFGS（英語版） DFP（英語版） 対称ランク1法（英語版） その他の求解法 ガウス・ニュートン法 最急降下法 レーベンバーグ・マルカート法（英語版） 共役勾配法（非線形共役勾配法） 切り捨てニュートン法（英語版） … ヘッセ行列 最適化におけるニュートン法（英語版） 非線形(制約付き) 一般 バリア関数 ペナルティ関数法（英語版） 微分可能 ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版） 凸最適化 凸縮小化 切断面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版） 線型 および二次 内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版） 組合せ最適化 系列範例(Paradigms) 近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断) グラフ理論 最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版） メタヒューリスティクス 進化的アルゴリズム（進化戦略） 山登り法 局所探索法 焼きなまし法 タブーサーチ カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版） 表 話 編 歴 アルゴリズムソート 比較ソート バブルソート 選択ソート 挿入ソート シェルソート クイックソート マージソート ヒープソート シェーカーソート コムソート ノームソート 図書館ソート イントロソート 奇偶転置ソート 線形時間ソート 鳩の巣ソート 基数ソート バケットソート 並行ソート ソーティングネットワーク バッチャー奇偶マージソート シェアソート 非効率的 ボゴソート ストゥージソート グラフ トポロジカルソート 探索 リスト 線形探索 二分探索 木・グラフ 幅優先探索最良優先探索 均一コスト探索 A* 深さ優先探索反復深化深さ優先探索 深さ制限探索 双方向探索 分枝限定法 文字列 クヌース–モリス–プラット法 ボイヤー-ムーア法 エイホ–コラシック法 ラビン-カープ法 Bitap法 最短経路問題 ダイクストラ法 ベルマン–フォード法 ワーシャル–フロイド法 最小全域木 プリム法 クラスカル法 最大フロー問題最小カット問題 フォード・ファルカーソン法 エドモンズ・カープ法 線型計画問題 シンプレックス法 カーマーカー法 順序統計量 選択アルゴリズム 中央値の中央値 種類 近似アルゴリズム 乱択アルゴリズム その他 分割統治法 動的計画法 貪欲法 カテゴリ
※この「擬似コード」の解説は、「貪欲法」の解説の一部です。
「擬似コード」を含む「貪欲法」の記事については、「貪欲法」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/14 05:46 UTC 版)
「木構造 (データ構造)」の記事における「擬似コード」の解説
前順(n) n を処理 for each (n の子ノード i) 前順(i) 間順(n) if (n に左の子ノードがあれば) 間順(n の左の子ノード) n を処理 if (n に右の子ノードがあれば) 間順(n の右の子ノード) 後順(n) for each (n の子ノード i) 後順(i) n を処理 これらの実装では、木構造の高さのぶんだけコールスタック領域を必要とする。平衡が保たれていない木では、これが深刻な問題となる場合もある。各ノードの親ノードの位置を覚えておくことでスタックを使わないようにもできる。 下記はレベル順の擬似コード。 レベル順(n) n をキューに追加 while (キューに要素を含むなら) n ← キューから取り出す n を処理 for each (n の子ノード i) i をキューに追加
※この「擬似コード」の解説は、「木構造 (データ構造)」の解説の一部です。
「擬似コード」を含む「木構造 (データ構造)」の記事については、「木構造 (データ構造)」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/03 19:37 UTC 版)
「ワーシャル–フロイド法」の記事における「擬似コード」の解説
ワーシャル–フロイド法の擬似コードを記述する。以下で、経路の長さが無限大は経路がないことを意味している。 d i , j {\displaystyle d_{i,j}} は p i , j {\displaystyle p_{i,j}} の長さ。 d i , j {\displaystyle d_{i,j}} を更新する際、経路も記録すると、 p i , j {\displaystyle p_{i,j}} も求めることができる。 グラフ G = ( V , E ) {\displaystyle G=(V,E)} および各辺 e ∈ E {\displaystyle e\in E} の長さ length(e) を入力として受け取る。// 初期化for each i ∈ {\displaystyle \in } {1,...,n} for each j ∈ {\displaystyle \in } {1,...,n} di,j ← i と j を結ぶ辺 e があれば length(e) なければ 無限大// 本計算for each k ∈ {\displaystyle \in } {1,...,n} for each i ∈ {\displaystyle \in } {1,...,n} for each j ∈ {\displaystyle \in } {1,...,n} if (di,j > di,k + dk,j) di,j ← di,k + dk,j
※この「擬似コード」の解説は、「ワーシャル–フロイド法」の解説の一部です。
「擬似コード」を含む「ワーシャル–フロイド法」の記事については、「ワーシャル–フロイド法」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2010/04/18 05:28 UTC 版)
以下に NegaScout の擬似コードを示す。 function NegaScout( node, α, β, depth ) { if ( node.IsLeafNode || depth == 0 ) return Evaluate( node ); /* 終端ノードなので現在のノードを評価する */ node.ExpandChildNode(); /* 手を列挙 */ node.MoveOrdering(); /* 手の並べ替え */ child = node.GetNextChild(); max = v = -NegaScout ( child, -β, -α, depth - 1 ); /* 最善候補を通常の窓で探索 */ if ( β <= v ) return v; /* カット */ if ( α < v ) α = v; while ( ( child = node.GetNextChild() ) != null ){ v = -NegaScout ( child, -α - 1, -α, depth - 1 ); /* Null Window Search */ if ( β <= v ) return v; /* カット */ if ( α < v ) { α = v; v = -NegaScout( child, -β, -α, depth - 1 ); /* 通常の窓で再探索 */ if ( β <= v ) return v; /* カット */ if ( α < v ) α = v; } if( max < v ) max = v; } return max; /* 子ノードの最大値を返す (fail-soft) */ }
※この「擬似コード」の解説は、「Negascout」の解説の一部です。
「擬似コード」を含む「Negascout」の記事については、「Negascout」の概要を参照ください。
擬似コード
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2009/11/07 08:47 UTC 版)
以下に MTD(f) の擬似コードを示す。 node：探索開始ノード f：ミニマックス値を見積もった値 depth：探索の最大深さ function MTDF( node, f, depth ) { g = f; upperBound = +∞; lowerBound = -∞; while ( lowerBound < upperBound ) { if ( g == lowerBound ) β = g + 1; else β = g; /* 置換表付きアルファ・ベータ法で Null Window Search を行う*/ g = AlphaBetaWithMemory( node, β - 1, β, depth ); if ( g < β ) upperBound = g; else lowerBound = g; } return g; }
※この「擬似コード」の解説は、「MTD-f」の解説の一部です。
「擬似コード」を含む「MTD-f」の記事については、「MTD-f」の概要を参照ください。
「擬似コード」の例文・使い方・用例・文例
- 擬似コードのページへのリンク
