Heuristik für gleitende Kachel Problem

Question

Die Idee ist, alle die richtigen Elemente in die linke und die linke in die rechte mit einem leeren Raum in der Mitte zu bewegen. Die Elemente können entweder Sprung über ein oder zwei Stücke in einen leeren Raum.

LLL[ ]RRR

Ich versuche, eine Heuristik für diese Aufgabe zu denken. Ist die Heuristik eine mögliche Lösung zu finden, unterstützen bedeutet oder tatsächlich eine Anzahl von Zügen als die Lösung zurückkehren? Wie würde ich ausdrücken, eine solche Heuristik?

Answer 1

Klingt wie Sie ein wenig verwirrt darüber, was eine Heuristik ist.

Eine grobe Definition ist „eine vereinfachenden Annahme“ oder „eine anständige guess“

Zum Beispiel, sagen wir, Sie ein Basketball-Team setzen müssen zusammen, und Sie haben Blätter auf Menschen, die diese Liste ihre Kontaktdaten, Geburtsdatum und Höhe spielen möchten. Sie könnten tryouts halten, wo Sie jeden Kandidaten spezifische Fähigkeiten zu testen; das würde erfordern in allen Kandidaten zu bringen, aber, und dass eine lange Zeit in Anspruch nehmen könnte. Sie verwenden eine Heuristik, die Suche einzuschränken -. Nur Leute nennen, die mindestens 6'2" hoch sind Dies könnten einige großen Basketball-Spieler ignorieren, aber es ist eine recht ordentliche Vermutung

.

Ein weiteres Beispiel einer Heuristik: Sie versuchen, die kleinste Anzahl von Münzen zu verwenden, um eine Rechnung zu bezahlen. Die Heuristik (eine Vereinfachung Ansatz) ist die Münze mit dem größten Wert zu wählen (die kleiner als die restlichen Rechnung ist) zuerst, subtrahieren Sie den Wert aus der Rechnung, und wiederholt. Dies ist nicht garantiert jedes Mal arbeiten, aber es wird Sie an die richtige Nachbarschaft die meiste Zeit bekommen.

Eine Heuristik für Ihr Problem könnte sein, „nie Ls nach rechts zu bewegen, und nie Rs nach links bewegen.“ - es engt den „Suchraum“ alle möglichen Züge durch einige der Möglichkeiten von vornherein eliminiert

Answer 2

Sie suchen nach einem heuristischen oder einem Algorithmus? Eine Heuristik kann oder kann nicht ein bestimmtes Problem lösen. Es ist wirklich nur soll Sie in die Richtung zeigen, dass die Lösung liegt wahrscheinlich in. Ein Algorithmus wirklich ein bestimmtes Problem lösen sollte.

Answer 3

Eine Heuristik ist in der Regel ein „Hinweis“, die in der Regel (aber nicht immer) der Prozedur in die richtige Richtung führen. Mit Heuristik beschleunigt das Verfahren (Ihre Algorithmen), wieder, in der Regel , aber nicht immer. Es ist wie eine „Beratung“ für den Algorithmus, der oft richtig mehr ist als nicht.

Ich bin mir nicht sicher, was Sie suchen, da die Beschreibung ein wenig vage. Wenn Sie den Algorithmus wollen, müssen Sie studieren, welche Auswirkungen eine bestimmte Bewegung auf die aktuelle Situation haben wird und einen Weg nach vorn für alle möglichen Bewegungen jedes Mal zu dem Schritt, in der Tat einen Baum von Zuständen durchlaufen (dh. Staaten, die sich entwickeln, wenn Suchen Sie eine bestimmte Abfolge von Bewegungen).

Sie können auch sehen, dass es möglicherweise Angelegenheiten , wie nah ist die aktuelle Position zu dem, was Sie (Ihre gewünschte Endposition) .So statt Berechnung alle möglichen Pfade von Ihrem ursprünglichen Zustand erreichen wollen, bis Sie den Endzustand finden Sie Ihren Algorithmus basiert auf der Heuristik „wie nah ist der aktuelle Zustand in den gewünschten“ führen kann und nur einen Teil des Baumes durchqueren.