Schrift
Start · Board · Anwendungen/Programme/Skripte in Perl · Allgemeines zu Perl
[thread]11137[/thread]

Masyu Algorithmus (Seite 3)



<< |< 1 2 3 4 >| >> 31 Einträge, 4 Seiten
KurtZ
 2008-01-17 21:05
#104869 #104869
User since
2007-12-13
411 Artikel
BenutzerIn
[default_avatar]
Hi
pktm+2008-01-17 19:24:55--

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.


Statt Legosteinchen könnte man auch sagen das Abstraktionslevel ist höher, meine Programmierlatte ist ähnlich vielleicht mehr Assembler- und Scriptlastig.

Als Laie wundert mich das Haskell nicht zur Linguistik taugen soll, das geLispel hab ich im Emacs hassen gelernt, besonders die Klammerei. AFAIK kommt von Haskell ein wesentlicher Einfluss zu Perl6 rüber, vielleicht kannst du dich ja eines Tages von dem Sprachfehler befreien! :)

EDIT: machst du auch NLP?
TMTOWTDYOG (there's more than one way to dig your own grave)
pktm
 2008-01-17 21:39
#104872 #104872
User since
2003-08-07
2921 Artikel
BenutzerIn
[Homepage]
user image
KurtZ+2008-01-17 19:51:08--
Helfen die Überlegungen? :)


Ja, insbesondere die Optimierungsmöglichkeiten :)

Unser Ansatz (Arbeitsgruppe...) sieht so ähnlich aus, nur dass ich nicht immer nur ein Teilstück in die Pfadbeschreibung aufnehme wie bei dir in c1:
Quote
c1. Widerspruchsfrei => Nachbarn als aktuelle Zelle auswählen, Teilstrecke erweitern.


Ich schaue in das nächste (Nachbar-)Feld und wenn:
a) es leer ist ziehe ich auf gut Glück dort eine Linie rein (Fehler werden übers Backtracking behandelt, da dann ja einfach ein anderer Weg eingeschlagen wird)
b) eine Kugel drin ist errechne ich den Vektor, der von der Regel ener entsprechenden Kugel beschrieben wird und prüfe dann, ob das, was ich bereits als Pfad habe, auf den Vektor passt (bzw, umgekehrt, je nach Fall) und zeichne dann den kompletten Vektor ein.
Dann gibts Rekutsion.

Zu beachten ist dabei, dass im voraus eingezeichnete Pfade, was durchaus vorkommen kann, da der Algorithmus zwar nu Felderweise vorgeht, aber mehr als die Verbindung zwischen zwei Feldern als Pfad eintragen kann. auch Berücksichtigt werden müssen.

Wenn ich mir das richtig überlegt habe beschneidet das den Suchbaum. Hoffentlich wird das nicht durch diesen lookahead den ich manchmal machen muss wieder ausgeglichen. Außerdem muss man prüfen, ob auf dem Pfad, der eingetragen wird andere Kugeln liegen, und ob deren Vektoren auch passen.

Nun, Freitag ists feritg, dann kann ich es ja mal hier posten.

Grüße, pktm

PS: welches NLP meinst du?
http://www.intergastro-service.de (mein erstes CMS :) )
KurtZ
 2008-01-17 22:15
#104874 #104874
User since
2007-12-13
411 Artikel
BenutzerIn
[default_avatar]
pktm+2008-01-17 20:39:00--

Ich schaue in das nächste (Nachbar-)Feld und wenn:
a) es leer ist ziehe ich auf gut Glück dort eine Linie rein (Fehler werden übers Backtracking behandelt, da dann ja einfach ein anderer Weg eingeschlagen wird)
b) eine Kugel drin ist errechne ich den Vektor, der von der Regel ener entsprechenden Kugel beschrieben wird und prüfe dann, ob das, was ich bereits als Pfad habe, auf den Vektor passt (bzw, umgekehrt, je nach Fall) und zeichne dann den kompletten Vektor ein.
Dann gibts Rekutsion.


verstehe ich nicht ganz aber Freitag (nächste Woche?) gibts ja eine Demo in Perl ;)
Du machst eine Tiefen- statt Breitensuche??? (wenn man nur irgendeine statt der kürzesten Lösung will durchaus vertretbar)


pktm+2008-01-17 20:39:00--
Wenn ich mir das richtig überlegt habe beschneidet das den Suchbaum. Hoffentlich wird das nicht durch diesen lookahead den ich manchmal machen muss wieder ausgeglichen. Außerdem muss man prüfen, ob auf dem Pfad, der eingetragen wird andere Kugeln liegen, und ob deren Vektoren auch passen.


