4

私が遭遇する「難しい」組み合わせ問題のいくつか は、アルファベータ法、ビームサーチ、または同様のアルゴリズムなど、ある種のツリーサーチの観点から投げかけることができることに気づきました。ただし、それらをプログラミングすることは、同じことを繰り返しコーディングしているように見え、間違いを犯しやすいこともあります。これらのアルゴリズムを実装するライブラリがあるはずだと私には思えます、そして私が書くように頼まれるべきなのは

  1. ソリューションのコーディング、つまり、不完全なソリューションからより具体的なソリューションを取得する方法。これにより、ツリー/グラフの構造が得られます。
  2. 部分的な解決策を考えると、最大/最小コストを取得する方法、そしておそらくコストの見積もり。
  3. 初期ソリューション/部分ソリューション。
  4. 多分ある種の検証ソリューション。

特定のコードを提供していないことをお詫び申し上げますが、問題を説明したと思います。上記の関数のコードを記述できれば、多くのツリー/グラフ検索アルゴリズムを簡単に実行できるはずではありませんか？これを簡単にサポートするユーザーフレンドリーなライブラリ/フレームワークはありますか？PythonまたはC/C ++で使用したいのですが、何か提案があれば興味があります。

編集：より正確に言うと、私は情報に基づいたツリー検索アルゴリズムについて話しています。

4

5 に答える 5

2

QuickGraph

.Netに進んで行く人は、すべてのグラフ/ツリーベースの処理のためのオープンソースのQuickGraphライブラリを見てください。これは、グラフ表現、アルゴリズム、突然変異、および表現に関連するすべての概念をきちんと分離します。多数の拡張ポイントがあるため、ほとんどのグラフキャスト可能な問題をサポートできるはずです。

[編集]QuickGraphで提供される一連のアルゴリズムには、現時点ではアルファベータ法やビームサーチは含まれていませんが、その「検索」アルゴリズムセクションには、お気に入りのトラバーサルアルゴリズムを実装するための十分なガイダンスを提供する他の11のメソッドが含まれています。アルファベータとビームをサポートすると想像します。

広告。1 ただし、不完全な解（つまり現在のノード）に基づいていくつかのより具体的な解（つまり隣接ノード）を返すデリゲート関数を挿入できるという点で、最初の基準を満たしています。これはDelegateImplicitGraph（およびバリエーション）によって処理され、検索スペース全体を一度にメモリに格納することを防ぐため、メモリ効率が高いと考えられます。 広告。2さらに、アルゴリズムは、最大/最小/予想コストヒューリスティックなどのカスタムデリゲートを使用する場合があります（を参照AStarShortestPathAlgorithm）。これは2番目の基準を満たしています。

要約すると、QuickGraphは問題の構造化を支援し、さまざまなタイプの問題にドロップインアルゴリズムを提供し、新しいアルゴリズムを提供することで問題を改善できるようにします。

于 2011-04-09T21:33:06.323 に答える
1

BoostにはBoostGraphLibary（BGL）があります。Boostグラフライブラリユーザーズガイドには、暗黙のグラフを使用したナイトツアーの問題の例があります。

于 2011-04-04T13:07:04.113 に答える
1

特定のステップを指定せずに問題を表現することは、一種の宣言型プログラミングです。

あなたは「部分的な解決策」について話します。これは、検討している種類の問題に重複するサブ問題があることを意味しますか？もしそうなら、それはあなたが一般的な動的計画法を行う方法を求めているように聞こえます。つまり、実際に意味するのは、連続するステップを通じて関数を構築し、問題のより単純なバージョンを解決してから反復することです。このMathematicaジャーナルの記事にはいくつかの良い例があります。

Prologを検討しましたか？これはフレームワークではありませんが、必要に応じて、検索アルゴリズムが言語に組み込まれています。Prologのようなものをベースとして使用して、非常に一般的な制約プログラミングソリューションを作成することができます。Pythonには、python-constraintライブラリがあります。これは非常に便利です。過去に使用したことがあります。

于 2011-04-08T17:10:58.043 に答える
1

Fuegoは、オープンソースのモンテカルロツリー検索（アルファベータツリー検索ではなく）プラットフォームであり、2人用の完全な情報ゲーム（元々はGoをターゲットとして作成されたもの）をターゲットにできます。それよりも一般的かもしれません。

http://fuego.sourceforge.net/

編集：アルファベータサーチャーも備えていることを知りました。最近の論文は次のとおりです： http ：//webdocs.cs.ualberta.ca/~mmueller/ps/fuego-TCIAIG.pdf

于 2011-04-09T22:50:22.060 に答える
0

オンラインで情報に基づいた検索と情報に基づいていない検索を行うためのPeterNorvigのPythonコードを見つけました。A-star検索をサポートしており、私が見ることができるものから一般的な問題をプログラムするために使用できます。それは十分に速いのか、それともビームサーチ、分枝限定法などに拡張できるのだろうか。

于 2011-04-09T19:30:40.493 に答える