Problem2 - solve

dripper
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 25. Mär 2009 14:01

Problem2 - solve

Beitrag von dripper »

Hallo,
Ich kann nicht verstehen was wir hier machen sollen.
Wie soll bei der Eingaben 1 und 2 die Ausgabe aussehen.
1.{ "Bob", "Jim" };
2.{ "!Bob", "!Jim" };

Trillium
Windoof-User
Windoof-User
Beiträge: 28
Registriert: 1. Jul 2007 16:05

Re: Problem2 - solve

Beitrag von Trillium »

Ich stelle mir gerade die gleiche Frage.

Ich habe mich mal durch die Testfälle debugt ... also bei {"Bob","Jim"} kommt für Beide true raus. Wenn ich das richtig verstanden habe, bedeutet das, dass Bob und Jim im Team sind. Aber die constraints besagen doch, dass entweder Bob ODER Jim im Team sind und nicht beide Zusammen.

Irgendwie steige ich da nicht durch ...

SecretAgent
Neuling
Neuling
Beiträge: 8
Registriert: 16. Apr 2009 10:18

Re: Problem2 - solve

Beitrag von SecretAgent »

Ich glaube "Bob OR Jim" bedeutet, dass beide doch ausgewaehlt werden darf.

kned
Mausschubser
Mausschubser
Beiträge: 80
Registriert: 14. Okt 2008 18:49
Kontaktdaten:

Re: Problem2 - solve

Beitrag von kned »

liste = "bob" "jim"

truthA = "bob".charat(0) != "!" -> = true
truthB = "jum".charat(0) != "!" -> = true

if( solution.get(agentA) != truthA && solution.get(agentB) != truthB )
fehlgeschlagen

also schlägt der test nur fehl wenn beides false

bei mir läuft mittlerweile alles bis auf :
assertEquals("too many big random constraints rejected", 8, impossible); ... expected 8, is: 11

