pktm+2008-01-15 23:03:17--

Ist aber in Prolog.

Arbeitest du zufällig mit AI::Prolog?

Interessiert Dich das Modul?

renee+2008-01-15 23:19:12--

Interessiert Dich das Modul?

Ja, auch wenn mir aktuell Prolog noch etwas esoterisch wirkt. Geht in Richtung deklarative Programmierung, oder?

Ronnie+2008-01-15 23:15:53--

pktm+2008-01-15 23:03:17--

Ist aber in Prolog.

Arbeitest du zufällig mit AI::Prolog?

Nein, ich arbeite mit SWI Prolog, ohne Perl :)

pktm+2008-01-15 23:03:17--

Wer will kann mir ne PM mit seiner eMail-Adresse schreiben und bekommt dann die Aufgabenstellung aus meinem Info-Kurs.
Ist aber in Prolog.

Wenns jetzt nur um Hilfe für deinen Prolog-Kurs geht, bist du hier denke ich falsch.
Eine Algo in Perl wird IMHO radikal anders aussehen als in Prolog, weil das Instrumentarium sich wesentlich unterscheidet.

Die angesprochenen Lösungstrategieen in http://www.janko.at/Raetsel/Masyu/Regeln.htm sollten dir weiterhelfen.

Doppelpost durch Änderung. Sehr dubioser Bug...

pktm+2008-01-17 00:26:57--

KurtZ+2008-01-16 01:40:33--

pktm+2008-01-15 23:03:17--

Wer will kann mir ne PM mit seiner eMail-Adresse schreiben und bekommt dann die Aufgabenstellung aus meinem Info-Kurs.
Ist aber in Prolog.

Wenns jetzt nur um Hilfe für deinen Prolog-Kurs geht, bist du hier denke ich falsch.
Eine Algo in Perl wird IMHO radikal anders aussehen als in Prolog, weil das Instrumentarium sich wesentlich unterscheidet.

Die angesprochenen Lösungstrategieen in http://www.janko.at/Raetsel/Masyu/Regeln.htm sollten dir weiterhelfen.

Nein, es geht mir nicht ausschließlich um Hilfe zu meinem Prolog-Kurs, ich hätte mir nur gerne mal einen Algorithmus dazu angesehen. Dass der dann in Perl wäre liegt daran, dass Perl eines meiner Hobbies ist, und ich hier danach gefragt habe (und nicht in einem Prlolg-Forum).
Schadet es denn, wenn man sich eine radikal andere Lösung ansieht?

pktm+2008-01-17 00:28:26--

Schadet es denn, wenn man sich eine radikal andere Lösung ansieht?

Wenn es die primäre Zielsetzung ist Prolog zu erlernen, definitiv JA!

Das sind komplett verschiedenen Paradigmen. Grob gesprochen, was hilft es dir eine Modellbau-Aufgabe mit Streichhölzern zu lösen, wenn sie auf Legosteine ausgelegt ist? Legosteine kann man weder kürzen noch kleben, sie lassen sich auch nur in einer Richtung kombinieren!

Aber für eine bestimmte Problemklasse sind Legosteine viel praktischer als Streichhölzer! Die Gefahr bestünde dass du versuchst das Streichholzmodell mit Legosteinen nachzubauen.

In Prolog konzentrierst du dich eher darauf die Kriterien einer Lösung und Suchraum (K)-Intelligent zu beschreiben und der konkrete Suchalgo ist eher eine Blackbox (und eher langsam). Ich bezweifle das die Aufgabenstellung für dein Testat deswegen eine hohe Rechenkomplexität haben wird, dafür wird dein Prolog-Programm dann auch knackiger und KI-näher sein als in Perl. (Lego vs Streichholz) [1]

Als Perlfreak würde mich aber eher reizen durch geschicktes Algo-Tuning ein Masyu-Problem hoher Rechenkomplexität zu knacken und möglichst nahe an die Performance eines vergleichbaren C-Programms zu kommen. (Streichholzmodelle kommen dem Original näher als Lego)

Außerdem würden ich mich heutzutage auch eher für Haskell interessieren, insbesondere wg des Einflusses auf Perl6.

Ciao
Kurt

[1] Meine letzte Prologerfahrungen stammen noch aus Atari ST Zeiten, wahrscheinlich sind die internen Suchalgos seit damals deutlich besser geworden, ausschließen kann ich es nicht.

PS: wen's interessiert -> wiki/Prolog

KurtZ+2008-01-17 15:34:37--

pktm+2008-01-17 00:28:26--

Schadet es denn, wenn man sich eine radikal andere Lösung ansieht?

Wenn es die primäre Zielsetzung ist Prolog zu erlernen, definitiv JA!

Das sind komplett verschiedenen Paradigmen. Grob gesprochen, was hilft es dir eine Modellbau-Aufgabe mit Streichhölzern zu lösen, wenn sie auf Legosteine ausgelegt ist? Legosteine kann man weder kürzen noch kleben, sie lassen sich auch nur in einer Richtung kombinieren!

