|
|
|
|
Sag nächstes Mal Bescheid, wenn du in der Nähe bist
|
|
|
|
|
|
|
Hatte nicht viel Zeit, leider. 2 Hotels, 4 Unis und 1600 Kilometer in 3 Tagen.
+ ich hatte meinen Vater mit
|
|
|
|
|
|
|
| Zitat von Kambfhase
Karlsruhe
| |
informatik? ich werd auch mal ne bewerbung hinschicken ...
|
|
|
|
|
|
|
|
|
|
|
| Zitat von Renga
| Zitat von Kambfhase
Karlsruhe
| |
informatik? ich werd auch mal ne bewerbung hinschicken ...
| |
Muss man sich da bewerben? In Saarbrücken gibts keine Beschränkungen und man kann sich einfach einschreiben.
|
|
|
|
|
|
|
Mein ich doch
|
|
|
|
|
|
|
In Münster muss man sich richtig bewerben. Dort ist Info beschränkt.
Statistik
163 haben sich beworben
57 sind angenommen worden
2 haben sich eingeklagt
|
|
|
|
|
|
|
Kann mir einer einen Algorithmus erstellen?
Ich möchte bei einem Graphen die Knoten so einfärben, dass nie zwei verbundene Knoten "schwarz" sind. Es gibt nur die Zustände "schwarz" und "weiß".
Allerdings will ich den Graphen nicht nur irgendwie einfärben, sondern die maximale Zahl an schwarzen Knoten erreichen.
Zudem sind Näherungswerte unerwünscht. Nur das exakte Maximum ist sinnvoll.
Hat einer da was auf Lager? Vllt. ein Informatik-Student?
Mit fragenden Grüßen, Hase
ps. sollte ich das vllt im Gerhirnsalat oder so nochmal posten/ zitieren?
|
|
|
|
|
|
|
|
|
|
|
Ich glaub, dass sollte ein Bahnhof werden. hmm.
|
|
|
|
|
|
|
| Zitat von Kambfhase
Kann mir einer einen Algorithmus erstellen?
Ich möchte bei einem Graphen die Knoten so einfärben, dass nie zwei verbundene Knoten "schwarz" sind. Es gibt nur die Zustände "schwarz" und "weiß".
Allerdings will ich den Graphen nicht nur irgendwie einfärben, sondern die maximale Zahl an schwarzen Knoten erreichen.
Zudem sind Näherungswerte unerwünscht. Nur das exakte Maximum ist sinnvoll.
Hat einer da was auf Lager? Vllt. ein Informatik-Student?
Mit fragenden Grüßen, Hase
ps. sollte ich das vllt im Gerhirnsalat oder so nochmal posten/ zitieren? | |
Wenn du Knoten abwechselnd einfärben willst, sollte der Modulo dir helfen...
|
|
|
|
|
|
|
| Zitat von Kambfhase
Kann mir einer einen Algorithmus erstellen?
Ich möchte bei einem Graphen die Knoten so einfärben, dass nie zwei verbundene Knoten "schwarz" sind. Es gibt nur die Zustände "schwarz" und "weiß".
Allerdings will ich den Graphen nicht nur irgendwie einfärben, sondern die maximale Zahl an schwarzen Knoten erreichen.
Zudem sind Näherungswerte unerwünscht. Nur das exakte Maximum ist sinnvoll.
Hat einer da was auf Lager? Vllt. ein Informatik-Student?
Mit fragenden Grüßen, Hase
ps. sollte ich das vllt im Gerhirnsalat oder so nochmal posten/ zitieren?
| |
Leider nicht genug spezifiziert..
Um was für Graphen handelt es sich denn? Die Knotenverbindungen bestehen bereits? Oder soll der Graph durch den Algo mit aufgespannt werden? Sprich es existieren nur die Knoten oder bereits der gesamte Graph mit Knoten und Kanten? Gerichtet? Ungerichtet? Zyklisch? usw.
Mal als kleiner Denkanstoß, ohne wirklich viel Infos zu haben:
Knoten und Kanten vorhanden ungerichtet/gerichtet:
Brauchst du dir eigentlich nur den längesten Weg durch den Graph suchen, wobei die Kanten bei dir immer das gleiche Gewicht haben. Hast du nämlich den längesten Weg, dann hast du auch die meisten Konten durchlaufen und somit auch die meisten Knoten abwechselnd gefärbt. (Zumindest wenn ich mich in der Eile jetzt nicht täusche.) Zumindest mal für die ein guter denkanstoß.
Ein kleines Beispiel wie man den "kürzesten" Weg findet: http://de.wikipedia.org/wiki/Dijkstra-Algorithmus
(Ja ja, wikipedia, hatte grad keinen Wissenschaftlichen Link parat!)
Nur Knoten vorhanden, keine Kanten:
Das kauen wir durch wenn das der Fall sein sollte
/E: Das ganze hört sich übrigens sehr stark nach Bipartiter Graph an...
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von JJDTE am 14.07.2009 17:04]
|
|
|
|
|
|
| Zitat von Teufel
| Zitat von Kambfhase
Kann mir einer einen Algorithmus erstellen?
Ich möchte bei einem Graphen die Knoten so einfärben, dass nie zwei verbundene Knoten "schwarz" sind. Es gibt nur die Zustände "schwarz" und "weiß".
Allerdings will ich den Graphen nicht nur irgendwie einfärben, sondern die maximale Zahl an schwarzen Knoten erreichen.
Zudem sind Näherungswerte unerwünscht. Nur das exakte Maximum ist sinnvoll.
Hat einer da was auf Lager? Vllt. ein Informatik-Student?
Mit fragenden Grüßen, Hase
ps. sollte ich das vllt im Gerhirnsalat oder so nochmal posten/ zitieren? | |
Wenn du Knoten abwechselnd einfärben willst, sollte der Modulo dir helfen...
| |
Wirtschaft-Informatik?
|
|
|
|
|
|
|
Jau, nach kurzem Nachdenken erhärten sich meine Vermutungen!
Schau mal hier rein, das sollte dein problem lösen:
http://en.wikipedia.org/wiki/Matching#Maximum_bipartite_matchings
Jaja, wieder wikipedia, zum informieren reicht es aber allemal.
/E: Oh, trippel Post, sry.
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von JJDTE am 14.07.2009 17:08]
|
|
|
|
|
|
| Zitat von JJDTE
Leider nicht genug spezifiziert..
Um was für Graphen handelt es sich denn? Die Knotenverbindungen bestehen bereits? Oder soll der Graph durch den Algo mit aufgespannt werden? Sprich es existieren nur die Knoten oder bereits der gesamte Graph mit Knoten
und Kanten? Gerichtet? Ungerichtet? Zyklisch? usw.
| |
Gerichtet? Ungerichtet? Zyklopädisch? Keine Ahnung.
Der Kontext:
Konkret geht es ums Sudoku lösen. Dort gibt es eine "Master-Technik" die Subset-Counting heißt. Dort wählt man einen Haufen Zellen und guckt dann wie oft man jeden Kandidaten(1..9) maximal unterbringen kann. Die zusammen addiert geben den Count. Falls der Count durch einen Kandidaten außerhalb des Subsets unter die Zahl der Zellen reduziert werden würde, wäre das Sudoku fehlerhaft. Dh. jener Kandidat scheidet aus. Meine Idee war jetzt dieses Maximal-Problem mittels Graphen zu lösen.
Ich glaube, ich hatte meinen Quellcode sogar schon mal irgendwo gepostet.
/e: ein bipartiter Graph ist es nicht, da die weiße Seite nicht unbedingt perfekt ist. Hab ich zB. 3 Zellen in einer Spalte folgt für den Graphen ein Dreieck. Somit kann ich höchsten 1 Knoten schwarz färben. Sollte ich vorher vllt noch einen Algorithmus anschließen, mit dem ich den Graphen vereinfache? Dh. Knoten die alle die selben Knoten und sich selber berühren zu einem Knoten zusammen fügen.
/e²³: kann mir einer Faz.net hacken? - schon gut, den lädt mein Vater mir morgen umsonst runter.
|
[Dieser Beitrag wurde 3 mal editiert; zum letzten Mal von Kambfhase am 15.07.2009 22:53]
|
|
|
|
|
|
|
|
|
|
Na also, wenn sich so viele gut bezahlte leute darüber gedanken machen, dann muss ich das auch nicht noch umbedingt machen.
|
|
|
|
|
|
|
Morgen gehts wieder nach Hamburg und ich kann schon seit gestern nicht mehr ruhig sitzen (obwohl es erst Dienstag ernst wird). Scheiß Nervösität
Aber ich treffe Kambfhase \o/
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von Redh3ad am 19.07.2009 12:54]
|
|
|
|
|
|
und Ine
|
|
|
|
|
|
|
|
|
|
|
Och
|
|
|
|
|
|
|
Ja, muss wohl arbeiten
|
|
|
|
|
|
|
da kann er sich doch mal frei nehmen wenn du in seine Hood kommst
|
|
|
|
|
|
|
Ganz seine "Hood" ist das auch nicht, er wohnt in Bremen
|
|
|
|
|
|
|
Achja
|
|
|
|
|
|
|
ICE ist wieder proppenvoll, Platzreservierung heute morgen am Automaten hat natürlich nicht geklappt
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Meine Beine tun weh vom rumlaufen durch Hamburg
Wir haben ne Kamera vergessen, Hase
|
|
|
|
|
|
|
Yay, Win7 Gutschein ist da \o/
|
|
|
|
|
|
Thema: » ScriptPoker « ( Der Club der toten Scripter ) |