ähm fang lieber einfach an und optimiere später.

Was ich hasse, ist wenn die Aufgabenstellung keinen Aussage über die Komplexität der Aufgaben macht und Zeitvorgaben macht. Das führt nur dazu sich zu Tode zu optimieren.

Ich hatte unlängst einen Algo um Labyrinte dynamisch widerspruchsfrei zu bauen ( der User wurde gezwungen immer alle Zellen zu durchlaufen egal wie er sich bei Abzweigungen entschied.)

Auch diese Überlegungen kann man zur Überschneidungsfreiheit einfließen lassen, aber wie gesagt, ist OVERHEAD für kleine Aufgaben.


pktm+2008-01-17 20:39:00--
PS: welches NLP meinst du?


ähm ... Selbsthypnose liegt bei Computerlinguisten nahe ... ;-)

"Natural Language Processing" dachte ich, allerdings wenn deine AG leiber Masyu spielt ... *fg*
TMTOWTDYOG (there's more than one way to dig your own grave)
pktm
 2008-01-17 22:35
#104876 #104876
User since
2003-08-07
2921 Artikel
BenutzerIn
[Homepage]
user image
Hrhr, nein wir machen KI bei den Infos.
Die Aufgabestellung ist übrigens recht Präzise und weist das Rätsel als NP-vollständig aus. Gesucht sind alle Lösungen eines Rätsels. Der zeiteffizienteste Algo ergibt einen Bonus auf die Klausurnote, aber das haben wir aufgegeben weil unser Algo nicht lief. So direkt als Optimierung des Suchbaumes war das mit dem lookahead auch gar nicht gedacht, es war nur unter den ersten Dingen die uns in denn Sinn kamen. Aber praktisch wäre es, wenn der Suchraum dadurch beschnitten würde. Zur Zeit macht er eher das Gegenteil, er führt irgendwo in eine Endlosschleife :-S
Ich hasse trace...
http://www.intergastro-service.de (mein erstes CMS :) )
KurtZ
 2008-01-18 01:23
#104879 #104879
User since
2007-12-13
411 Artikel
BenutzerIn
[default_avatar]
schade würd mich reizen aber muss mich grad um dringenderes kümmern, und Klausurpunkte bringen mir nix. 8-)