hab schon alles versucht aber komm net weiter :(

Heap
Erstie
Erstie
Beiträge: 18
Registriert: 28. Apr 2009 20:38

Re: Problem2 - solve

Beitrag von Heap »

Hi,
steig bei dieser Aufgabe nicht ganz hinter die Hinweise.

Habe das soweit verstanden, dass es eine Lösung gibt, wenn das Argument und die Negation davon in verschieden starken Zusammenhangskomonenten sind.

Was ist dann aber eine Lösung?

Denke mir das so:
Schaue in der ersten Komponenten, welche Namen auftauchen,
Bsp.: {Bob, Sally}
und welche negiert auftauchen
Bsp: {!Henry, !Q}
so baue ich dann meine Map auf. Hier also 4 Einträge. (bob--> true, Sally --> true, Henry --false, Q --> false)

In den restlichen Komponenten schaue ich dann nur, ob die Bedingung verletzte ist, dass Argument und Negation vorkommen
Bsp.: Bob und !Bob
und ob es Namen gibt, die in keiner vorherigen Komponenten auftauchen (ist das mit der Priorisierung gemeint?) und trage diese entsprechend in die map?

ab26iget.stud.tu
Mausschubser
Mausschubser
Beiträge: 63
Registriert: 14. Okt 2008 20:19

Re: Problem2 - solve

Beitrag von ab26iget.stud.tu »

Heap hat geschrieben:Hi,
steig bei dieser Aufgabe nicht ganz hinter die Hinweise.

Habe das soweit verstanden, dass es eine Lösung gibt, wenn das Argument und die Negation davon in verschieden starken Zusammenhangskomonenten sind.

Was ist dann aber eine Lösung?

Denke mir das so:
Schaue in der ersten Komponenten, welche Namen auftauchen,
Bsp.: {Bob, Sally}
und welche negiert auftauchen
Bsp: {!Henry, !Q}
so baue ich dann meine Map auf. Hier also 4 Einträge. (bob--> true, Sally --> true, Henry --false, Q --> false)

In den restlichen Komponenten schaue ich dann nur, ob die Bedingung verletzte ist, dass Argument und Negation vorkommen
Bsp.: Bob und !Bob
und ob es Namen gibt, die in keiner vorherigen Komponenten auftauchen (ist das mit der Priorisierung gemeint?) und trage diese entsprechend in die map?
Das verstehe ich auch so ,
wenn (Bob und !Bob) in der selben Komponente sind , dann ist keine Lösung möglich !
ich weiB aber nicht was hat die umgekehrte topologische Reihenfolge hier zu tun ?

dripper
Windoof-User
Windoof-User
Beiträge: 40
Registriert: 25. Mär 2009 14:01

Re: Problem2 - solve

Beitrag von dripper »

ein Beispiel, mit dem es alles klar werden muss.
Mann hat z.B. die Komponente {Bob, Jim, Anna, !Bob}. Wie im Praktikum steht gibt es hier keine Lösung, aber wenn es nur {Katja, Jim, Anna, !Bob} steht dann sind die erste drei wahr und der letzte falsh. Was könnt ihr eigentlich nicht verstehen?

*Hinweis - Versuchen sie nicht immer alles nach den Hinweisen zu implementieren. Versuchen sie zu vergessen was da steht und stellen sie euch vor wie das genau aussehen soll.

Vockilein
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 16. Apr 2009 18:29

Re: Problem2 - solve

Beitrag von Vockilein »

Die Beispiele von dripper sind mir klar. Aber was macht man im Fall

{Bob, Jim, Anna, !Bob} , {Amy, Charles}

Zählen dann alle 5 die true sind zum Team oder nur die ersten drei? Bei mir läuft ausser random und bigtest nur impossible1 noch nicht. Weiß da einer was an dem Test speziell ist?

linn
Mausschubser
Mausschubser
Beiträge: 77
Registriert: 15. Okt 2008 21:16

Re: Problem2 - solve

Beitrag von linn »

Vockilein hat geschrieben:Die Beispiele von dripper sind mir klar. Aber was macht man im Fall

{Bob, Jim, Anna, !Bob} , {Amy, Charles}

Zählen dann alle 5 die true sind zum Team oder nur die ersten drei? Bei mir läuft ausser random und bigtest nur impossible1 noch nicht. Weiß da einer was an dem Test speziell ist?
dann gibst du null aus weil Bob in der selben scc is wie !bob.

Benutzeravatar
glowhand
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 128
Registriert: 23. Okt 2008 22:23
Wohnort: Darmstadt

Re: Problem2 - solve

Beitrag von glowhand »

Kann mal jemand, der die Aufgabe schon gelöst hat seinen Lösungsweg skizzieren? Das wär ne Hilfe um zu sehen was ich vergesse! Danke!
1. Wandle übergebemnen conjstraints in Zusammenhangskomponenten um
2. durchlaufe alle Zusammenhangskomponenten
2.a) durchlaufe Knoten der Zusammenhangskomponente
2.a) a) wenn einzelne Komponente TEAMMITGLIED und gleichzeitig auch !TEAMMITGLIED enthält, gib null zurück
2.b) b) füge das Teammitglied mit entsprechendem Wert (true/false) der Ausgabemap hinzu

Heap
Erstie
Erstie
Beiträge: 18
Registriert: 28. Apr 2009 20:38

Re: Problem2 - solve

Beitrag von Heap »

Hi,
verstehe ich das dann so:
Bei folgenden Zusammenhangskomponenten
{Amy, Bob, Charles}{!Bob,Jim}
habe ich dieses Ergebnis?
Amy - true
Bob - false
Charles - true
Jim - true

Benutzeravatar
m_stoica
Kernelcompilierer
Kernelcompilierer
Beiträge: 473
Registriert: 5. Dez 2008 20:19
Wohnort: Zuhause

Re: Problem2 - solve

Beitrag von m_stoica »

