ブラウザよりも高速アクセス！
19 関係: 力まかせ探索、人工知能、ナップサック問題、プログラミング言語、ヒューリスティクス、制約プログラミング、制約充足問題、アルゴリズム解析、アクターモデル、エイト・クイーン、再帰、動的計画法、組合せ最適化、Planner、Prolog、束縛 (情報工学)、構文解析、正規表現、深さ優先探索。
力まかせ探索
力まかせ探索（ちからまかせたんさく、Brute-force search）またはしらみつぶし探索（Exhaustive search）は、単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。 バックトラッキングと混同されやすいが、バックトラッキングでは解候補の大部分を明示的に探索することなく捨てることができる。例えば、エイト・クイーンは、8個のクイーンをチェスボード上で互いに取り合えない状態で配置するものである。力まかせ探索では 64! / 56!.
新しい！!: バックトラッキングと力まかせ探索 · 続きを見る »
人工知能
250px 人工知能（じんこうちのう、artificial intelligence、AI）とは、「計算機（コンピュータ）による知的な情報処理システムの設計や実現に関する研究分野」を指す。.
新しい！!: バックトラッキングと人工知能 · 続きを見る »
ナップサック問題
ナップサック問題 ナップサック問題（ナップサックもんだい、Knapsack problem）は、計算複雑性理論における計算の難しさの議論の対象となる問題の一つで、「容量 C のナップサックが一つと、n 種類の品物（各々、価値 pi, 容積 ci）が与えられたとき、ナップサックの容量 C を超えない範囲でいくつかの品物をナップサックに詰め、ナップサックに入れた品物の価値の和を最大化するにはどの品物を選べばよいか」という整数計画問題である。同じ種類の品物を1つまでしか入れられない場合（xi ∈ ）や、同じ品物をいくつでも入れてよい場合（xi ∈ 0以上の整数）など、いくつかのバリエーションが存在する。 決定問題としてのナップサック問題は、「C, pi, ci のほかに価値の合計の目標 V が与えられたとき、容量 C 以内でナップサック内の品物の価値の合計が V 以上になるような品物の選び方はあるか」を判定することである。 全ての品物について pi.
新しい！!: バックトラッキングとナップサック問題 · 続きを見る »
プログラミング言語
プログラミング言語（プログラミングげんご、programming language）とは、コンピュータプログラムを記述するための形式言語である。なお、コンピュータ以外にもプログラマブルなものがあることを考慮するならば、この記事で扱っている内容については、「コンピュータプログラミング言語」（computer programming language）に限定されている。.
新しい！!: バックトラッキングとプログラミング言語 · 続きを見る »
ヒューリスティクス
ヒューリスティック（heuristic, Heuristik）とは、必ず正しい答えを導けるわけではないが、ある程度のレベルで正解に近い解を得ることができる方法である。ヒューリスティックスでは、答えの精度が保証されない代わりに、回答に至るまでの時間が少ないという特徴がある。主に計算機科学と心理学の分野で使用される言葉であり、どちらの分野での用法も根本的な意味は同じであるが、指示対象が異なる。すなわち、計算機科学ではプログラミングの方法を指すが、心理学では人間の思考方法を指すものとして使われる。なお、論理学では仮説形成法と呼ばれている。.
新しい！!: バックトラッキングとヒューリスティクス · 続きを見る »
制約プログラミング
制約プログラミング（Constraint Programming）はプログラミングパラダイムの一つである。 制約プログラミングにおいては、変数間の関係を制約という形で記述することによりプログラムを記述する。制約が他のプログラミングパラダイムのプリミティブと異なっているのは、実行すべきステップではなく解の特性を記述するという点である。制約プログラミングにおける制約は様々である。制約充足問題での制約やシンプレックス法における制約などがある。制約は通常、プログラミング言語に埋め込まれているか別個のライブラリで提供される。 制約プログラミングは制約を論理プログラミングに埋め込んだ制約論理プログラミングが起源である。1987年、Jaffer と Lassez がProlog IIにある種の制約を取り入れたのが最初であった。制約論理プログラミング言語の実装としては、Prolog III、CLP(R)、CHIP がある。今日でも GNU Prolog などの制約論理プログラミングのインタプリタが存在している。 論理プログラミング以外では、制約は関数型言語、項書き換え、命令型言語などと融合させることができる。関数プログラミングでの制約としては、マルチパラダイムプログラミング言語 Oz がある。制約を取り入れた命令型言語としては Kaleidscope がある。しかし、命令型言語での制約はツールキット的な形態でライブラリとして既存の言語向けに提供されている場合がほとんどである。.
新しい！!: バックトラッキングと制約プログラミング · 続きを見る »
制約充足問題
制約充足問題（せいやくじゅうそくもんだい、Constraint satisfaction problem, CSP）は、複数の制約条件を満たすオブジェクトや状態を見つけるという数学の問題を指す。CSPは特に人工知能やオペレーションズ・リサーチで研究されている。多くのCSPでは、それなりの時間内に解くのにヒューリスティクスと組合せ最適化手法を組み合わせる必要がある。 制約充足問題の具体例.
新しい！!: バックトラッキングと制約充足問題 · 続きを見る »
アルゴリズム解析
アルゴリズム解析とは、アルゴリズムの実行に必要とされるリソース（時間や記憶領域）量を見積もることである。多くのアルゴリズムは任意長の入力を受け付けるよう設計されている。アルゴリズムの「効率」や「複雑さ」は一般に、入力長からそのアルゴリズムを実行するのに必要なステップ数（時間複雑性）や記憶領域サイズ（空間複雑性）への関数として表される。 アルゴリズム解析は計算複雑性理論の重要な一分野である。計算複雑性理論では、与えられた計算問題を解くアルゴリズムが必要とするリソースを理論的に見積もる。この見積もりにより効率的なアルゴリズムを設計する指針が得られることがある。 アルゴリズム解析ではふつう、漸近的（asymptotic）な意味で複雑性を見積もる。すなわち、ある程度大きな入力長の際の複雑性関数を見積もる。このためにO記法、Ω記法、Θ記法が用いられる。例えば、二分探索のステップ数は入力サイズの対数に比例し、これを O(log(n)) と表記したり、「対数時間」と称したりする。このような漸近的な見積もりを用いるのは、同じアルゴリズムでも実装の違いにより差が出るのを捨象するためである。異なる妥当な実装による効率の違いは定数倍に留まる。この定数を隠れた定数（hidden constant）と呼ぶ。 漸近的でない正確な効率がわかる場合もあるが、そのためには「計算モデル」と呼ばれるアルゴリズムの特定の実装を仮定する必要がある。計算モデルはチューリング機械のような抽象化された機械を使うか、個々の命令の実行時間が変化しないと仮定することが多い（例えば実際のコンピュータではキャッシュにヒットするかしないかでは大きく実行時間が異なるが、アルゴリズム解析では一般にそれを無視する）。例えば、二分探索で N 個のソートされた数から探索する場合、1回の参照を一定の単位時間でできるとした場合、回答を得るまでに最大で log2 N+1 単位時間を要する。.
新しい！!: バックトラッキングとアルゴリズム解析 · 続きを見る »
アクターモデル
アクターモデル（actor model）とは、1973年、カール・ヒューイット、Peter Bishop、Richard Steiger が発表した並行計算の数学的モデルの一種Carl Hewitt（1973年）, "A Universal Modular Actor Formalism for Artificial Intelligence".
新しい！!: バックトラッキングとアクターモデル · 続きを見る »
エイト・クイーン
イト・クイーンとは、チェスの盤とコマを使用したパズルの名称である。.
新しい！!: バックトラッキングとエイト・クイーン · 続きを見る »
再帰
再帰（さいき）は、あるものについて記述する際に、記述しているものそれ自身への参照が、その記述中にあらわれることをいう。定義において、再帰があらわれているものを再帰的定義という。 主に英語のrecursionとその派生語の訳にあてられる。他にrecurrenceの訳（回帰#物理学及び再帰性を参照のこと）や、reflexiveの訳として「再帰」が使われることがある。数学的帰納法との原理的な共通性から、recursionの訳として数学では「帰納」を使うことがある。.
新しい！!: バックトラッキングと再帰 · 続きを見る »
動的計画法
動的計画法（どうてきけいかくほう、Dynamic Programming, DP）は、計算機科学の分野において、アルゴリズムの分類の1つである。対象となる問題を複数の部分問題に分割し、部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ。.
新しい！!: バックトラッキングと動的計画法 · 続きを見る »
組合せ最適化
組合せ最適化（くみあわせさいてきか、combinatorial optimization、組み合わせ最適化、または組み合せ最適化とも表記される）は、応用数学や情報工学での組合せ論の最適化問題である。オペレーションズリサーチ、アルゴリズム理論、計算複雑性理論と関連していて、人工知能、数学、およびソフトウェア工学などの交差する位置にある。組合せ最適化では、厳密解が簡単に求まる場合もあれば、そうでない場合もある。厳密解を求めるのが難しいと思われる問題を解くために、その問題の解空間を探索する場合もあり、そのためのアルゴリズムでは、効率的に探索するために解空間を狭めたりすることもある。.
新しい！!: バックトラッキングと組合せ最適化 · 続きを見る »
Planner
Planner（"PLANNER"とも表記される）は、1969年にMITのカール・ヒューイットが設計したプログラミング言語。当初、サブセットの Micro-Planner や Pico-Planner が実装され、後に完全実装として Popler が登場。その後、派生言語として QA-4、Conniver、QLISP、Ether などが実装され、1970年代の人工知能研究の道具として重要な役割を果たし、商用の KEE や ART の開発にも影響を与えた。 当時マービン・ミンスキー、シーモア・パパート、Mike Peterson の学生だったヒューイットは、「知識の手続き的埋め込み」論者であり、高レベルの手続き的計画によるアプローチを信奉していた。当時、ジョン・マッカーシーらは人工知能(AI)のための知識表現として数理論理学を用いた宣言的かつ論理的アプローチを信奉しており、両者は対立関係にあった。このことは次のような基本的な疑問を生み出した。「手続き的アプローチと論理的アプローチの違いは何か?」である。これに答えが出せるようになるまで数年を要した。.
新しい！!: バックトラッキングとPlanner · 続きを見る »
Prolog
Prolog（プロログ）は、非手続き型プログラミング言語の一つ。論理型言語に分類される。名称は、「論理を使ったプログラミング」を意味するフランス語「programmation en logique」に由来しているRobert Kowalski.
新しい！!: バックトラッキングとProlog · 続きを見る »
束縛 (情報工学)
束縛またはバインディング（Binding）は一般に、参照 (情報工学) の集合である。コンピュータ関連で「束縛」という語が使われるものはいくつかあり、それぞれ具体的な内容は異なるので、以下いくつかの例を示す。.
新しい！!: バックトラッキングと束縛 (情報工学) · 続きを見る »
構文解析
構文解析（こうぶんかいせき、syntactic analysis あるいは parse）とは、文章、具体的にはマークアップなどの注記の入っていないベタの文字列を、自然言語であれば形態素に切分け、さらにその間の関連（修飾-被修飾など）といったような、統語論的（構文論的）な関係を図式化するなどして明確にする（解析する）手続きである。自然言語については自然言語処理における要点のひとつであり、プログラミング言語など形式言語の場合は、形式文法に従い構文木を得る。構文解析を行う機構を構文解析器（parser）と呼ぶ。.
新しい！!: バックトラッキングと構文解析 · 続きを見る »
正規表現
正規表現（せいきひょうげん、regular expression）とは、文字列の集合を一つの文字列で表現する方法の一つである。正則表現（せいそくひょうげん）とも呼ばれ、形式言語理論の分野では比較的こちらの訳語の方が使われる。まれに正規式と呼ばれることもある。 もともと正規表現は形式言語理論において正規言語を表すための手段として導入された。形式言語理論では、形式言語が正規言語であることと正規表現によって表せることは同値である。 その後正規表現はテキストエディタ、ワードプロセッサなどのアプリケーションで（ないし、そもそもそれ以前に単機能の文字列探索ツールの）、マッチさせるべき対象を表すために使用されるようになり、表せるパターンの種類を増やすために本来の正規表現にはないさまざまな記法が新たに付け加えられた。このような拡張された正規表現には正規言語ではない文字列も表せるものも多く、ゆえに正規表現という名前は実態に即していない面もあるが、伝統的に正規表現と呼ばれ続けている。 この記事では主にこのような正規表現を用いたパターンマッチングについて説明している。以下、誤解のない限り、アプリケーションやプログラミングにおいて正規表現を用いた文字列のパターンマッチングを行う機能のことを、単に正規表現という。 ほとんどのプログラミング言語では、ライブラリによって正規表現を使うことができる他、一部の言語では正規表現のリテラルもある。「正規表現によるマッチ」を意味する（専用の）演算子がある言語なども一部ある。具体例として、grep、AWK、sed、Perl、Tcl、lexなどがある。 それぞれの言語やアプリケーションで細部の仕様が異なっている、といったように思われることも多いが（また、古い実装では実際にそういうことも多いが）、近年は同じライブラリを使っていれば同じということも多い。またPOSIXなど標準もある。.
新しい！!: バックトラッキングと正規表現 · 続きを見る »
深さ優先探索
深さ優先探索のイメージ 深さ優先探索（ふかさゆうせんたんさく、depth-first search, DFS、バックトラック法ともいう）は、木やグラフを探索するためのアルゴリズムである。アルゴリズムは根から(グラフの場合はどのノードを根にするか決定する)始まり、バックトラックするまで可能な限り探索を行う。「縦型探索」とも呼ばれる。.
新しい！!: バックトラッキングと深さ優先探索 · 続きを見る »