Sag mal durch wie groß das typische Feld sein soll und wieviele Kugeln es haben soll.
TMTOWTDYOG (there's more than one way to dig your own grave)
pktm
 2008-01-18 01:32
#104880 #104880
User since
2003-08-07
2921 Artikel
BenutzerIn
[Homepage]
user image
Eine Größenbeschränkung gibt es nicht, es muss halt mind. 3x3 Felder groß sein.
Hier sind die Testfelder aus der Aufgabenstellung:

Code: (dl )
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
puzzle(1,
       [f(1,1,e),f(1,2,e),f(1,3,b),
        f(2,1,e),f(2,2,e),f(2,3,e),
        f(3,1,e),f(3,2,e),f(3,3,e)]).
puzzle(2,
       [f(1,1,e),f(1,2,e),f(1,3,e),
        f(2,1,e),f(2,2,w),f(2,3,e),
        f(3,1,e),f(3,2,e),f(3,3,e)]).
puzzle(3,
       [f(1,1,e),f(1,2,e),f(1,3,e),
        f(2,1,e),f(2,2,b),f(2,3,e),
        f(3,1,e),f(3,2,e),f(3,3,e)]).
puzzle(4,
       [f(1,1,e),f(1,2,e),f(1,3,e),
        f(2,1,e),f(2,2,e),f(2,3,e),
        f(3,1,w),f(3,2,e),f(3,3,e)]).
puzzle(5,
       [f(1,1,e),f(1,2,e),f(1,3,e),
        f(2,1,w),f(2,2,w),f(2,3,w),
        f(3,1,e),f(3,2,e),f(3,3,e)]).
puzzle(6,
       [f(1,1,e),f(1,2,e),f(1,3,e),f(1,4,e),f(1,5,e),
        f(2,1,e),f(2,2,b),f(2,3,e),f(2,4,b),f(2,5,e),
        f(3,1,e),f(3,2,e),f(3,3,e),f(3,4,e),f(3,5,e),
        f(4,1,w),f(4,2,e),f(4,3,e),f(4,4,e),f(4,5,e),
        f(5,1,e),f(5,2,e),f(5,3,e),f(5,4,e),f(5,5,b)]).
puzzle(7,
       [f(1,1,b),f(1,2,e),f(1,3,e),f(1,4,e),f(1,5,e),
        f(2,1,e),f(2,2,e),f(2,3,e),f(2,4,w),f(2,5,e),
        f(3,1,e),f(3,2,e),f(3,3,e),f(3,4,e),f(3,5,w),
        f(4,1,e),f(4,2,w),f(4,3,w),f(4,4,e),f(4,5,e),
        f(5,1,e),f(5,2,e),f(5,3,b),f(5,4,e),f(5,5,e)]).
puzzle(8,
       [f(1,1,e),f(1,2,e),f(1,3,w),f(1,4,e),f(1,5,e),f(1,6,e),
        f(2,1,w),f(2,2,e),f(2,3,e),f(2,4,e),f(2,5,e),f(2,6,b),
        f(3,1,e),f(3,2,e),f(3,3,e),f(3,4,e),f(3,5,e),f(3,6,e),
        f(4,1,e),f(4,2,e),f(4,3,e),f(4,4,e),f(4,5,e),f(4,6,e),
        f(5,1,b),f(5,2,e),f(5,3,e),f(5,4,e),f(5,5,e),f(5,6,w),
        f(6,1,e),f(6,2,e),f(6,3,e),f(6,4,w),f(6,5,e),f(6,6,e)]).
puzzle(9,
       [f(1,1,e),f(1,2,e),f(1,3,b),f(1,4,e),f(1,5,b),f(1,6,e),f(1,7,e),
        f(2,1,e),f(2,2,e),f(2,3,e),f(2,4,e),f(2,5,e),f(2,6,w),f(2,7,e),
        f(3,1,w),f(3,2,e),f(3,3,e),f(3,4,e),f(3,5,e),f(3,6,e),f(3,7,e),
        f(4,1,e),f(4,2,w),f(4,3,w),f(4,4,w),f(4,5,e),f(4,6,e),f(4,7,e),
        f(5,1,e),f(5,2,e),f(5,3,e),f(5,4,e),f(5,5,e),f(5,6,b),f(5,7,w),
        f(6,1,b),f(6,2,e),f(6,3,e),f(6,4,e),f(6,5,e),f(6,6,e),f(6,7,e),
        f(7,1,e),f(7,2,e),f(7,3,e),f(7,4,w),f(7,5,w),f(7,6,e),f(7,7,e)]).

cycles(1,
       [[c(1,1,1,2),c(1,2,1,3),c(1,3,2,3),c(2,1,1,1),
         c(2,2,2,1),c(2,3,3,3),c(3,2,2,2),c(3,3,3,2)],
        [c(1,1,1,2),c(1,2,1,3),c(1,3,2,3),c(2,1,1,1),
         c(2,3,3,3),c(3,1,2,1),c(3,2,3,1),c(3,3,3,2)],
        [c(1,1,2,1),c(1,2,1,1),c(1,3,1,2),c(2,1,2,2),
         c(2,2,3,2),c(2,3,1,3),c(3,2,3,3),c(3,3,2,3)],
        [c(1,1,2,1),c(1,2,1,1),c(1,3,1,2),c(2,1,3,1),
         c(2,3,1,3),c(3,1,3,2),c(3,2,3,3),c(3,3,2,3)]]).
cycles(2,
       [[c(1,1,1,2),c(1,2,1,3),c(1,3,2,3),c(2,1,1,1),c(2,2,2,1),c(2,3,2,2)],
        [c(1,1,1,2),c(1,2,2,2),c(2,1,1,1),c(2,2,3,2),c(3,1,2,1),c(3,2,3,1)],
        [c(1,1,2,1),c(1,2,1,1),c(1,3,1,2),c(2,1,2,2),c(2,2,2,3),c(2,3,1,3)],
        [c(1,1,2,1),c(1,2,1,1),c(2,1,3,1),c(2,2,1,2),c(3,1,3,2),c(3,2,2,2)],
        [c(1,2,1,3),c(1,3,2,3),c(2,2,1,2),c(2,3,3,3),c(3,2,2,2),c(3,3,3,2)],
        [c(1,2,2,2),c(1,3,1,2),c(2,2,3,2),c(2,3,1,3),c(3,2,3,3),c(3,3,2,3)],
        [c(2,1,2,2),c(2,2,2,3),c(2,3,3,3),c(3,1,2,1),c(3,2,3,1),c(3,3,3,2)],
        [c(2,1,3,1),c(2,2,2,1),c(2,3,2,2),c(3,1,3,2),c(3,2,3,3),c(3,3,2,3)]]).
cycles(3, []).
cycles(4, []).
cycles(5, []).
cycles(6,
       [[c(1,1,1,2),c(1,2,1,3),c(1,3,1,4),c(1,4,1,5),c(1,5,2,5),c(2,1,1,1),
         c(2,2,3,2),c(2,3,2,2),c(2,4,2,3),c(2,5,3,5),c(3,1,2,1),c(3,2,4,2),
         c(3,4,2,4),c(3,5,4,5),c(4,1,3,1),c(4,2,5,2),c(4,3,4,4),c(4,4,3,4),
         c(4,5,5,5),c(5,1,4,1),c(5,2,5,1),c(5,3,4,3),c(5,4,5,3),c(5,5,5,4)],
        [c(1,1,2,1),c(1,2,1,1),c(1,3,1,2),c(1,4,1,3),c(1,5,1,4),c(2,1,3,1),
         c(2,2,2,3),c(2,3,2,4),c(2,4,3,4),c(2,5,1,5),c(3,1,4,1),c(3,2,2,2),
         c(3,4,4,4),c(3,5,2,5),c(4,1,5,1),c(4,2,3,2),c(4,3,5,3),c(4,4,4,3),
         c(4,5,3,5),c(5,1,5,2),c(5,2,4,2),c(5,3,5,4),c(5,4,5,5),c(5,5,4,5)]]).
cycles(7,
       [[c(1,1,1,2),c(1,2,1,3),c(1,3,2,3),c(2,1,1,1),c(2,3,2,4),c(2,4,2,5),
         c(2,5,3,5),c(3,1,2,1),c(3,2,4,2),c(3,3,3,2),c(3,5,4,5),c(4,1,3,1),
         c(4,2,5,2),c(4,3,3,3),c(4,5,5,5),c(5,1,4,1),c(5,2,5,1),c(5,3,4,3),
         c(5,4,5,3),c(5,5,5,4)],
        [c(1,1,2,1),c(1,2,1,1),c(1,3,1,2),c(2,1,3,1),c(2,3,1,3),c(2,4,2,3),
         c(2,5,2,4),c(3,1,4,1),c(3,2,3,3),c(3,3,4,3),c(3,5,2,5),c(4,1,5,1),
         c(4,2,3,2),c(4,3,5,3),c(4,5,3,5),c(5,1,5,2),c(5,2,4,2),c(5,3,5,4),
         c(5,4,5,5),c(5,5,4,5)]]).
cycles(8,
       [[c(1,1,1,2),c(1,2,1,3),c(1,3,1,4),c(1,4,2,4),c(2,1,1,1),c(2,4,2,5),
         c(2,5,2,6),c(2,6,3,6),c(3,1,2,1),c(3,6,4,6),c(4,1,3,1),c(4,6,5,6),
         c(5,1,4,1),c(5,2,5,1),c(5,3,5,2),c(5,6,6,6),c(6,3,5,3),c(6,4,6,3),
         c(6,5,6,4),c(6,6,6,5)],
        [c(1,1,2,1),c(1,2,1,1),c(1,3,1,2),c(1,4,1,3),c(2,1,3,1),c(2,4,1,4),
         c(2,5,2,4),c(2,6,2,5),c(3,1,4,1),c(3,6,2,6),c(4,1,5,1),c(4,6,3,6),
         c(5,1,5,2),c(5,2,5,3),c(5,3,6,3),c(5,6,4,6),c(6,3,6,4),c(6,4,6,5),
         c(6,5,6,6),c(6,6,5,6)]]).
cycles(9,
       [[c(1,3,1,4),c(1,4,1,5),c(1,5,2,5),c(1,6,1,7),c(1,7,2,7),c(2,1,2,2),
         c(2,2,3,2),c(2,3,1,3),c(2,5,3,5),c(2,6,1,6),c(2,7,3,7),c(3,1,2,1),
         c(3,2,4,2),c(3,3,2,3),c(3,4,4,4),c(3,5,3,4),c(3,6,2,6),c(3,7,4,7),
         c(4,1,3,1),c(4,2,5,2),c(4,3,3,3),c(4,4,5,4),c(4,6,3,6),c(4,7,5,7),
         c(5,1,4,1),c(5,2,5,3),c(5,3,4,3),c(5,4,5,5),c(5,5,5,6),c(5,6,4,6),
         c(5,7,6,7),c(6,1,5,1),c(6,2,6,1),c(6,3,6,2),c(6,6,7,6),c(6,7,6,6),
         c(7,3,6,3),c(7,4,7,3),c(7,5,7,4),c(7,6,7,5)],
        [c(1,3,2,3),c(1,4,1,3),c(1,5,1,4),c(1,6,2,6),c(1,7,1,6),c(2,1,3,1),
         c(2,2,2,1),c(2,3,3,3),c(2,5,1,5),c(2,6,3,6),c(2,7,1,7),c(3,1,4,1),
         c(3,2,2,2),c(3,3,4,3),c(3,4,3,5),c(3,5,2,5),c(3,6,4,6),c(3,7,2,7),
         c(4,1,5,1),c(4,2,3,2),c(4,3,5,3),c(4,4,3,4),c(4,6,5,6),c(4,7,3,7),
         c(5,1,6,1),c(5,2,4,2),c(5,3,5,2),c(5,4,4,4),c(5,5,5,4),c(5,6,5,5),
         c(5,7,4,7),c(6,1,6,2),c(6,2,6,3),c(6,3,7,3),c(6,6,6,7),c(6,7,5,7),
         c(7,3,7,4),c(7,4,7,5),c(7,5,7,6),c(7,6,6,6)]]).

Und die Lösungen sind auch gleich dabei (ist ja zum Testen).

Grüße, pktm
http://www.intergastro-service.de (mein erstes CMS :) )
KurtZ
 2008-01-22 16:28
#105024 #105024
User since
2007-12-13
411 Artikel
BenutzerIn
[default_avatar]
hi

besonders clever scheinen deine Kursleiter nicht zu sein, für Aufgabe 1 gibts nur 2 Lösungen,
je zwo der Musterlösungen sind identisch, bzw, ergeben sich durch Wechsel der Richtung!

vergleiche:
Code: (dl )
1
2
3
4
5
6
7
[c(1,1,1,2),c(1,2,1,3),c(1,3,2,3),c(2,1,1,1),
 c(2,2,2,1),c(2,3,3,3),c(3,2,2,2),c(3,3,3,2)],

identisch zu

[c(1,1,2,1),c(1,2,1,1),c(1,3,1,2),c(2,1,2,2),
 c(2,2,3,2),c(2,3,1,3),c(3,2,3,3),c(3,3,2,3)],


statt nur die Kanten zu sortieren, hätten sie auch die Richtung der Kanten normieren sollen.

Bye
Kurt
TMTOWTDYOG (there's more than one way to dig your own grave)
pktm
 2008-01-22 17:22
#105025 #105025
User since
2003-08-07
2921 Artikel
BenutzerIn
[Homepage]
user image
Jaja, das ist schon absicht so. Das Problem ist, dass ich hier die PDF mit den Aufgaben nicht einstellen kann. Da stehen noch ein paar Erläuterungen, so z.B. dass der Algo ja jeden Pfad zweimal findet, einmal in die eine Richtung und einmal in die andere Richtung, und dass man, da wir das sowieso NP-vollständig parsen müssen, die jeweils 2 Lösungen für einen Pfad per Backtracking generieren sollen.
Mal sehen wann ich die Zeit finde die Sache einzustellen.
http://www.intergastro-service.de (mein erstes CMS :) )
KurtZ
 2008-01-22 17:27
#105027 #105027
User since
2007-12-13
411 Artikel
BenutzerIn
[default_avatar]
das kommt auf den "Algo" an, ob er beide Richtungen findet. Und das mit dem np-Vollständig glaub ich erstmal nicht, da sind Viele oft voreilig.

Im übrigen wozu betrachten wir die Komplexität? Anzahl der Kugeln oder Anzahl der Felder? Sollen alle Lösungen gefunden werden oder mindestens eine?
TMTOWTDYOG (there's more than one way to dig your own grave)
pktm
 2008-01-22 17:33
#105029 #105029
User since
2003-08-07
2921 Artikel
BenutzerIn
[Homepage]
user image
Alle Lösungen sollen gefunden werden.
http://www.intergastro-service.de (mein erstes CMS :) )
<< |< 1 2 3 4 >| >> 31 Einträge, 4 Seiten



View all threads created 2008-01-14 13:35.