ヒューリスティックとアルゴリズムの違いは何ですか?
127538 次
12 に答える
108
アルゴリズムは、問題に対する自動化されたソリューションの説明です。アルゴリズムが何をするかは正確に定義されています。解決策は可能な限り最善のものである可能性もありませんが、どのような結果が得られるかは最初からわかっています。何らかのプログラミング言語を使用してアルゴリズムを実装し、プログラム(の一部) を取得します。
現在、一部の問題は難しく、許容できる時間内に許容できる解決策を得ることができない場合があります。そのような場合、いくつかの任意の選択 (知識に基づいた推測) を適用することで、それほど悪くない解決策をより迅速に得ることができます。これはヒューリスティックです。
ヒューリスティックも一種のアルゴリズムですが、考えられる問題のすべての状態を調査するわけではなく、最も可能性の高い状態を調査することから始めます。
典型的な例はゲームです。チェス ゲームのプログラムを作成するとき、考えられるすべての動きをある深さレベルで試し、ボードに何らかの評価関数を適用することを想像できます。ヒューリスティックは、明らかに悪い動きで始まる完全な分岐を除外します。
場合によっては、最適なソリューションを探しているのではなく、何らかの制約に適合するソリューションを探していることがあります。優れたヒューリスティックは短時間で解決策を見つけるのに役立ちますが、試行しないことを選択した状態に唯一の解決策がある場合は、何も見つけられない可能性もあります。
于 2010-02-26T15:42:09.357 に答える
34
- 通常、アルゴリズムは決定論的であり、最適な結果が得られることが証明されています
- ヒューリスティックには正しさの証明がなく、多くの場合、ランダムな要素が含まれ、最適な結果が得られない場合があります。
最適な解を見つけるための効率的なアルゴリズムが知られていない多くの問題には、最適に近い結果を非常に迅速に生成するヒューリスティックなアプローチがあります。
「遺伝的アルゴリズム」は受け入れられている用語ですが、厳密に言えば、それらはヒューリスティックであり、アルゴリズムではありません。
于 2010-02-25T13:29:08.243 に答える
22
一言で言えば、ヒューリスティックは「教育を受けた推測」です。ウィキペディアはそれをうまく説明しています。最後に、「一般に受け入れられる」方法が、指定された問題に対する最適な解決策として採用されます。
ヒューリスティックは、問題解決、学習、発見に役立つ経験ベースの手法の形容詞です。ヒューリスティックな方法を使用して、可能な限り最良の答え、つまり「最適解」に近いことが期待される解に迅速に到達します。ヒューリスティックスとは、「経験則」、知識に基づく推測、直感的な判断、または単なる常識です。ヒューリスティックは、問題を解決する一般的な方法です。名詞としてのヒューリスティックスは、ヒューリスティック手法の別名です。
より正確に言えば、ヒューリスティックスとは、人間と機械の問題解決を制御するために、簡単にアクセスできるが大まかに適用可能な情報を使用する戦略を表します。
アルゴリズムは、問題を解決するために使用される有限の命令セットを含む方法です。この方法は、問題に対して機能することが数学的または科学的に証明されています。形式的な方法と証明があります。
ヒューリスティック アルゴリズムは、一般的なヒューリスティックの方法で、多くの実際的なシナリオで問題に対して許容可能なソリューションを生成できるアルゴリズムですが、その正確性の正式な証明はありません。
于 2010-02-25T13:29:09.320 に答える
9
アルゴリズムは、実行される自己完結型の段階的な一連の操作であり4、通常、次のような問題の解決策を決定するための (コンピューターまたは人間の) 命令の有限シーケンスとして解釈されます。 B、または A と B の間の最小パスは何ですか。後者の場合、「かなり近い」代替ソリューションで満足することもできます。
アルゴリズムには特定のカテゴリがあり、ヒューリスティック アルゴリズムはその 1 つです。この場合のアルゴリズムの (実証済みの) プロパティに応じて、次の 3 つのカテゴリのいずれかに分類されます (注 1)。
- Exact : 解が入力問題の最適 (または正確な解)であることが証明されて
- 近似: 解の値の偏差は、事前に定義された境界よりも最適値から離れていないことが証明されています (たとえば、最適値よりも 50% 以上大きくなることはありません)。
- ヒューリスティック: アルゴリズムが最適であることが証明されておらず、事前に定義された最適解の範囲内に収まっていない
近似アルゴリズムもヒューリスティックですが、それが出力する解 (値) に証明された境界があるというより強力なプロパティがあることに注意してください。
一部の問題については、最適解を計算するための「効率的な」アルゴリズムを誰も発見していません (注 2)。そのような問題の 1 つに、有名な巡回セールスマン問題があります。たとえば、巡回セールスマン問題に対するクリストフィデスのアルゴリズムは、最適解の 50% 以内であることが証明されていなかったため、ヒューリスティックと呼ばれていました。ただし、証明されているため、Christophides のアルゴリズムは、より正確には近似アルゴリズムと呼ばれます。
コンピュータができることには制限があるため、可能な限り最適なソリューションを効率的に見つけることが常に可能であるとは限りません。問題に十分な構造がある場合、解空間が巨大であっても (つまり、最短経路問題の場合)、解空間をたどる効率的な方法が存在する可能性があります。
ヒューリスティックは通常、アルゴリズムの実行時間を改善するために適用され、「専門家の情報」または「知識に基づく推測」を追加して検索方向を導きます。実際には、ヒューリスティックは最適なアルゴリズムのサブルーチンであり、最初にどこを見るかを決定することもできます。
(注 1) : また、アルゴリズムには、ランダム要素または非決定論的要素が含まれているかどうかによって特徴付けられます。常に同じ方法で実行し、同じ答えを生成するアルゴリズムは、決定論的と呼ばれます。
(注 2) : これは P 対 NP 問題と呼ばれ、NP 完全および NP 困難に分類される問題は、「効率的な」アルゴリズムを持つ可能性は低いです。ノート; コメントで@Krissが述べたように、「より悪い」タイプの問題もあり、計算には指数関数的な時間またはスペースが必要になる場合があります。
質問の一部に答えるいくつかの回答があります。私はそれらが完全ではなく、十分に正確ではないと考え、@Krissによって行われた受け入れられた回答を編集しないことにしました
于 2016-01-20T16:49:20.610 に答える
6
実際、私はそれらの間に多くの共通点があるとは思わない. 一部のアルゴリズムは、ロジックでヒューリスティックを使用します (多くの場合、計算を少なくしたり、結果を速くしたりするために)。通常、ヒューリスティックは、いわゆる貪欲なアルゴリズムで使用されます。
ヒューリスティックスとは、アルゴリズムで最良の選択を行うために使用するとよいと思われる「知識」です (選択を行う必要がある場合)。たとえば...チェスのヒューリスティックは次のようになります（可能であれば、常に対戦相手のクイーンを取ります。これがより強いフィギュアであることを知っているからです）。ヒューリスティックスは、それが正しい答えに導くことを保証するものではありませんが、(仮定が正しい場合) はるかに短い時間で最良に近い答えを得ることがよくあります。
于 2010-02-25T13:24:19.263 に答える
4
Heuristics are algorithms, so in that sense there is none, however, heuristics take a 'guess' approach to problem solving, yielding a 'good enough' answer, rather than finding a 'best possible' solution.
A good example is where you have a very hard (read NP-complete) problem you want a solution for but don't have the time to arrive to it, so have to use a good enough solution based on a heuristic algorithm, such as finding a solution to a travelling salesman problem using a genetic algorithm.
于 2010-02-25T15:02:11.907 に答える
4
アルゴリズムは、与えられた入力が何か (関数) を計算し、結果を出力するいくつかの操作のシーケンスです。
アルゴリズムにより、正確な値または近似値が得られる場合があります。
また、正確な値に近い可能性が高いランダム値を計算する場合もあります。
ヒューリスティック アルゴリズムは、入力値に関するいくつかの洞察を使用し、正確な値を計算しません (ただし、最適値に近い場合があります)。いくつかの特殊なケースでは、ヒューリスティックが正確な解を見つけることができます。
于 2010-02-25T16:51:34.890 に答える
4
アルゴリズムは、問題を解決するための明確に定義された一連の指示です。ヒューリスティックスは、学習と発見のアプローチを利用して解決策に到達することを伴います。
したがって、問題を解決する方法を知っている場合は、アルゴリズムを使用してください。ソリューションを開発する必要がある場合、それはヒューリスティックです。
于 2010-02-25T13:29:18.677 に答える
2
通常、ヒューリスティックは最適化または戦略であり、通常は十分な答えを提供しますが、常に最良の答えになるとは限りません。たとえば、巡回セールスマンの問題を力ずくで解決する場合、コストが現在の最適なソリューションのコストを超えると、部分的なソリューションを破棄するのはヒューリスティックです。 t アルゴリズムの理論上の (big-oh 表記法) 実行時間を改善する
于 2010-02-25T13:29:59.833 に答える
2
ヒューリスティックは、将来のソリューションの状態を予測するのが難しいため、人工知能の学習ベースのモデルで使用される制約に近いと思います。
しかし、上記の回答を読んだ後の私の疑問は、「確率的最適化手法を使用してヒューリスティックをどのようにうまく適用できるでしょうか?または、確率的最適化で使用すると本格的なアルゴリズムとして機能できるでしょうか?」ということです。
于 2011-01-26T18:03:35.140 に答える
2
私が読んだ中で最も優れた説明の 1 つは、すばらしい本Code Completeからのものです。
ヒューリスティックとは、答えを探すのに役立つ手法です。ヒューリスティックは何を見つけるかではなく、どう見るかだけを教えてくれるので、その結果は偶然に左右されます。ポイント A からポイント B に直接移動する方法は説明されていません。点 A と点 B がどこにあるのかもわからないかもしれません。実際、ヒューリスティックは道化師のスーツを着たアルゴリズムです。予測が難しく、より楽しく、30 日間の返金保証はありません。
これは誰かの家に車で行くためのアルゴリズムです: 国道 167 号線を南にピュイ アラップまで行きます。サウス ヒル モール出口を出て、丘を 4.5 マイル (4.5 マイル) 進みます。食料品店のそばの信号を右折し、最初の角を左折します。714 North Cedar の左側にある大きな黄褐色の家の私道に入ります。
これは、誰かの家にたどり着くためのヒューリスティックです。私たちがあなたに送った最後の手紙を見つけてください。返送先住所の町まで車で行きます。町に着いたら、誰かに私たちの家がどこにあるか尋ねてください。誰もが私たちを知っています。誰かが喜んでお手伝いします。見つからない場合は、公衆電話からお電話いただければお迎えに参ります。
アルゴリズムとヒューリスティックの違いは微妙で、この 2 つの用語は多少重なっています。この本では、この 2 つの主な違いは、ソリューションからの間接的なレベルです。アルゴリズムが指示を直接与えます。ヒューリスティックは、自分で指示を見つける方法、または少なくとも指示を探す場所を教えてくれます。
于 2012-05-04T13:23:59.103 に答える
0
彼らは、見つかった解の品質に関して何の保証もなく、次善の解を見つけます。ヒューリスティックのみの多項式の開発に意味があることは明らかです。これらの方法の適用は、実世界の問題や大きな問題を解決するのに適しているため、計算の観点からは扱いにくいため、多項式時間で近似解を見つけることができるアルゴリズムすらありません。
于 2011-01-26T18:17:10.983 に答える