問題タブ [dijkstra]

AI の本の 1 つで、よく知られている「15 パズル」を解決するために、シミュレーションやゲームでパスを見つけるための一般的なアルゴリズム (A-Star、Dijkstra) も​​使用されていることを読みました。

これらのアルゴリズムの1つを適用できるように、15パズルをノードとエッジのグラフに縮小する方法について、誰かが私にいくつかの指針を与えることができますか?

グラフの各ノードをゲームの状態として扱うとしたら、そのツリーは非常に大きくなりませんか? それとも、それはそれを行うための方法ですか？

約100個のノードと約200個のエッジを持つ無向グラフがあります。1つのノードには「start」というラベルが付けられ、もう1つは「end」というラベルが付けられ、「mustpass」というラベルが付けられたノードが約12個あります。

'start'で始まり、'end'で終わり、すべての' mustpass'ノードを（任意の順序で）通過する、このグラフの最短経路を見つける必要があります。

（http://3e.org/local/maize-graph.png / http://3e.org/local/maize-graph.dot.txtは問題のグラフであり、ペンシルバニア州ランカスターのトウモロコシの迷路を表しています）

Edsger Dijsktra が見た、プログラミング スタイルに関するこの記事に出会いました。簡単に言い換えると、主な違いはモーツァルトです。プログラミングに例えると、何かを書く前に問題を完全に理解している (議論の余地がある) のに対し、ベートーベンは紙にメモを書きながら決定を下し、途中で多くの改訂を行いました。Mozart プログラミングでは、バージョン 1.0 は、エラーなしで最大限の効率で動作することを目指すソフトウェアの唯一のバージョンです。また、Dijkstra は、そのレベルの洗練度と安定性に達しないソフトウェアは公開すべきではないと述べています。

彼の見解に基づいて、2 つの質問があります。モーツァルトのプログラミングは可能ですか? 代わりにモーツァルト スタイルを採用した場合、今日私たちが作成するソフトウェアは本当に役立つのでしょうか?

私の考え。ソフトウェアの複雑化に対処するために、私たちはこの方法から、アジャイル開発、公開ベータ テスト、コンスタント リビジョンなど、速度が最も重要な Web 開発を定義する方法に移行したようです。しかし、Web ソフトウェアが通過できるすべてのリビジョンを考えると、特にメンテナンス中に、パッチがパッチの上に適用され、退屈なリファクタリング プロセスによって洗練されることがよくあります。Mozart の方法は非常に魅力的です。少なくとも、Digsby、Windows、iTunes などの煩わしいソフトウェア アップデートは軽減されます。これらの多くは、新しい即時リリースを必要とする予期せぬ脆弱性の結果です。

編集:ダイスクトラの見解のより正確な説明については、以下の回答を参照してください。

A* パス検索アルゴリズムの定義を調べていますが、場所によって定義が多少異なっているようです。

違いは、ノードのサクセサーを通過するときに実行されるアクションと、サクセサーがクローズド リストにあることを見つけることです。

• 1 つのアプローチ (ウィキペディアとこの記事で提案) は、次のように述べています。
• 別のアプローチ (たとえば、こことここで推奨) は次のように述べています。現在計算されているスコアよりも高い場合は、今後の調​​査のためにクローズド リストからアイテムを削除します。

私は混乱しています - どの方法が正しいですか? 直感的には前者の方が分かりやすいのですが、定義の違いが気になります。定義の 1 つが間違っていますか、それとも何らかの形で同形ですか?

AdjacencyGraph<string, Edge<string>>実行したいがAlgorithmExtensions.ShortestPathsDijkstraありますが、QuickGraph のドキュメントは最適ではありません。

誰かが私に従うことができる例を持っていますか?

私が Google で見つけたものはすべてオブザーバーを使用していましたが、これはAlgorithmExtension必要ありません。

これは一種の奇妙な質問です。形式手法を使ったプログラミングの学習に関する本を書いている最中です。プログラミングの経験がある人を対象にしています。アイデアは、彼らに高品質のプログラマーになるように教えることです。

基本的な表記法は、いくつかの並行性と通信の拡張機能とともに、ダイクストラのプログラミングの分野からのものになります。

