Ich habe keine Ahnung von Robotik, aber vielleicht hilft dir dieser Link weiter " [Only registered and activated users can see links. Click Here To Register...] " .
Coders Chit-Chat
11/19/2016 22:54
Keyed##721
11/19/2016 23:23
warfley#722
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...].Quote:
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.
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
11/19/2016 23:54
D3luxe.#723
Lego-Roboter? XDQuote:
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...
11/20/2016 01:04
alpines#724
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:
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...
11/20/2016 02:57
bLUM3#725
Fläche ist nicht bekannt, soll auch dynamisch funktionieren :-/ Werd mir aber sonst alles andere was gepostet wurd anschauen. Danke schonmal! Weitere Erleuchtungen erwünschtQuote:
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
11/20/2016 21:25
warfley#726
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).Quote:
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
12/08/2016 12:12
Goku.#727
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)
12/08/2016 12:15
Syc#728
Spricht etwas dagegen die Fragen direkt hier zu stellen?Quote:
12/08/2016 23:53
Sycrog#729
Würde mich nicht als Experten bezeichnen, habe aber schon öfters damit gearbeitet.Quote:
12/21/2016 09:26
Devsome#730
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
12/21/2016 12:03
Der-Eddy#731
Aber hier gibts keine coolen Bots! :(Quote:
;emilia
12/21/2016 12:05
Devsome#732
Das stimmt , aber die Bilder könnte man dennoch hier posten dann.Quote:
;emilia
:hype
12/21/2016 12:08
Der-Eddy#733
Ich glaube das verfehlt dann den Sinn dieses Threads :DQuote:
:hype
[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 :)
03/07/2017 17:55
Syc#734
VS 2017 ist da [Only registered and activated users can see links. Click Here To Register...]
03/09/2017 16:23
Bobo#735
Gibts irgendein Programm/Skript das automatisch jede 5 Minuten etwas im Chat auf einer Seite posten kann?