目標は、タイルが自然な位置に表示されるようにタイルを再配置することです。一度にスライドできるタイルは1つだけです。パズルの各可能な状態は、検索グラフのノードです。
h（x）関数では、すべてのタイルにわたって、目標状態からのタイルの転位の合計を使用しています。上の画像では、5は位置0,0にあり、位置1,0に属しているため、h（x）関数に1を与えます。次のタイルは11で、0,1にあり、2,2に属しているため、h（x）に3を寄与します。等々。編集：私は今、これが彼らが「マンハッタン距離」または「タクシー距離」と呼んでいるものであることを理解しています。
私はg（x）のステップカウントを使用しています。私の実装では、状態グラフ内の任意のノードについて、gは前のノードのgからちょうど+1です。
連続するノードを見つけるために、パズルの「穴」をどこに移動できるかを調べます。表示されるパズルの状態（別名ノード）には3つの隣接点があります。穴は北、西、または東に移動できます。
私のA*検索は、20秒、180秒でソリューションに収束する場合もあれば、まったく収束しない場合もあります（10分以上待機）。hは妥当だと思います。gを適切にモデル化したかどうか疑問に思います。言い換えると、私のA *関数が最短経路ではない経路を経由してグラフ内のノードに到達している可能性はありますか？
たぶん私は十分長く待っていませんでしたか？たぶん10分では十分ではありませんか？
完全にランダムな配置の場合（パリティの問題がないと仮定）、A *ソリューションが調べる順列の平均数はいくつですか？（数学を見せてください）
コード内の論理エラーを探しますが、それまでの間、ヒントはありますか？
（ps：それはJavascriptで行われます）。
また、いいえ、これはCompSciの宿題ではありません。それは単なる個人的な探求です。私はJavascriptを学ぼうとしています。
編集：実行時間はヒューリスティックに大きく依存していることがわかりました。誰かが言及した記事からヒューリスティックに適用される10倍の係数を見たのですが、なぜ10倍なのか疑問に思いました。なぜ線形なのですか？これはjavascriptで行われるため、コードを変更して、現在検討中のノードでhtmlテーブルを動的に更新できます。これにより、アルゴリズムの進行中にアルゴリズムを確認することができました。通常のタクシー距離ヒューリスティックで、収束に失敗するのを観察しました。
一番上の列には5と12があり、彼らはぶらぶらし続けました。1、2、3、4が一番上の行に忍び寄るのが見えますが、その後はドロップアウトし、他の数字はそこに移動します。私が見たかったのは、1、2、3、4のようなものが上に忍び寄り、そこにとどまっていることでした。
私は自分自身に思いました-これは私がこれを個人的に解決する方法ではありません。これを手動で行うことで、一番上の行、次に2番目の行、次に3番目と4番目の行を同時に解決します。
そこで、h（x）関数を微調整して、上位の行と「左側の」列にさらに大きな重みを付けました。その結果、A*ははるかに速く収束しました。「無期限」ではなく、3分で実行されるようになりました。私が話した「覗き見」で、小さい数字が高い列に忍び寄り、そこにとどまるのを見ることができます。これは正しいことのように見えるだけでなく、はるかに高速に実行されます。
私はたくさんのバリエーションを試しているところです。A*ランタイムがヒューリスティックに非常に敏感であることはかなり明らかなようです。現在、私が見つけた最高のヒューリスティックは dislocation * ((4-i) + (4-j))、iとjが行と列であり、転位がタクシーの距離である場所の合計を使用しています。
私が得た結果の興味深い部分の1つは、特定のヒューリスティックを使用すると、パスを非常にすばやく見つけることができますが、それは明らかに最短パスではありません。これは、ヒューリスティックに重み付けしているためだと思います。あるケースでは、10秒で178ステップのパスを取得しました。私自身の手作業は87回の動きで解決策を生み出します。（10秒以上）。さらなる調査が必要です。
その結果、収束が速くなる必要があり、パスは間違いなく最短ではありません。これについてもっと考えなければなりません。
コード：
var stop = false;
function Astar(start, goal, callback) {
// start and goal are nodes in the graph, represented by
// an array of 16 ints. The goal is: [1,2,3,...14,15,0]
// Zero represents the hole.
// callback is a method to call when finished. This runs a long time,
// therefore we need to use setTimeout() to break it up, to avoid
// the browser warning like "Stop running this script?"
// g is the actual distance traveled from initial node to current node.
// h is the heuristic estimate of distance from current to goal.
stop = false;
start.g = start.dontgo = 0;
// calcHeuristic inserts an .h member into the array
calcHeuristicDistance(start);
// start the stack with one element
var closed = []; // set of nodes already evaluated.
var open = [ start ]; // set of nodes to evaluate (start with initial node)
var iteration = function() {
if (open.length==0) {
// no more nodes. Fail.
callback(null);
return;
}
var current = open.shift(); // get highest priority node
// update the browser with a table representation of the
// node being evaluated
$("#solution").html(stateToString(current));
// check solution returns true if current == goal
if (checkSolution(current,goal)) {
// reconstructPath just records the position of the hole
// through each node
var path= reconstructPath(start,current);
callback(path);
return;
}
closed.push(current);
// get the set of neighbors. This is 3 or fewer nodes.
// (nextStates is optimized to NOT turn directly back on itself)
var neighbors = nextStates(current, goal);
for (var i=0; i<neighbors.length; i++) {
var n = neighbors[i];
// skip this one if we've already visited it
if (closed.containsNode(n)) continue;
// .g, .h, and .previous get assigned implicitly when
// calculating neighbors. n.g is nothing more than
// current.g+1 ;
// add to the open list
if (!open.containsNode(n)) {
// slot into the list, in priority order (minimum f first)
open.priorityPush(n);
n.previous = current;
}
}
if (stop) {
callback(null);
return;
}
setTimeout(iteration, 1);
};
// kick off the first iteration
iteration();
return null;
}