EWDとは異なり、最終的には生徒に実際の実行可能プログラムを作成してもらいたいと思います。つまり、ある時点でEWD表記から他の言語に翻訳することを意味します。私が最初に正式なプログラミングを始めたとき、私はCをターゲットにしましたが、多くの配管を書くことになります。さらに、ポインターの処理などの複雑さがすべてあります。Rubyは、SchemeやLispと同様に、明らかに可能なターゲットです。しかし、さまざまな機能言語もあります。私は特に並行性に興味があるので、Erlangは可能性のようです。

それで、最後に、私の質問があります：彼らの正式に開発されたプログラムをターゲットにするために、私は私の読者にどの言語を教えるべきですか？

ダイクストラ アルゴリズムの j2ME 実装を高速化するのを手伝ってくれる人はいますか? 2 つのループがあり、1 つは別のループです。このような

ほぼ 23000 のノードとそれらを接続する 50000 のエッジがあります...以下で説明するすべての改善の後、内側のループは平均 169330131 回実行されます。w910i モバイルでは完了までに 5 分かかり、エミュレータでは数分以上かかります。これは私には多すぎるように見えます。改善のための提案はありますか？私はすでに以下の改善を実装しています。

1. ベクトルの代わりに配列を使用します。
2. 内側のループが訪問したノードを考慮していないことを確認してください。訪問したすべてのノードは配列の最後にあり、ノードはその数を知っています。だから、私は簡単にそれらを完全にスキップすることができます.

SDK 3.0 以降、iPhone の GPS 機能を簡単に使用できますが、Google のマップの使用は明示的に禁止されています。これには 2 つの意味があると思います。

1. マップは自分で用意する必要があります
2. 最短ルートを自分で計算する必要があります。

最短経路の計算は長年数学者を困惑させてきましたが、Tom Tom と Google の両方が素晴らしい仕事をしているので、その問題は解決されたようです。私自身は数学者ではありませんが、ネットで検索していると、 Dijkstra Algorithmに出くわしました。このアルゴリズムを iPhone のマップのようなアプリでうまく使用した人はいますか? 私/コミュニティと共有してもよろしいですか？これは正しいアプローチですか、それとも他のオプションですか? ご検討いただきありがとうございます。

これは学校のプロジェクト用です。私は膨大な量の問題に直面しており、理解できる解決策が見つからないようです。

それが二次元配列です。したがって、a、b、e、d、z = 7、および (a、b) = (b、a) からの最短パスを見つけたい場合は、新しい行に移動して、行の隣接するパス

この例でダイクストラのアルゴリズムを実装するのを手伝ってくれる人はいますか? 本当にありがたいです。（私は配列が一番好きなようですが、マップとセットは少し混乱しますが、リストは扱いやすいですが、この時点であらゆる種類の解決策を検討したいと思っています）

[少なくとも、ネットから情報源を盗んでいるだけではありません。本当はこういうことを学びたいのですが… なかなか難しいです(>.<)]

あ、始点がAで終点がZ

ほとんどの人と同じように、アルゴリズムの概念が難しいとは思いません。コーディングを正しく行う方法がわかるだけです...助けてください。

サンプル コード -- 友人がこれを大いに助けてくれました (ただし、従うのが難しいと思われるデータ構造でいっぱいですが)、dreamincode.net/forums/blog/martyr2/index.php? showentry=578 を Java に入力しましたが、うまくいきませんでした ...

時々やや研ぎ澄まされる可能性のあるエドガー・ダイクストラ（彼は「数学者の王子であるが、やや臆病者でもあるカール・フリードリヒ・ガウス」と呼んだ）は、エッセイで「コンピューティング科学を実際に教えることの残酷さについて」（EWD1036）と述べた。

これらの現象の多くは、「ソフトウェアエンジニアリング」という名前でバンドルされています。経済学は「悲惨な科学」として知られているので、ソフトウェアエンジニアリングは「運命の規律」として知られるべきであり、その目標は自己矛盾しているため、その目標に近づくことさえできないために運命づけられています。もちろん、ソフトウェアエンジニアリングは別の価値のある原因として現れますが、それは洗眼剤です。その文献を注意深く読み、その信者が実際に何をしているのかを分析すると、ソフトウェアエンジニアリングがその憲章として受け入れられていることがわかります。 。」。

これは本当ですか？