Top-Themen

Aktuelle Themen (A bis Z)

Administrator.de FeedbackApache ServerAppleAssemblerAudioAusbildungAuslandBackupBasicBatch & ShellBenchmarksBibliotheken & ToolkitsBlogsCloud-DiensteClusterCMSCPU, RAM, MainboardsCSSC und C++DatenbankenDatenschutzDebianDigitiales FernsehenDNSDrucker und ScannerDSL, VDSLE-BooksE-BusinessE-MailEntwicklungErkennung und -AbwehrExchange ServerFestplatten, SSD, RaidFirewallFlatratesGoogle AndroidGrafikGrafikkarten & MonitoreGroupwareHardwareHosting & HousingHTMLHumor (lol)Hyper-VIconsIDE & EditorenInformationsdiensteInstallationInstant MessagingInternetInternet DomäneniOSISDN & AnaloganschlüsseiTunesJavaJavaScriptKiXtartKVMLAN, WAN, WirelessLinuxLinux DesktopLinux NetzwerkLinux ToolsLinux UserverwaltungLizenzierungMac OS XMicrosoftMicrosoft OfficeMikroTik RouterOSMonitoringMultimediaMultimedia & ZubehörNetzwerkeNetzwerkgrundlagenNetzwerkmanagementNetzwerkprotokolleNotebook & ZubehörNovell NetwareOff TopicOpenOffice, LibreOfficeOutlook & MailPapierkorbPascal und DelphiPeripheriegerätePerlPHPPythonRechtliche FragenRedHat, CentOS, FedoraRouter & RoutingSambaSAN, NAS, DASSchriftartenSchulung & TrainingSEOServerServer-HardwareSicherheitSicherheits-ToolsSicherheitsgrundlagenSolarisSonstige SystemeSoziale NetzwerkeSpeicherkartenStudentenjobs & PraktikumSuche ProjektpartnerSuseSwitche und HubsTipps & TricksTK-Netze & GeräteUbuntuUMTS, EDGE & GPRSUtilitiesVB for ApplicationsVerschlüsselung & ZertifikateVideo & StreamingViren und TrojanerVirtualisierungVisual StudioVmwareVoice over IPWebbrowserWebentwicklungWeiterbildungWindows 7Windows 8Windows 10Windows InstallationWindows MobileWindows NetzwerkWindows ServerWindows SystemdateienWindows ToolsWindows UpdateWindows UserverwaltungWindows VistaWindows XPXenserverXMLZusammenarbeit

Mathematisches Problem, ges.: Anzahl Wege über ein Schachbrett

Mitglied: Garrarufa

Garrarufa (Level 1) - Jetzt verbinden

03.10.2013 um 15:13 Uhr, 1996 Aufrufe, 5 Kommentare

Hallo,

warscheinlich ist das nicht gerade das richtige Forum für solche Fragen, aber bevor ich mich wieder woanders registrieren muss, probiere ich es trotzdem hier.
Ich schreibe im Moment eine Android App, bei der ein beliebig großes 2-dimensionales Feld aus Buttons angezeigt wird.
Man soll auf 2 verschiedene Buttons klicken und dann wird ein zufälliger Weg dazwischen ausgerechnet und eingefärbt.
Bei größeren Feldern dauert das ziemlich lange und ich brauche eine Anzeige, die eine Schätzung abgibt, wie lange die Suche voraussichtlich noch dauern wird.
Dazu müsste ich ausrechnen, wie viele mögliche Wege es von meinem Startpunkt zu jedem beliebigen anderen Punkt auf dem Feld gibt, da ich im schlimmsten Fall alle diese Möglichkeiten durchprobiere.
Dabei ist zu beachten, dass ich mich von jedem Punkt nur in vertikaler oder horizontaler Richtung bewegen kann, also nicht schräg.
Wenn mir dazu jemand eine Formel sagen könnte, wäre ich schon mal glücklich.
Um es ganz genau zu machen, gibt es aber noch eine weitere Einschränkung.
Zwei Wegstücke verlaufen niemals parallel direkt nebeneinander. D.h. zwischen zwei Wegabschnitten ist immer mindestens eine freie Reihe Buttons. Zwei Wegstücke können sich nur in einem Fall berühren, nämlich wenn sich zwei Ecken schräg gegenüber liegen. Diese berühren sich dann in genau einem Punkt.
Ich hoffe das war verständlich, wenn nicht, bitte fragen.
Hoffentlich kann mir jemand helfen!

