Coders Chit-Chat

Quote:

Originally Posted by bLUM3 Jemand ne Idee wie ich einen guten Algorithmus für einen Roboter schreibe, der innerhalb eines vorgegebenen Bereichs alles abfährt? Dabei natürlich nicht mehrfach über die selbe Stelle fahren. Eingegrenzt ist der Bereich mit Schwarz, die Fläche wo er drüber fahren soll ist Weiß. 2 Polulu's vorne zum erkennen der Farbe.

Das ist einfach. Zunächst nehmen wir einfach mal an dass die gesamte Fläche bereits bekannt ist, als Graph bei dem jeder Knoten für ein Feld steht und jeweils kanten zu allen knoten direkt benachbarter Felder hat. Damit hast du das so genannte Hamiltonkreisproblem (bzw Hamiltonweg, da es ja kein geschlossener kreis sein muss) welches NP vollständig ist (siehe wikipedia). Das bedeutet das es (nach aktuellem Forschungsstand) keinen Algorithmus gibt der Asymptotisch effizienter ist als alle Möglichkeiten durchzuprobieren. Weitere Informationen dazu findest du [Only registered and activated users can see links. Click Here To Register...].

Wenn die Fläche nicht von Anfang an bekannt ist sondern erst durch das abfahren gebildet werden kann hast du ganz schlechte Karten. Ich habe zwar keinen beweis dafür, aber das ganze schreit irgendwie nach unentscheidbar für mich. Darum würde ich einfach am Anfang die Strecke abfahren, und danach den entsprechenden Hamiltonkreis berechnen

Quote:

Originally Posted by bLUM3 Jemand ne Idee wie ich einen guten Algorithmus für einen Roboter schreibe, der innerhalb eines vorgegebenen Bereichs alles abfährt? Dabei natürlich nicht mehrfach über die selbe Stelle fahren. Eingegrenzt ist der Bereich mit Schwarz, die Fläche wo er drüber fahren soll ist Weiß. 2 Polulu's vorne zum erkennen der Farbe.

Lego-Roboter? XD

Kannst du einfach so schreiben, dass sich der Roboter bei schwarz um eine bestimmte, evt. random Grad Zahl dreht und dann weiter fährt. Z.B. [90,110]°Wobei das natürlich nur für Kämpfe und nicht möglichst effizientes Abfahren gilt...

Quote:

Originally Posted by D3luxe. Lego-Roboter? XD Kannst du einfach so schreiben, dass sich der Roboter bei schwarz um eine bestimmte, evt. random Grad Zahl dreht und dann weiter fährt. Z.B. [90,110]°Wobei das natürlich nur für Kämpfe und nicht möglichst effizientes Abfahren gilt...

Dann könnte er aber wieder auf der selben Stelle landen oder einen Bereich ungültig machen indem er ihn sozusagen abschneidet, so einfach ist das leider nicht.

Quote:

Originally Posted by warfley Das ist einfach. Zunächst nehmen wir einfach mal an dass die gesamte Fläche bereits bekannt ist, als Graph bei dem jeder Knoten für ein Feld steht und jeweils kanten zu allen knoten direkt benachbarter Felder hat. Damit hast du das so genannte Hamiltonkreisproblem (bzw Hamiltonweg, da es ja kein geschlossener kreis sein muss) welches NP vollständig ist (siehe wikipedia). Das bedeutet das es (nach aktuellem Forschungsstand) keinen Algorithmus gibt der Asymptotisch effizienter ist als alle Möglichkeiten durchzuprobieren. Weitere Informationen dazu findest du [Only registered and activated users can see links. Click Here To Register...]. Wenn die Fläche nicht von Anfang an bekannt ist sondern erst durch das abfahren gebildet werden kann hast du ganz schlechte Karten. Ich habe zwar keinen beweis dafür, aber das ganze schreit irgendwie nach unentscheidbar für mich. Darum würde ich einfach am Anfang die Strecke abfahren, und danach den entsprechenden Hamiltonkreis berechnen

Fläche ist nicht bekannt, soll auch dynamisch funktionieren :-/ Werd mir aber sonst alles andere was gepostet wurd anschauen. Danke schonmal! Weitere Erleuchtungen erwünscht

Quote:

Originally Posted by bLUM3 Fläche ist nicht bekannt, soll auch dynamisch funktionieren :-/ Werd mir aber sonst alles andere was gepostet wurd anschauen. Danke schonmal! Weitere Erleuchtungen erwünscht

