Coders Chit-Chat

Keyed# · 11/19/2016, 22:54

Ich habe keine Ahnung von Robotik, aber vielleicht hilft dir dieser Link weiter "

" .

warfley · 11/19/2016, 23:23

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

.

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

D3luxe. · 11/19/2016, 23:54

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...

alpines · 11/20/2016, 01:04

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.

bLUM3 · 11/20/2016, 02:57

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 .

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

warfley · 11/20/2016, 21:25

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

Goku. · 12/08/2016, 12:12

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)

Syc · 12/08/2016, 12:15

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?

Sycrog · 12/08/2016, 23:53

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.

Devsome · 12/21/2016, 09:26

Glaube Kreative'GFX braucht keine Hilfe mehr. @

Leute wir haben auch noch einen Chit-Chat :3

Der-Eddy · 12/21/2016, 12:03

Quote:

Originally Posted by Devsome

Glaube Kreative'GFX braucht keine Hilfe mehr. @Leute wir haben auch noch einen Chit-Chat :3

Aber hier gibts keine coolen Bots!

;emilia

Devsome · 12/21/2016, 12:05

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

Der-Eddy · 12/21/2016, 12:08

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

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

Syc · 03/07/2017, 17:55

VS 2017 ist da

Bobo · 03/09/2017, 16:23

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