Grüße
Garrarufa
Mitglied: Bitboy
03.10.2013 um 15:39 Uhr
Hi,

so wie ich es verstanden habe, hast du da "unmögliches" vor. Wenn der Weg komplett zufällig ist, gibt es da nichts zu schätzen. Es könnte der kürzeste oder auch der längst mögliche Weg sein der da am Ende bei rauskommt. Nur ausgehend von den 2 gewählten Punkten kann man aber nichts sagen.

Sehr stark vereinfacht könntest du die Zahl der schon besuchten Felder durch die gesamtzahl der Felder Teilen und das Ergebnis in Prozent angeben. Der Anwender sieht dann wieviel Spielfläche schon abgelaufen wurde.

Mathegenies können bestimmt noch anhand der Reglen die Zahl der noch möglichen Felder berechnen und somit die Anzeige verfeiernen, aber das übersteigt mein können ;)
Bitte warten ..
Mitglied: Garrarufa
03.10.2013 um 16:05 Uhr
Mir ist klar, dass ich nicht anzeigen kann, wie lange es noch dauert, bis die Berechnung fertig ist.
Was ich anzeigen möchte, ist die prozentuale Anzahl der bereits probierten Wege, gemessen an der Anzahl der möglichen Wege. Kann natürlich sein, dass schon nach 1% ein Weg gefunden wurde. Die Anzeige zeigt nur die maximale Dauer an.
Bitte warten ..
Mitglied: Dirmhirn
03.10.2013 um 16:49 Uhr
HI!

das kannst du(man) vll über Graphen Theorie lösen. Alle Nachbarknoten von markierten Knoten dürfen nicht mehr besucht werden, so kannst du einmal die überhaupt noch möglichen Knoten abschätzen. Hinzu kommt dann, wenn das Feld zb schon mal geteilt ist - dann kannst du die eine Hälfte auch nicht mehr besuchen (falls sich die Wege nicht kreuzen dürfen).

Im Bereich der Mustererkennung kannst du dich auch umsehen - Anzahl der Pixel/nicht markierten Knoten - dafür gibt es Algorithmen.
kA ob die dann nicht länger brauchen als der Rest... aber ja...

was ist wenn du einfach das Verhältnis der restlichen Knoten zu den bereits markierten nimmst?

sg Dirm
Bitte warten ..
Mitglied: Lochkartenstanzer
03.10.2013, aktualisiert um 17:44 Uhr
Moin,

Du kannst die maximale Anzahl de Wege nach oben abschätzen:

Durch die vorgabe der nachbarschaft kannst Du effektiv ca. nur maximal die hälfte aller felder besuchen. wenn man die Sonderfälle an den Rändern des feldes wegläßt, hat Du bei jedem Feld ca. 3 mögliche variantionen "weiterzugehen", rechts links gerade. Damit ist eine obere Grenze 3^(n/2) mit n als Anzahl der "buttons" auf dem Feld.

lks
Bitte warten ..
Mitglied: Garrarufa
15.10.2013 um 16:32 Uhr
Danke für eure Antworten, ich habe mir die Zeit genommen das Problem nochmal zu überdenken und bin auf einen einfacheren Algorithmus gekommen, der erstens schneller zum Ziel kommt und zweitens einfacher abzuschätzen ist.
Idee: Alle Felder auf dem Schachbrett in zufälliger Reihenfolge füllen, bis nur noch ein Weg vom Start- zum Endpunkt übrig bleibt.
Bitte warten ..
Ähnliche Inhalte
Basic