Das hängt von der Reihenfolge ab, in der du die Komponenten durchsuchst.
Du hasdt dass ja jetzt so gemacht, dass du im Falle, dass zwei Komponenten den gleichen Namen haben, du den letzeren Eintrag übernimmst. Das könnte funzen.(Ein Kumpel hat das zumindestens so gemacht). Das hängt halt davon ab wie du die Komponenten sortiert hast. Und wie du iterierst.
In meiner Methode gehe ich rückwärts durch die Komponenten, und wenn dann eine Komponente kommt, die die Gleichen Namen beinhaltet, springe ich zur nächsten Komponente.

Heap
Erstie
Erstie
Beiträge: 18
Registriert: 28. Apr 2009 20:38

Re: Problem2 - solve

Beitrag von Heap »

m_stoica hat geschrieben: In meiner Methode gehe ich rückwärts durch die Komponenten, und wenn dann eine Komponente kommt, die die Gleichen Namen beinhaltet, springe ich zur nächsten Komponente.
springst du zur nächsten Komponente? du meinst wohl eher du gehst zum nächsten Eintrag, sonst würdest du dir doch die restlichen Einträge der Komponente nicht mehr anschauen?
dann würde es aber auf doch das gleiche rauskommen?

ich sortiere die komponenten topologisch.

Es laufen alle Tests bei mir, bis auf einen bei testRandom. da wird ein constraint nicht eingehalten. das aber zu debuggen bei 100 durchläufen wird schwer. sau ärgerlich

robert.n
Nerd
Nerd
Beiträge: 673
Registriert: 29. Sep 2008 19:17

Re: Problem2 - solve

Beitrag von robert.n »

Heap hat geschrieben:
m_stoica hat geschrieben: In meiner Methode gehe ich rückwärts durch die Komponenten, und wenn dann eine Komponente kommt, die die Gleichen Namen beinhaltet, springe ich zur nächsten Komponente.
ich sortiere die komponenten topologisch.

Es laufen alle Tests bei mir, bis auf einen bei testRandom. da wird ein constraint nicht eingehalten. das aber zu debuggen bei 100 durchläufen wird schwer. sau ärgerlich
Bei mir läuft mittlerweile alles bis auf die letzten beiden Tests (testRandom und testBig). Ich glaube ich habe auch schon den Grund gefunden. Genau diese topologische Sortierung der Zusammenhangskomponenten fehlt bei mir. Bis jetzt verwende ich nur eine "halbherzige" topologische Sortierung, die wahrscheinlich bei testRandom/testBig einfach nicht mehr funktioniert.
Ich verstehe schlichtweg nicht, wie ich da jetzt eine _richtige_ topologische Sortierung reinkriegen soll.

Beispiel (aus den Tests):
Bild
Zusammenhangskomponenten sind: {[Jim, Bob], [!Bob, !Jim]}
Nur, wie kriege ich da jetzt im allgemeinen Fall die topologische Sortierung ([!Bob, !Jim], [Jim, Bob]) rein? Im Moment mache ich es noch so, dass ich mit der DFS bei den Knoten mit dem größeren Eingangsgrad anfange (in diesem Falle also bei Jim oder Bob). Würde ich beim ersten DFS-Aufruf stattdessen bei !Bob beginnen, dann würde ich nämlich gleich alle Knoten erwischen, was ja nicht der Sinn der Sache ist.
In diesem konkreten Fall und bei allen kleineren Tests scheint dieses Verfahren zu funktionieren, aber im Allgemeinen eben nicht.

Also wie macht ihr das (mir fallen nur fürchterlich aufwendige Verfahren ein)?

MonkeyT
DON'T PANIC
Beiträge: 42
Registriert: 17. Apr 2009 18:02

Re: Problem2 - solve

Beitrag von MonkeyT »

Ich hab hier noch en Problem:

testTautology übergibt folgendes:
[Bob, !Bob]

Ich dachte jetzt soll null zurückgegeben werden (return null;) aber dann gibts das: "java.lang.NullPointerException"
Komisch, naja, einfach nur nix zurück geben wie bei testempty (also {}) hat das als Ergebnis: "Bob is missing from solution"
hä?!?

wenn ich {Bob=false} zurück geben wird der Test grün... Warum?

Antworten

Zurück zu „Archiv“