問題タブ [backtracking]

正規表現マッチングを実装するには、DFA、NFA、およびバックトラッキングの 3 つの異なるソリューションがあります。私は例を探しています:

• DFA で解決できる正規表現と、DFA で十分である理由。
• NFA を必要とする正規表現と、NFA が必要な理由。
• バックトラッキングが必要な正規表現と、バックトラッキングが必要な理由。

このトピックに関するいくつかの優れた文献の推奨もいいでしょう.

私はプロローグでいくつかの問題を抱えています。2つの都市間のすべてのパスを返す述語を書き込もうとしていますが、現時点では無限ループで最初に見つかったパスを返します。どこが間違っているのかわかりませんが、私は一日中これを理解しようとしていて、どこにも行きません。

提供できるどんな助けもいただければ幸いです。

ここで期待している出力は[spa、ath、lon] 4 [spa、kol、lon]3です。

もう一度、助けていただければ幸いです。

よろしくお願いします。

同様の質問に目を通しましたが、私の問題に関連するものは何も見つかりません。のデータベースを使用して、からCityAへのパスを見つけるアルゴリズムまたは「ループ」のセットを見つけるのに苦労していますCityB

事実。これまでになんとかできたことは以下のとおりですが、常にバックトラックしwrite(X),て最終的な反復で完了します。これは、私がやりたいことですが、ある程度だけです。

たとえば、行き止まりになっている都市名を出力したり、最終的な繰り返しを使用したりしたくありません。基本的に からCityAまでのパスを作成CityBし、そのパス上に移動先の都市の名前を書きます。

誰かが私を助けてくれることを願っています！

入力: n ( int) とn値 ( float) は、 と の間のランダムな値で為替レート (それらの間で異なります) を表し4ます5。

出力:上昇曲線と下降曲線を表すために (同じ順序で) 使用できる値の最大数を計算しますか?

ex 八つの価値観

出力する必要があります

5 (4.5 4.6 4.8 4.4 4.1)

私のアプローチ

• 連続したifs を試すと、曲線条件を尊重するランダムな配列が得られますが、最長ではありません。
• 私はそれに慣れていないのでバックトラックを試みていませんが、それを使ってすべての解を計算し、最も長いものを選ぶ必要があると何かが教えてくれます。
• そして最後に、ブルートフォースですが、これはアルゴリズム設計の課題であるためです。私はそれを手渡さないかもしれません。:)

よりシンプル/より効率的/高速な方法はありますか?

Daniel Lemireのアルゴリズムに基づいた私の試みは次のとおりです。位置0、i、nを考慮していないようです。ifs が問題だと確信していますが、どうすれば修正できますか?

私は答えを求められたこの質問に汗を流してきました（技術的には宿題です）。私はハッシュテーブルを検討しましたが、これをどのように機能させるかについての正確な詳細に固執しています

ここに質問があります：

整数のkセット_A1、A ₂、..、合計サイズO（n ）のA k_が与えられた場合 、₁ ϵ A ₁、a ₂ ϵ A ₂、.. 、_ak ϵ A _k、a ₁ + a ₂ + .. + a _{k −1} = _akとなるように。アルゴリズムはTk （n）時間で実行する必要があります。ここで、_{T k}（n）= O（n ^{k /2} ×logn ）（偶数kの場合） 、O（n ^{（k +1）/ 2 ）（} kの奇数値の場合）。

私がこれを解決することに近づくことができるように、誰かが私に一般的な方向性を与えることができますか？

Scala のアルゴリズムで streamaを定義する方法はありますか?backtracking

たとえば、次のbacktrackingアルゴリズムは、指定されたサイズのすべての「バイナリ」文字列を出力します。

別の反復アルゴリズムstreamを使用して、特定のサイズの「バイナリ」文字列を定義できると思います。ただし、上記のバックトラッキングアルゴリズムを.stream

OpenStreetMapsからMySQLテーブルとしてベクターデータを取得することは可能ですか？たとえば、Points_of_routes（x、y、id）、Nodes（point1、point2、id）、Route_define（route_id、node、id）、Route_info（name、level、id） ）...？

このデータベース構造を使用して、バックトラックアルゴリズムとUTMを使用してポイントAからポイントBまでの最短距離を検索したいと思います。

私は昨夜今日までネット全体を広範囲に検索してきましたが、特にバックトラッキングアルゴリズムを使用して最短経路問題を解決する方法を説明しているリソースを見つけることができないようです。このアルゴで解いてみましたが、意味がわかりません。それがn-クイーンの問題であれば、それほど複雑ではありません。

それで、誰かが私にいくつかのリソースを指すいくつかのインターネットリンクを与えることができますか？とても感謝しています。

*更新：興味深いことに、バックトラッキングアルゴリズムは本当に最短経路問題を解決できますか？

スパニングツリーを見つけるためにc++でDFSアルゴリズムの実装を行っていますが、アルゴリズムDFSを使用したスパニングツリーの出力は常に事前注文ですか、それともまったくの偶然ですか？

問題は：

数学の 3 クラス、PC プログラミングの 3 クラス、物理学の 2 クラスを 1 週間に 5 日間で混合する可能性をすべて出力します。学生は 1 週間のうち少なくとも 1 クラス、最大で 3 クラスを持っています。どんなに混ざっても」

M: [数学,数学,数学]
T: [PC プログラム,PC プログラム]
W: [PC プログラム]
T: [物理]
F: [物理]

私は Python で 15/5 = 3 (学生が持つことができる最大クラス) のすべてのクラスを含む 15 要素のリストを作成するというアイデアを持っているので、上記の例ではリストは次のようになりますが[m,m,m,cs,cs,0,cs,0,0,p,0,0,p,0,0]、私はそうしません。バックトラッキングを使用してすべてのリストを生成する方法を本当に知りません。アイデアを教えてください。