Regex Anzahl Character Nicht Anzahl Bytes

gelöst Frage von PeronasBasic6 Kommentare

Guten Morgen zusammen, und zwar habe ich eine Frage bzgl. RegEx/RegExp. Ich habe einen regulären Ausdruck der wie folgt ...

Firewall

Windows-Firewall und Logging wegen SQL-Problem

gelöst Frage von HenereFirewall13 Kommentare

Servus zusammen, mal wieder eine andere Baustelle Server 2012 Format-Software - WUP Es wird eine Exe aus einer Freigabe ...

Router & Routing

Zwei Netze per VPN verbinden, ges. Internet-Traffic zu einem Netz routen

gelöst Frage von andreaswalterRouter & Routing3 Kommentare

Hallo, ich habe folgendes Szenario: Lokation A: Internetzugang, Kabel Fritzbox. Ist: 192.168.0.0 Lokation B: Zugang zum Internet über ein ...

Windows Server

GPO Fehlermeldung wegen inetres.admx

gelöst Frage von Looser27Windows Server2 Kommentare

Guten Morgen allerseits, als ich gestern nach langer Zeit nochmal etwas an einer der GPO's ändern mußte, erwartete mich ...

Neue Wissensbeiträge
Windows Userverwaltung

Passwortwechsel in der Domain bei Anmeldung erzwingen

Anleitung von Looser27 vor 3 StundenWindows Userverwaltung

Nachdem es immer wieder User geschafft haben, sich während des laufenden Betriebes auszusperren, habe ich nach einer Möglichkeit gesucht, ...

Ausbildung

Linux-Ausstieg in Niedersachsen - Windows statt Bugfix

Information von StefanKittel vor 3 TagenAusbildung37 Kommentare

Sind ja nur Steuergelder

Speicherkarten

Neuer Speicherkartentyp - zunächst nur für Huawei-Smartphones (künftig auch für Notebooks u. Tablets?)

Tipp von VGem-e vor 5 TagenSpeicherkarten6 Kommentare

Servus, als ob das "Chaos" i.S. Speicherkarten noch nicht groß genug wäre?! Evtl. kommt dieser neue Kartentyp bald auch ...

Sicherheit

Diverse D-Link-Router durch drei Schwachstellen kompromittierbar

Information von kgborn vor 5 TagenSicherheit1 Kommentar

Hat jemand D-Link-Router in Verwendung? Einige Modelle sind sicherheitstechnisch offen wie ein Scheunentor. Äußerst unschöne Sache, aber nichts neues ...

Heiß diskutierte Inhalte
Windows Userverwaltung
Passwortwechsel Zeitpunkt festlegen
gelöst Frage von Looser27Windows Userverwaltung32 Kommentare

Guten Morgen liebe Kolleginnen und Kollegen, da es eine Userin in meinem Urlaub geschafft hat, sich vom AD vollständig ...

Windows Server
Probleme im AD am Außenstandort
gelöst Frage von emeriksWindows Server19 Kommentare

Hi, wir haben ein Problem mit AD und GPO am Außenstandort und ich stehe momentan mächtig auf dem Schlauch. ...

Microsoft
Netzlaufwerksordner Berechtigungen Speichern unter aus Programmen
gelöst Frage von ITler7Microsoft19 Kommentare

Moin, bin in ein neues Unternehmen eingetreten und habe die Anforderung bekommen Berechtigungen auf einige Ordner anzupassen, da bisher ...

CMS
Seltsame Joomla-Meldung auf unserer WebSite
Frage von Winfried-HHCMS14 Kommentare

Hallo in die Runde! Kennt sich jemand mit Joomla aus? Im Backend unserer WebSite lesen wir seit einiger Zeit ...