Ich hab den Spaß mal ein wenig durchgerechnet, und wie ich es mir gestern gedacht habe ist das Problem unentscheidbar. Der Beweis ging darüber das ich daher das die Fläche unbekannt ist, enthält ihr Graph n Knoten, mit n fest aber beliebig. Nun wenn man eine Struktur A(i) geschickt wählt also einen Graphen abhängig von i, sodass A(i) i Äquivalent unter FO Logik zu eine Unendlichen Graphen B, welcher zwei unendliche Teilgraphen enthält, dann kann man zeigen dass A nicht FO Axiomatisierbar ist. Das bedeutet das es keine Formel in Prädikatenlogik gibt, welche A von B unterscheiden kann. (Die konstruktion von A(i) ist nicht sonderlich kompliziert, die idee ist einfach 2^i viele Knoten zu verwenden).

Da es per definition in B unmöglich ist das Feld Abzufahren bedeutet dies nun zwangsläufig, dass es keine FO Formel gibt mit der sich dieses Problem beschreiben lässt.

Aus dem Beweis des Satz von Cook und Lewin folgt dass es zu jeder Turingmaschine einen Äquivalente Formel in Aussagenlogik gibt. Die Aussagenlogik ist per definition der Prädikatenlogit eine Teilmenge dieser.
Da es für dein Problem keine Formel in Prädikatenlogik gibt bedeutet dies, dass es auch keine Formel in Aussagenlogik gibt. Und damit dass es auch keine Turingmaschine gibt welche dieses Problem lösen kann.

Lange rede kurzer Sinn: Es ist unmöglich einen Algorithmus zu schreiben welcher dieses Problem löst.

Daher würde ich einfach einmal die Fläche abfahren, und dann einen Hammingkreis Algorithmus verwenden, bzw. einen bei dem die Fehler vernachlässigbar gering sind. Du kannst die besuchten Felder markieren, und versuchen diese zu vermeiden, damit sparst du dir eventuell diese doppelt zu fahren. Im wost case müsstest du all diese nochmal durchlaufen. Aber der Worst case sollte auch nur bei Spezialfällen vorkommen, daher müsste das so gar nicht mal so schlechte Ergebnisse liefern

Gibt es hier zufällig Node.js-Experten, die mir kurz einige Fragen beantworten könnte, ob es technisch möglich ist, ... umzusetzen. (es werden keine Coding Schnipssel benötigt, sondern, ob es technisch möglich ist)

Quote:

Originally Posted by .Kreativ'GFX Gibt es hier zufällig Node.js-Experten, die mir kurz einige Fragen beantworten könnte, ob es technisch möglich ist, ... umzusetzen. (es werden keine Coding Schnipssel benötigt, sondern, ob es technisch möglich ist)

Spricht etwas dagegen die Fragen direkt hier zu stellen?

Quote:

Originally Posted by .Kreativ'GFX Gibt es hier zufällig Node.js-Experten, die mir kurz einige Fragen beantworten könnte, ob es technisch möglich ist, ... umzusetzen. (es werden keine Coding Schnipssel benötigt, sondern, ob es technisch möglich ist)

Würde mich nicht als Experten bezeichnen, habe aber schon öfters damit gearbeitet.

Glaube Kreative'GFX braucht keine Hilfe mehr. @[Only registered and activated users can see links. Click Here To Register...]Leute wir haben auch noch einen Chit-Chat :3

Quote:

Originally Posted by Devsome Glaube Kreative'GFX braucht keine Hilfe mehr. @[Only registered and activated users can see links. Click Here To Register...]Leute wir haben auch noch einen Chit-Chat :3

Aber hier gibts keine coolen Bots! :(

;emilia

Quote:

Originally Posted by Der-Eddy Aber hier gibts keine coolen Bots! :( ;emilia

Das stimmt , aber die Bilder könnte man dennoch hier posten dann.

:hype

Quote:

Originally Posted by Devsome Das stimmt , aber die Bilder könnte man dennoch hier posten dann. :hype

Ich glaube das verfehlt dann den Sinn dieses Threads :D

[Only registered and activated users can see links. Click Here To Register...]

btw. hat einer ein paar coole Ruby Links? Hab bock mir das mal genauer anzuschauen :)

VS 2017 ist da [Only registered and activated users can see links. Click Here To Register...]

Gibts irgendein Programm/Skript das automatisch jede 5 Minuten etwas im Chat auf einer Seite posten kann?

Wenn es kein Problem ist, dass du die Seite im Hintergrund offen hast, dann würde sich das leicht mit einem Userscript lösen lassen.