Aber für eine bestimmte Problemklasse sind Legosteine viel praktischer als Streichhölzer! Die Gefahr bestünde dass du versuchst das Streichholzmodell mit Legosteinen nachzubauen.

In Prolog konzentrierst du dich eher darauf die Kriterien einer Lösung und Suchraum (K)-Intelligent zu beschreiben und der konkrete Suchalgo ist eher eine Blackbox (und eher langsam). Ich bezweifle das die Aufgabenstellung für dein Testat deswegen eine hohe Rechenkomplexität haben wird, dafür wird dein Prolog-Programm dann auch knackiger und KI-näher sein als in Perl. (Lego vs Streichholz) [1]

Als Perlfreak würde mich aber eher reizen durch geschicktes Algo-Tuning ein Masyu-Problem hoher Rechenkomplexität zu knacken und möglichst nahe an die Performance eines vergleichbaren C-Programms zu kommen. (Streichholzmodelle kommen dem Original näher als Lego)

Außerdem würden ich mich heutzutage auch eher für Haskell interessieren, insbesondere wg des Einflusses auf Perl6.

Ciao
Kurt

[1] Meine letzte Prologerfahrungen stammen noch aus Atari ST Zeiten, wahrscheinlich sind die internen Suchalgos seit damals deutlich besser geworden, ausschließen kann ich es nicht.

PS: wen's interessiert -> wiki/Prolog

Ja nö, nach den zwei Prologkursen (Sehr gut & gut) und nach sieben Semestern Computerlinguistik und dem LSIP-Kurs, der ebenfalls eine andere Art der Programmierung vermittelt (mit gut abgeschlossen) habe ich definitiv nicht mehr das Ziel Prolog zu erlernen ;)
Das Legostein-Steichhölzchen-Beispiel gefällt mir allerdings, das merker ich mir.

Durchaus ist es auch interessant was du so alles machen wollen würdest - Gott sei Dank bist du nicht ich, sonst wüsste ich nicht mehr, wohin mit der Zeit :) Nach Prolog, LISP, Perl, C++, Java, VBA, Pascal, Delphi und anderen dubiosen Dingen (es gibt ja auch noch TXL und Konsorten) jetzt auch noch mit Haskell anzufangen wäre wohl wirklich ein bischen viel. Außerdem kann man das in der Computerlinguistik, in dem Bereich den ich mache, nicht gebrauchen.

Grüße, pktm

mal ein grober Algo-Entwurf ohne Optimierung:

1. die Zellen des Spielfelds und des Außenrandes als 2D-Array darstellen.

2. Jede Zelle kann 7 verschiende Zustände einnehmen, 2 gerade, 4 gebogene oder gar kein Streckenstück.

3. Jede Zelle kann diverse Neben-Bedingungen haben, die erlaubte Zustände einschränken:
a) Weißer Punkt =>muss ein gerades Streckenstück beinhalten, mind. ein verbundener Nachbar gebogen
b) Scharzer Punkt => muss gebogenes Streckenstück beinhalten, kein verbundener Nachbar gebogen
c) kein Punkt
d) liegt außerhalb

4. Die erlaubten Zustände einer Zelle werden zusätzlich (nur) von den Bedingungen und Zuständen der vier Nachbarzellen beeinflusst.

5. Baumsuche:
a. Einen Punkt als Start auswählen.
b. in aktueller Zelle erlaubten Zustand ausprobieren.(evt. Backtrack auf frühere Zelle)
c. auf Widerspruchsfreiheit mit Nachbarn überprüfen
c1. Widerspruchsfrei => Nachbarn als aktuelle Zelle auswählen, Teilstrecke erweitern.
c2. Widerspruch => Zustand streichen, weiter mit =>b
d. Falls Nachbar gleich Startpunkt, überprüfen ob alle Schwarzen und Weißen Punkte durchlaufen wurden.
d1. Nein => b
d2 Ja => Fertig.


Dieser Brute-Force Ansatz dürfte für einfache Beispiele reichen ...

Optimierungsmöglichkeiten:
1. Die möglichen Teilgraphen für zusammenhängende Gebiete mit mehreren S/W-Punkten oder Außenpunkten vorkalkulieren.
2. Bei der Auswahl des nächsten Nachbarn immer priorisiert am Rand langlaufen.
3. Teilstrecken die bestimmte s/w-Punkte isolieren frühzeitig erkennen und zum Backtracken nutzen.
4. Aufwendige Tests durch Tabellenzugriffe realisieren (Rechenkomplexität mit Speicherkomplexität ersetzen). Z.B lassen sich alle erlaubten Zustände und Bedingungen einer Zelle als Bits realisieren, die Implikation auf Nachbarzellen ließen sich wiederum als Bitmaske aus einer Tabelle ablesen, statt aufwendige if/then konstrukte zu durchlaufen.


Helfen die Überlegungen? :)